Number of Good Pairs

Easy
189.

Number of Good Pairs

Number of Good Pairs is an easy coding problem on arrays, hash table and math, asked in Amazon, Adobe and Cognizant interviews.

Given an array of integers nums, a pair (i, j) is good if nums[i] == nums[j] and i < j.

Return the number of good pairs.

Example 1

Input
nums = [1,2,3,1,1,3]
Output
4
Explanation
The good pairs are (0,3), (0,4), (3,4) and (2,5).

Example 2

Input
nums = [1,1,1,1]
Output
6
Explanation
Every one of the 4-choose-2 pairs qualifies.

Example 3

Input
nums = [1,2,3]
Output
0

Constraints

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var numIdenticalPairs = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Good Pairs — Solution in Python, Java & C++

Number of Good Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Number of Good Pairs is an easy coding problem on arrays, hash table and math, asked in Amazon, Adobe and Cognizant interviews.

Problem statement

Given an array of integers nums, a pair (i, j) is good if nums[i] == nums[j] and i < j.

Return the number of good pairs.

Example 1

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: The good pairs are (0,3), (0,4), (3,4) and (2,5).

Example 2

Input: nums = [1,1,1,1]
Output: 6
Explanation: Every one of the 4-choose-2 pairs qualifies.

Example 3

Input: nums = [1,2,3]
Output: 0

Constraints

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= 100

Hints for Number of Good Pairs

  1. Hint 1

    A value seen c times contributes c × (c - 1) / 2 pairs.

  2. Hint 2

    Or count as you scan: each new occurrence pairs with every earlier occurrence of the same value.

How to solve Number of Good Pairs

Each new occurrence of a value pairs with every earlier occurrence, so add the running count of that value before incrementing it.

Approach

  1. Keep count[value].
  2. For each x, add count[x] to the answer, then increment count[x].

Why it works

Summing the pre-increment counts over all occurrences of a value with total frequency c gives 0 + 1 + … + (c - 1) = c(c - 1)/2, the number of unordered pairs.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Incrementing before adding double-counts each element with itself.

Reference solution

Python

def numIdenticalPairs(nums):
    count = {}
    total = 0
    for x in nums:
        total += count.get(x, 0)
        count[x] = count.get(x, 0) + 1
    return total

Java

public static int numIdenticalPairs(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    int total = 0;
    for (int x : nums) {
        int seen = count.getOrDefault(x, 0);
        total += seen;
        count.put(x, seen + 1);
    }
    return total;
}

C++

int numIdenticalPairs(vector<int>& nums) {
    unordered_map<int, int> count;
    int total = 0;
    for (int x : nums) {
        total += count[x];
        count[x]++;
    }
    return total;
}

JavaScript

var numIdenticalPairs = function(nums) {
    const count = new Map();
    let total = 0;
    for (let i = 0; i < nums.length; i++) {
        const seen = count.get(nums[i]) || 0;
        total += seen;
        count.set(nums[i], seen + 1);
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets