LeetCode 1512: Number of Good Pairs

Explanation:

To solve this problem, we can iterate through the array and keep track of the count of each number using a hashmap. For each number, if there are k occurrences of that number, we can form k*(k-1)/2 good pairs.

Algorithmic Idea:

1. Initialize a hashmap to store the count of each number.
2. Iterate through the array and update the count of each number in the hashmap.
3. For each number with count k, increment the total count of good pairs by k*(k-1)/2.
4. Return the total count of good pairs.

Time Complexity:

The time complexity of this solution is O(N), where N is the number of elements in the input array.

Space Complexity:

The space complexity of this solution is O(N) to store the count of each number in the hashmap.

:

class Solution {
    public int numIdenticalPairs(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        int goodPairs = 0;
        
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        
        for (int count : countMap.values()) {
            goodPairs += count * (count - 1) / 2;
        }
        
        return goodPairs;
    }
}