Solution Explanation: Counting Good Pairs

This problem asks to find the number of "good pairs" in an array. A good pair (i, j) is defined as a pair of indices where nums[i] == nums[j] and i < j. The solution uses a counting approach to efficiently solve this.

Approach:

1. Initialization: We initialize a counter array (or hash map, depending on the language) cnt of size 101 (as the problem constraints specify numbers are between 1 and 100). This array will store the frequency of each number encountered in the nums array. We also initialize a variable ans to 0, which will store the total count of good pairs.

2. Iteration: We iterate through the nums array. For each element x:

   • We add the current count of x in cnt to ans. This is because each of the existing occurrences of x forms a good pair with the current x (since i < j).
   • We increment the count of x in cnt by 1.

3. Return Value: After iterating through the entire nums array, ans will contain the total number of good pairs. We return ans.

Time Complexity: O(n), where n is the length of the nums array. We iterate through the array once.

Space Complexity: O(C), where C is the range of numbers (101 in this case). The space complexity is dominated by the size of the cnt array (or hash map). In this specific problem, it's a constant space complexity because C is a constant.

Code Examples (with explanations):

The provided code examples in multiple languages implement this counting approach. Let's examine the Python and Java examples in more detail:

Python3:

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        ans = 0
        cnt = Counter() # Using Counter from collections for efficient counting
        for x in nums:
            ans += cnt[x] # Add existing count of x to ans
            cnt[x] += 1   # Increment count of x
        return ans

Here, Counter from the collections module provides a dictionary-like object that automatically handles counting element frequencies.

Java:

class Solution {
    public int numIdenticalPairs(int[] nums) {
        int ans = 0;
        int[] cnt = new int[101]; // Array of size 101 to store counts
        for (int x : nums) {
            ans += cnt[x]++; // Postfix increment: ans += cnt[x]; cnt[x]++;
        }
        return ans;
    }
}

The Java code uses a simple integer array cnt for counting. The line ans += cnt[x]++; cleverly uses the postfix increment operator to first add the current count to ans and then increment the count.

The other language examples follow a similar structure, adapting the counting mechanism to the specific features of each language. All solutions leverage the same core idea of efficient counting to achieve linear time complexity.