Number Of Good Pairs - Leetcode Solution

Problem 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:

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.

Solution:

The solution to this problem can be found by using a HashMap where the keys of the map will be the elements of the input array and the values will be the frequency of each element in the array. We can then iterate through the input array and for each element nums[i], we can obtain the number of times it has been encountered previously by checking its frequency in the map. The number of good pairs for this value will be exactly equal to the frequency of this value. We can then update the frequency of this value in the map and move on to the next element of the array.

Code:

Here is the code for the Number Of Good Pairs problem on LeetCode:

public int numIdenticalPairs(int[] nums) {
    Map<Integer, Integer> frequencyMap = new HashMap<>();
    int numGoodPairs = 0;
    for (int i = 0; i < nums.length; i++) {
        int frequency = frequencyMap.getOrDefault(nums[i], 0);
        numGoodPairs += frequency;
        frequencyMap.put(nums[i], frequency + 1);
    }
    return numGoodPairs;
}

The time complexity of this solution is O(n) as we only need to loop through the input array once. The space complexity is also O(n) as we need to store the frequency of each element in the input array in a map.

1