Skip to content

1512. Number of Good Pairs

Description

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

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

 

Example 1:

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:

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

Example 3:

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

 

Constraints:

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

Solutions

Solution 1: Counting

Thinking

Count index pairs with \(i<j\) and \(nums[i]=nums[j]\). A double loop would pass for \(n\le 100\), but it rescans earlier equals on every step.

The current \(x\) forms one pair with each previous \(x\). A frequency map of values already seen lets us add that count and then increment, so one pass suffices.

Traverse the array, and for each element \(x\), count how many elements before it are equal to \(x\). This count represents the number of good pairs formed by \(x\) and the previous elements. After traversing the entire array, we obtain the answer.

The time complexity is \(O(n)\), and the space complexity is \(O(C)\). Here, \(n\) is the length of the array, and \(C\) is the range of values in the array. In this problem, \(C = 101\).

1
2
3
4
5
6
7
8
class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        ans = 0
        cnt = Counter()
        for x in nums:
            ans += cnt[x]
            cnt[x] += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int numIdenticalPairs(int[] nums) {
        int ans = 0;
        int[] cnt = new int[101];
        for (int x : nums) {
            ans += cnt[x]++;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int ans = 0;
        int cnt[101]{};
        for (int& x : nums) {
            ans += cnt[x]++;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func numIdenticalPairs(nums []int) (ans int) {
    cnt := [101]int{}
    for _, x := range nums {
        ans += cnt[x]
        cnt[x]++
    }
    return
}

1
2
3
4
5
6
7
8
function numIdenticalPairs(nums: number[]): number {
    const cnt: number[] = Array(101).fill(0);
    let ans = 0;
    for (const x of nums) {
        ans += cnt[x]++;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
impl Solution {
    pub fn num_identical_pairs(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut cnt = [0; 101];
        for &x in nums.iter() {
            ans += cnt[x as usize];
            cnt[x as usize] += 1;
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
/**
 * @param {number[]} nums
 * @return {number}
 */
var numIdenticalPairs = function (nums) {
    const cnt = Array(101).fill(0);
    let ans = 0;
    for (const x of nums) {
        ans += cnt[x]++;
    }
    return ans;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function numIdenticalPairs($nums) {
        $ans = 0;
        $cnt = array_fill(0, 101, 0);
        foreach ($nums as $x) {
            $ans += $cnt[$x]++;
        }
        return $ans;
    }
}

1
2
3
4
5
6
7
8
int numIdenticalPairs(int* nums, int numsSize) {
    int cnt[101] = {0};
    int ans = 0;
    for (int i = 0; i < numsSize; i++) {
        ans += cnt[nums[i]]++;
    }
    return ans;
}

Comments