Algorithms to Count the Equivalent Pairs in an Array

You are given a list of integers nums. Return the number of pairs i < j such that nums[i] = nums[j].

Constraints
0 ≤ n ≤ 100,000 where n is the length of nums

Example 1
Input
nums = [3, 2, 3, 2, 2]
Output
4
Explanation
We have index pairs (0, 2), (1, 3), (1, 4), (3, 4).

Using a Hash Table to Count Pairs

We can use a hash table to count the numbers that we have seen. Then if a ‘same’ number is seen again, we know it will add n pairs to the answer where n is the counter for the current seen number. This approach takes O(N) time and O(N) space where N is the number of elements in the array.

C++ code:

1
2
3
4
5
6
7
8
9

int countPairs(vector<int>& nums) {
    int ans = 0;
    unordered_map<int, int> data;
    for (auto &n: nums) {
        ans += data[n];
        data[n] ++;
    }
    return ans;
}

int countPairs(vector<int>& nums) {
    int ans = 0;
    unordered_map<int, int> data;
    for (auto &n: nums) {
        ans += data[n];
        data[n] ++;
    }
    return ans;
}

Python implementation based on the defaultdict:

1
2
3
4
5
6
7
8

class Solution:
    def countPairs(self, nums):
        data = defaultdict(int)
        ans = 0
        for i in nums:
            ans += data[i]
            data[i] += 1
        return ans

class Solution:
    def countPairs(self, nums):
        data = defaultdict(int)
        ans = 0
        for i in nums:
            ans += data[i]
            data[i] += 1
        return ans

Using Math/Combinatorics to Compute the Number of Pairs

We can count the frequencies for each number first. That will cost O(N) time and O(N) space. In python, we can do this using the Counter() object.

Then we can use math to count the number of pairs for each number which is C(N, 2) – pick two numbers from N, and it will be N*(N-1)/2

1
2
3

class Solution:
    def solve(self, nums):
        return sum(c * (c - 1) // 2 for c in Counter(nums).values())

class Solution:
    def solve(self, nums):
        return sum(c * (c - 1) // 2 for c in Counter(nums).values())

–EOF (The Ultimate Computing & Technology Blog) —