Number of Good Pairs

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.

Key Insights

• A good pair consists of two indices where the values at these indices are the same.
• To count good pairs efficiently, we can use a hash map (or dictionary) to keep track of the occurrences of each number as we iterate through the array.
• For each occurrence of a number, the number of good pairs that can be formed is equal to the count of that number seen so far (since each previous occurrence can form a pair with the current index).

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we will use a hash map (or dictionary) to count the occurrences of each number in the array. As we iterate through the array, for each number, we will:

1. Check how many times it has appeared before (using the hash map).
2. Add that count to a running total of good pairs (since each previous occurrence can form a good pair with the current index).
3. Update the hash map to include the current number.

This approach ensures that we only need to traverse the array once, making it efficient.

Code Solutions