Count Pairs Of Nodes

You are given an undirected graph represented by an integer n, which is the number of nodes, and edges, where edges[i] = [ui, vi] which indicates that there is an undirected edge between ui and vi. You are also given an integer array queries.

The answer to the jth query is the number of pairs of nodes (a, b) that satisfy the following conditions:

a < b
cnt is strictly greater than queries[j], where cnt is the number of edges incident to a or b.

Return an array answers such that answers.length == queries.length and answers[j] is the answer of the jth query.

Note that there can be repeated edges.

Example 1:

Input: n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]
Output: [6,5]
Explanation: The number of edges incident to at least one of each pair is shown above.

Example 2:

Input: n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5]
Output: [10,10,9,8,6]

Constraints:

2 <= n <= 2 * 104
1 <= edges.length <= 105
1 <= ui, vi <= n
ui != vi
1 <= queries.length <= 20
0 <= queries[j] < edges.length

Solution:

cnt[i] is the count of edges for node i.
shared[i][j] is the count of shared edges between nodes i and j (if exists), where i < j.

How many node pairs i and j are there, so that cnt[i] + cnt[j] is greater than q?
- We can solve it in O(n) by sorting counts (sorted_cnt) and usign two-pointer approach.
How many connected node pairs are there, so that cnt[i] + cnt[j] is greater than q, but cnt[i] + cnt[j] - shared[i][j] is not?
- We can solve it in O(e) as there are no more than e connected node pairs.

The result is [1] - [2]. Pairs in [2] were incldued in [1] but they should not.

class Solution {
    public int[] countPairs(int n, int[][] edges, int[] queries) {
        int[] cnt = new int[n + 1], sorted_cnt = new int[n + 1], res = new int[queries.length];
        HashMap<Integer, Integer>[] shared = new HashMap[n + 1];
        for (var e : edges) {
            sorted_cnt[e[0]] = cnt[e[0]] = cnt[e[0]] + 1;
            sorted_cnt[e[1]] = cnt[e[1]] = cnt[e[1]] + 1;
            int n1 = Math.min(e[0], e[1]), n2 = Math.max(e[0], e[1]);
            shared[n1] = shared[n1] == null ? new HashMap() : shared[n1];
            shared[n1].put(n2, shared[n1].getOrDefault(n2, 0) + 1);
        }
        Arrays.sort(sorted_cnt);
        for (int q = 0; q < queries.length; ++q) {
            for (int i = 1, j = n; i < j; )
                if (queries[q] < sorted_cnt[i] + sorted_cnt[j])
                    res[q] += (j--) - i;
                else
                    ++i;
            for (int i = 1; i <= n; ++i)
                if (shared[i] != null)
                    for (var p : shared[i].entrySet()) {
                        int j =  p.getKey(), sh_cnt = p.getValue();
                        if (queries[q] < cnt[i] + cnt[j] && queries[q] + sh_cnt >= cnt[i] + cnt[j])
                            --res[q]; 
                    }
        }
        return res;
    }
}