Jobs

Interviews

Discussions

Number of Good Pairs

Easy

Asked by:

More companies

19 views

Topics:

Arrays

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.

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

Try coding it in LeetCode

Number of Good Pairs

Easy

Asked by:

19 views

Topics:

Arrays

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.

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `nums`?
Can the integers in `nums` be negative, zero, or only positive?
Are we expecting to handle very large integer values which could cause overflow issues?
If the input array is empty or null, what should I return?
Could the input array contain duplicate numbers, and if so, how should they be handled?

Brute Force Solution

Approach

The brute force approach to finding good pairs involves checking every single possible pair of numbers from the list. We compare each number to every other number in the list to see if they match. If they do, we count that as a good pair.

Here's how the algorithm would work step-by-step:

Take the first number in the list.
Compare it to every other number in the list, one by one.
If any of the numbers it's compared to are the same as the first number, count that as a 'good pair'.
Move on to the second number in the list.
Compare the second number to every other number in the list, just like we did with the first number.
Again, if any of the numbers it's compared to are the same as the second number, count that as a 'good pair'.
Keep doing this for every number in the list.
Once you've gone through every number and compared it to all the others, add up all the 'good pairs' you've counted. This is your final answer.

Code Implementation

def number_of_good_pairs_brute_force(numbers):
    number_of_pairs = 0

    # Iterate through each number in the list
    for first_index in range(len(numbers)):

        # For each number, compare it with all subsequent numbers
        for second_index in range(first_index + 1, len(numbers)):

            # Check if the numbers at both indices are equal
            if numbers[first_index] == numbers[second_index]:

                # Increment the counter if a good pair is found
                number_of_pairs += 1

    return number_of_pairs

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through the array of n elements. For each element, it compares it with all other elements in the array to find matching pairs. This results in a nested loop structure where for each of the n elements, we potentially perform n comparisons. The total number of comparisons is therefore proportional to n multiplied by n, or n*n. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force approach only iterates through the input list using nested loops and compares elements. It doesn't use any auxiliary data structures such as lists, hashmaps, or recursion. The only extra memory used is for a few integer variables to store the loop counters and the good pair count, which takes constant space regardless of the input size N, where N is the number of elements in the list. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The most efficient way to count these pairs avoids checking every single pair. It involves counting how many times each number appears, and then using a formula to calculate the number of good pairs based on those counts.

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the list.
For each unique number, use the formula n * (n - 1) / 2, where 'n' is the number of times that number appeared. This formula directly tells you how many good pairs that number makes with itself.
Add up the results from the formula for each unique number. The total sum is the number of good pairs in the list.

Code Implementation

def number_of_good_pairs(numbers):
    number_counts = {}
    for number in numbers:
        if number in number_counts:
            number_counts[number] += 1
        else:
            number_counts[number] = 1

    good_pairs_count = 0

    # Iterate through each unique number
    for number in number_counts:

        count = number_counts[number]

        # Apply formula to calculate good pairs for the number.
        good_pairs_count += count * (count - 1) // 2

    return good_pairs_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm first counts the frequency of each number in the input list of size n. This frequency counting iterates through the list once, taking O(n) time. Then, it iterates through the unique counts (at most n unique values), applying the formula n * (n - 1) / 2 to each. This second iteration is also bounded by n. The overall time complexity is therefore O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The primary space usage comes from counting the occurrences of each number in the input list. This requires a hash map (or similar data structure) where the keys are the unique numbers and the values are their counts. In the worst-case scenario, all N numbers in the input list are unique, resulting in a hash map storing N key-value pairs. Therefore, the auxiliary space required is proportional to N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately since no pairs can be formed.
Array with only one element	Return 0 as a pair requires at least two elements.
Array with all elements being identical	The solution should correctly calculate the number of pairs (n*(n-1)/2) in this scenario.
Array with a large number of elements (scalability)	Using a hash map (counting frequency) ensures O(n) time complexity, addressing scalability.
Array containing negative numbers, zeros, and positive numbers	The hash map based solution works regardless of the range or sign of numbers.
Array with very large integer values (potential overflow during counting)	Ensure the data type used for counting can accommodate large numbers of pairs (e.g., long in Java).
Array with a skewed distribution of values (some values appear many times)	The frequency counting approach will still correctly calculate the number of pairs based on each value's frequency.
Array containing duplicate 'good pairs' when using nested loops incorrectly.	The outer loop index must be less than the inner loop index (i < j) for correct pair identification.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `nums`?
Can the integers in `nums` be negative, zero, or only positive?
Are we expecting to handle very large integer values which could cause overflow issues?
If the input array is empty or null, what should I return?
Could the input array contain duplicate numbers, and if so, how should they be handled?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number in the list.
Compare it to every other number in the list, one by one.
If any of the numbers it's compared to are the same as the first number, count that as a 'good pair'.
Move on to the second number in the list.
Compare the second number to every other number in the list, just like we did with the first number.
Again, if any of the numbers it's compared to are the same as the second number, count that as a 'good pair'.
Keep doing this for every number in the list.
Once you've gone through every number and compared it to all the others, add up all the 'good pairs' you've counted. This is your final answer.

Code Implementation

def number_of_good_pairs_brute_force(numbers):
    number_of_pairs = 0

    # Iterate through each number in the list
    for first_index in range(len(numbers)):

        # For each number, compare it with all subsequent numbers
        for second_index in range(first_index + 1, len(numbers)):

            # Check if the numbers at both indices are equal
            if numbers[first_index] == numbers[second_index]:

                # Increment the counter if a good pair is found
                number_of_pairs += 1

    return number_of_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the list.
For each unique number, use the formula n * (n - 1) / 2, where 'n' is the number of times that number appeared. This formula directly tells you how many good pairs that number makes with itself.
Add up the results from the formula for each unique number. The total sum is the number of good pairs in the list.

Code Implementation

def number_of_good_pairs(numbers):
    number_counts = {}
    for number in numbers:
        if number in number_counts:
            number_counts[number] += 1
        else:
            number_counts[number] = 1

    good_pairs_count = 0

    # Iterate through each unique number
    for number in number_counts:

        count = number_counts[number]

        # Apply formula to calculate good pairs for the number.
        good_pairs_count += count * (count - 1) // 2

    return good_pairs_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately since no pairs can be formed.
Array with only one element	Return 0 as a pair requires at least two elements.
Array with all elements being identical	The solution should correctly calculate the number of pairs (n*(n-1)/2) in this scenario.
Array with a large number of elements (scalability)	Using a hash map (counting frequency) ensures O(n) time complexity, addressing scalability.
Array containing negative numbers, zeros, and positive numbers	The hash map based solution works regardless of the range or sign of numbers.
Array with very large integer values (potential overflow during counting)	Ensure the data type used for counting can accommodate large numbers of pairs (e.g., long in Java).
Array with a skewed distribution of values (some values appear many times)	The frequency counting approach will still correctly calculate the number of pairs based on each value's frequency.
Array containing duplicate 'good pairs' when using nested loops incorrectly.	The outer loop index must be less than the inner loop index (i < j) for correct pair identification.