Number of Good Pairs

class Solution {
public:
    int countGoodPairs(vector<int>& data) {
        unordered_map<int, int> occurrence;
        int result = 0;
        
        for (int value: data) {
            result += occurrence[value];
            occurrence[value]++;
        }
        
        return result;
    }
};

The solution to the "Number of Good Pairs" involves using a hash map to count occurrences of each integer in the input vector. Implement this function in C++ to compute how many pairs of indices (i, j) in the array satisfy that i < j and the elements at these indices are equal. Follow these instructions to grasp the implementation:

• Initialize an unordered_map to keep track of the occurrences of each number as you iterate through the vector.
• For every element in the vector:
  • Increment your result by the current count of that element in the map before the increment. This count represents the number of times the current number has appeared before, which translates directly to the number of new good pairs formed with this occurrence.
  • Increase the count of that number in your map.
• Finally, return the count of good pairs.

Key considerations:

• Use of an unordered map ensures average constant time complexity for operations, making this approach efficient.
• The code iterates through the array once, giving it a time complexity of O(n), where n is the number of elements in the input vector.
• Space complexity is O(m), where m is the number of distinct elements in the vector, due to the usage of the hash map for tracking occurrences.

This method is both powerful and succinct, leveraging the properties of hash maps to deliver a solution that is easy to understand and implement.

class Solution {
    public int countGoodPairs(int[] elements) {
        Map<Integer, Integer> frequency = new HashMap<>();
        int goodPairs = 0;

        for (int element: elements) {
            goodPairs += frequency.getOrDefault(element, 0);
            frequency.put(element, frequency.getOrDefault(element, 0) + 1);
        }
        
        return goodPairs;
    }
}

The Java solution provided efficiently calculates the number of good pairs in an array where a pair (i, j) is considered good if both elements are equal and i < j. The implementation utilizes a HashMap to keep track of the frequency of each element encountered as the array is traversed.

The process goes as follows:

1. Initialize a HashMap (frequency) to store the frequency of each element from the input array elements.
2. Initialize a variable goodPairs to zero. This will store the count of good pairs.
3. Iterate through each element in the elements array.
   • Calculate the number of good pairs for the current element by adding the current frequency of the element (obtained using .getOrDefault()) to goodPairs.
   • Update the frequency map for the current element. Increment the count of the current element in frequency map.
4. Finally, return the value of goodPairs, which now holds the total count of all good pairs in the array.

class Solution:
    def countGoodPairs(self, values: List[int]) -> int:
        num_counter = defaultdict(int)
        good_pairs = 0
        
        for value in values:
            good_pairs += num_counter[value]
            num_counter[value] += 1
        
        return good_pairs

The given Python code outlines a method for counting "Good Pairs" in a list of numbers. A good pair is defined as a pair of indices (i, j) such that the numbers at those indices are equal, and i < j.

The approach employs a dictionary to track the occurrences of each number as they're encountered in the list. As each number is processed:

• The current tally of good pairs increases by the count of that number seen so far, which represents the number of new good pairs that can be formed with the current number.
• The count for that number is then incremented, reflecting its latest occurrence.

The use of a dictionary to maintain counts ensures that the solution is efficient, utilizing the hashing mechanism for fast access and update operations. The algorithm elegantly accomplishes the task in O(n) time complexity, where n is the number of elements in the list, by making a single pass through the list and performing constant-time operations for each element.

The final return value gives the total number of good pairs in the list.

To execute this solution, ensure to import defaultdict from collections as it plays a crucial role in counting occurrences dynamically.