Vultr DocsLatest Content

Number of Good Pairs

Updated on 27 June, 2025
Number of Good Pairs header image

Problem Statement

In this problem, you are provided with an array of integers named nums. Your goal is to determine how many "good pairs" can be formed from this array. A pair (i, j) is defined as good if two conditions are satisfied:

  1. The elements at the two indices are equal, i.e., nums[i] == nums[j].
  2. The first index i is less than the second index j.

This problem requires you to count and return the number of such good pairs.

Examples

Example 1

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.

Example 2

Input:

nums = [1,1,1,1]

Output:

6

Explanation:

Each pair in the array are *good*.

Example 3

Input:

nums = [1,2,3]

Output:

0

Constraints

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

Approach and Intuition

Based on the given problem, considerations, and examples, let's develop an understanding of the required approach:

  1. Understanding the Good Pair: A good pair is defined based on the equality of the values at two distinct indices and the order of these indices (i.e., the first index should be less than the second). Thus, for an array element nums[i], a good pair is formed with nums[j] if i < j and nums[i] == nums[j].

  2. Exploring Examples:

    • Example 1: For the array [1,2,3,1,1,3], we find that elements 1 and 3 each form multiple good pairs:

      • Pairs like (0, 3), (0, 4), and (3, 4) indicate the various combinations for the value 1.

    • Example 2: In the array [1,1,1,1], every distinct pair of indices forms a good pair as all elements are equal.

    • Example 3: For the array [1,2,3], no good pairs exist since no two elements are equal.

  3. Algorithm Design:

    To count the number of good pairs:

    • Start iterating through the array with a nested loop where the inner loop always starts from the index next to the outer loop's index.

    • For each pair of indices, check if the elements are the same.

    • Count such pairs and return the total count.

  4. Constraints Handling:

    Given the constraint 1 <= nums.length <= 100, the described pair comparison method is feasible within the allowable computational limits. Performance becomes a significant concern with higher bounds, but with a maximum of 5050 comparisons (in the case of the largest array), the approach will run efficiently for the maximum inputs specified.

In summary, the solution involves iterating over pairs of elements in the array and counting those that meet the criteria for "good". This method ensures that all potential pairs are considered, and the imposed constraints on array size and element size are respected. Hence, it remains computationally effective for the given problem bounds.

Solutions

  • C++
  • Java
  • Python
cpp 
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.

java 
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.
python 
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.

Comments

No comments yet.