Count pairs of nodes

Array Hash Table Two Pointers Binary Search Graph Theory Sorting Counting

42.5% acceptance

Feb 25, 2026

344

172

You are given an undirected graph. Let incident(a, b) be the number of edges connected to either node a or b. Return answers[j] = number of pairs (a, b) where a < b and incident(a, b) > queries[j].

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn count_pairs(n: i32, edges: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
    let n = n as usize;
    let mut deg = vec![0i32; n + 1];
    let mut edge_cnt: HashMap<(usize, usize), i32> = HashMap::new();
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      deg[u] += 1;
      deg[v] += 1;
      *edge_cnt.entry((u.min(v), u.max(v))).or_insert(0) += 1;
    }
    let mut sorted_deg: Vec<i32> = (1..=n).map(|i| deg[i]).collect();
    sorted_deg.sort_unstable();

    queries.iter().map(|&q| {
      // Count pairs with sorted_deg[l]+sorted_deg[r] > q
      let mut l = 0usize;
      let mut r = n - 1;
      let mut cnt = 0i64;
      while l < r {
        if sorted_deg[l] + sorted_deg[r] > q {
          cnt += (r - l) as i64;
          r -= 1;
        } else {
          l += 1;
        }
      }
      // Subtract over-counted: edge (u,v) counted where sum>q but sum-shared<=q
      for (&(u, v), &ec) in &edge_cnt {
        let sum = deg[u] + deg[v];
        if sum > q && sum - ec <= q {
          cnt -= 1;
        }
      }
      cnt as i32
    }).collect()
  }
}