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:

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

Example 2:

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

Example 3:

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

Constraints:

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

Solution

Brute Force

The brute force approach would require two iterations through nums array. For each given number, check how many times it occurs other than this index position. Everytime we see the number again, we add 1 to count.

 1class Solution {
 2    public int numIdenticalPairs (int[] nums) {
 3        int count = 0;
 4        for (int i = 0; i < nums.length; i++) {
 5            for (int j = i; j < nums.length; j++) {
 6                if ((nums[i] == nums[j]) && (i < j)) {
 7                    count++;
 8                }
 9            }
10        }
11        return count;
12    }
13}

Using Hashing

This problem is essentially asking us to check how many times, we see number which was already seen before. Now, if we have seen a number 2 times before, that means the current number could form two good pairs. In below code, the number at index position 5 could form two good pairs using (1, 5) and (3,5). The number at index position 6 could form 3 good pairs as (1,6), (3,6) and (5,6).

1 1 3 5 3 2 3 3

So, each time, we encounter a number, we have to add how many times we have seen this number before current on to count variable. This way we will eventually have number of good pairs count.

 1class Solution {
 2    public int numIdentialPairs (int[] nums) {
 3        Map<Integer, Integer> map = new HashMap<>();
 4        int count = 0;
 5        for (int i = 0; i < nums.length; i++) {
 6            count += map.getOrDefault(nums[i], 0);
 7            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
 8        }
 9        return count;
10    }
11}
  • Time Complexity: O(n) since we have to iterate through nums array to populate map and count good pairs.
  • Space Complexity: O(n). In worst case, we may not find any good pairs and all numbers might be unique.