Code Logo

Number of Good Pairs

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given an array of integers, count the number of good pairs. A pair (i, j) is good if nums[i] == nums[j] and i < j. The order matters — each valid pair is counted separately based on its indices, not the values.

A brute force double loop would check every possible pair in O(n²) time. A hash map approach reduces this to O(n): count how many times each number occurs, then for each frequency, the number of pairs is n * (n - 1) / 2. This formula counts all combinations of two indices among the n occurrences of the same value.

The hash map collects frequencies in one pass. Then a second pass over the map sums up the pair counts. For example, if a number appears 4 times, there are 4 * 3 / 2 = 6 good pairs for that number. This works because each pair is defined by picking any two distinct indices, and the condition i < j is automatically satisfied by exactly half of the ordered pairs.

Edge cases include an empty array (return 0), an array with all distinct values (return 0), and an array with all identical values (return n * (n-1) / 2).

The combination formula n * (n-1) / 2 comes from choosing 2 positions out of n. Since order does not matter for indices (i < j is automatic when picking distinct indices), each unordered pair of equal-valued positions forms exactly one good pair. This formula avoids nested loops entirely.

Example Input & Output

Example 1
Input
[1,1,1,1]
Output
6
Explanation

Four 1s: 4*3/2 = 6 pairs.

Example 2
Input
[5,5,5]
Output
3
Explanation

Three 5s: 3*2/2 = 3 pairs.

Example 3
Input
[1,2,3,1,1,3]
Output
4
Explanation

Pairs: (0,3),(0,4),(3,4) for 1; (2,5) for 3.

Example 4
Input
[1,2,3]
Output
0
Explanation

All distinct values, no pairs.

Example 5
Input
[]
Output
0
Explanation

Empty array has no pairs.

Algorithm Flow

Recommendation Algorithm Flow for Number of Good Pairs
Recommendation Algorithm Flow for Number of Good Pairs

Solution Approach

Count frequencies with a hash map. Sum n * (n-1) / 2 for each frequency n.

function solution(nums) {
  var freq = {};
  for (var i = 0; i < nums.length; i++) {
    freq[nums[i]] = (freq[nums[i]] || 0) + 1;
  }
  var total = 0;
  for (var k in freq) {
    var n = freq[k];
    total += n * (n - 1) / 2;
  }
  return total;
}

Time O(n), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[] nums) {
        Map<Integer,Integer> freq = new HashMap<>();
        for (int n : nums) freq.put(n, freq.getOrDefault(n, 0) + 1);
        int total = 0;
        for (int n : freq.values()) total += n * (n - 1) / 2;
        return total;
    }
}