Count Pairs with Equal Values
Solve this ProblemEasy15 min
Topics
BasicsComplexityArraysHashing
Companies
TCSInfosysWipro
Given an array
nums, return how many pairs of positions i < j hold equal values.
This problem puts O(n)Linear Time O(n)Work proportional to the input size. and O(n²)Quadratic Time O(n²)Work proportional to the square of the input size. side by side. Checking every pair takes n(n − 1)/2 comparisons; remembering counts in a map turns the job into one pass. For 1000 values that is about 500,000 steps versus 1000; for a million values it is the difference between hours and a fraction of a second. The faster version trades extra memory for time — a very common bargain.
Test Case 1:
Input:nums = [4, 7, 4, 4, 7]
Output:4
Explanation:The three 4s form 3 pairs and the two 7s form 1 pair.
Test Case 2:
Input:nums = [1, 2, 3]
Output:0
Explanation:All values are different.
Constraints
- ◆
1 ≤ nums.length ≤ 1000 - ◆
-1000000 ≤ nums[i] ≤ 1000000
Try the Dry Run
Approach & Solutions
Compare Every PairBrute
Check every pair of positions i < j and count those with equal values. Simple and memory-free, but it makes n(n − 1)/2 comparisons — about half a million for 1000 values.
Time
O(n²)Space
O(1)Java
class Solution {
public int equalPairs(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j]) {
count++;
}
}
}
return count;
}
}Count with a Frequency MapOptimal
Walk the array once and remember how many times each value has been seen so far. A new value v pairs with every earlier copy of v, so add seen[v] to the answer, then increase seen[v]. One pass of O(1) map operations gives O(n) time, paid for with O(n) extra memory. (C uses an array indexed by value + 1,000,000 as its counter.)
Time
O(n)Space
O(n)Java
class Solution {
public int equalPairs(int[] nums) {
Map<Integer, Integer> seen = new HashMap<>();
int count = 0;
for (int value : nums) {
int before = seen.getOrDefault(value, 0);
count += before;
seen.put(value, before + 1);
}
return count;
}
}