Problem

Given an array of integers nums, return the number ofgood pairs.

A pair (i, j) is called good if nums[i] == nums[j] and i < j.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are _good_.

Example 3

1
2

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

Constraints

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

Solution

Method 1 – Hash Map Counting

Intuition

For each number, count how many times it appears. For each value with count c, the number of good pairs is c*(c-1)/2.

Approach

  1. Use a hash map (or array) to count occurrences of each number.
  2. For each count c, add c*(c-1)//2 to the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        unordered_map<int,int> cnt;
        for (int x : nums) cnt[x]++;
        int ans = 0;
        for (auto& [k, c] : cnt) ans += c*(c-1)/2;
        return ans;
    }
};
1
2
3
4
5
6
7

func numIdenticalPairs(nums []int) int {
    cnt := make(map[int]int)
    for _, x := range nums { cnt[x]++ }
    ans := 0
    for _, c := range cnt { ans += c*(c-1)/2 }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import java.util.*;
class Solution {
    public int numIdenticalPairs(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) cnt.put(x, cnt.getOrDefault(x, 0)+1);
        int ans = 0;
        for (int c : cnt.values()) ans += c*(c-1)/2;
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun numIdenticalPairs(nums: IntArray): Int {
        val cnt = mutableMapOf<Int,Int>()
        for (x in nums) cnt[x] = cnt.getOrDefault(x,0)+1
        var ans = 0
        for (c in cnt.values) ans += c*(c-1)/2
        return ans
    }
}
1
2
3
4
5

class Solution:
    def numIdenticalPairs(self, nums: list[int]) -> int:
        from collections import Counter
        cnt = Counter(nums)
        return sum(c*(c-1)//2 for c in cnt.values())
1
2
3
4
5
6
7
8

use std::collections::HashMap;
impl Solution {
    pub fn num_identical_pairs(nums: Vec<i32>) -> i32 {
        let mut cnt = HashMap::new();
        for &x in &nums { *cnt.entry(x).or_insert(0) += 1; }
        cnt.values().map(|&c| c*(c-1)/2).sum()
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    numIdenticalPairs(nums: number[]): number {
        const cnt: Record<number, number> = {};
        for (const x of nums) cnt[x] = (cnt[x]||0)+1;
        let ans = 0;
        for (const c of Object.values(cnt)) ans += c*(c-1)/2;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums.
  • 🧺 Space complexity: O(n).