Jobs

Interviews

Discussions

Find the Number of Good Pairs I

#248 Most AskedEasy

Find the Number of Good Pairs I #248 Most Asked

Easy

Google

8 views

Topics:

Arrays

You are given 2 integer arrays nums1 and nums2 of lengths n and m respectively. You are also given a positive integer k.

A pair (i, j) is called good if nums1[i] is divisible by nums2[j] * k (0 <= i <= n - 1, 0 <= j <= m - 1).

Return the total number of good pairs.

Example 1:

Input: nums1 = [1,3,4], nums2 = [1,3,4], k = 1

Output: 5

Explanation:

The 5 good pairs are (0, 0), (1, 0), (1, 1), (2, 0), and (2, 2).

Example 2:

Input: nums1 = [1,2,4,12], nums2 = [2,4], k = 3

Output: 2

Explanation:

The 2 good pairs are (3, 0) and (3, 1).

Constraints:

1 <= n, m <= 50
1 <= nums1[i], nums2[j] <= 50
1 <= k <= 50

Try coding it in LeetCode

Find the Number of Good Pairs I

#248 Most AskedEasy

Find the Number of Good Pairs I #248 Most Asked

Easy

Google

8 views

Topics:

Arrays

You are given 2 integer arrays nums1 and nums2 of lengths n and m respectively. You are also given a positive integer k.

A pair (i, j) is called good if nums1[i] is divisible by nums2[j] * k (0 <= i <= n - 1, 0 <= j <= m - 1).

Return the total number of good pairs.

Example 1:

Input: nums1 = [1,3,4], nums2 = [1,3,4], k = 1

Output: 5

Explanation:

The 5 good pairs are (0, 0), (1, 0), (1, 1), (2, 0), and (2, 2).

Example 2:

Input: nums1 = [1,2,4,12], nums2 = [2,4], k = 3

Output: 2

Explanation:

The 2 good pairs are (3, 0) and (3, 1).

Constraints:

1 <= n, m <= 50
1 <= nums1[i], nums2[j] <= 50
1 <= k <= 50

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 range of values within the input array?
Can the input array contain negative numbers or zero?
Are duplicate numbers allowed in the input array, and if so, do they contribute to the count of good pairs?
What should be returned if the input array is null or empty?
What is the maximum possible length of the input array?

Brute Force Solution

Approach

The most straightforward way to find the number of "good pairs" is to check every single possible pair of numbers. We compare each number with every other number in the group to see if they form a "good pair".

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

Take the first number in the collection.
Compare it to every other number in the collection, including itself.
If the two numbers are the same, count it as a "good pair".
Move on to the second number in the collection.
Compare it to every other number in the collection, including itself.
If the two numbers are the same, count it as a "good pair".
Repeat this process for each number in the collection.
Once you've gone through all the numbers, add up all the times you found a "good pair" to get the final count.

Code Implementation

def find_number_of_good_pairs_i(numbers):
    number_of_good_pairs = 0

    for first_index in range(len(numbers)):
        # Need to iterate through each number
        # to compare it to the others.

        for second_index in range(len(numbers)):
            # Compare each number with every other number.

            if numbers[first_index] == numbers[second_index]:
                # If a good pair is found, increment.
                number_of_good_pairs += 1

    # Divide by 2 to account for double counting.
    number_of_good_pairs = number_of_good_pairs // 2

    return number_of_good_pairs

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n numbers in the input. For each number, it compares it to all other n numbers in the input, including itself. Thus, for each of the n numbers, there are n comparisons. Therefore, the total number of operations is proportional to n * n, which simplifies to O(n²).

Space Complexity

O(1) – The provided algorithm iterates through all possible pairs within the input collection. It doesn't explicitly create any auxiliary data structures like arrays, hash maps, or sets to store intermediate results. It only uses a constant number of variables, likely loop counters and a variable to store the count of good pairs. Therefore, the auxiliary space used remains constant irrespective of the input size N (where N is the number of elements in the collection), resulting in O(1) space complexity.

Optimal Solution

Approach

The problem asks us to count pairs of numbers in a list that are equal. The best way to solve this is to count how many times each number appears, then use those counts to figure out how many good pairs each number creates.

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

First, count the occurrences of each unique number in the list.
For each unique number, determine how many pairs it can form. The number of pairs a number can form is calculated using a simple formula: (count * (count - 1)) / 2. This is because if you have 'count' instances of the same number, you can pick any two of them.
Add up the number of pairs from each unique number. The total sum will be the total number of 'good' pairs in the original list.

Code Implementation

def find_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

    total_good_pairs = 0

    # Iterate through the counts of each number.
    for number in number_counts:
        count = number_counts[number]

        # Calculate pairs for a number.
        if count > 1:
            number_of_pairs = (count * (count - 1)) // 2

            # Add the number of pairs to the total.
            total_good_pairs += number_of_pairs

    return total_good_pairs

Big(O) Analysis

Time Complexity

O(n) – The primary operation is counting the occurrences of each number in the input list of size n. This involves iterating through the list once. Calculating the number of pairs for each unique number then involves iterating through a hashmap of at most n unique numbers in the worst case (where all numbers are unique), or far less than n in the best cases. Therefore, the dominant factor in the time complexity is the initial linear scan of the list, making the overall time complexity O(n).

Space Complexity

O(N) – The algorithm counts the occurrences of each unique number in the list using a hash map (or dictionary). In the worst-case scenario, all N numbers in the input list are unique. Therefore, the hash map will store N key-value pairs, where each key is a unique number and each value is its count. This leads to an auxiliary space usage that grows linearly with the input size N. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no pairs can be formed.
Array with a single element	Return 0 as a pair requires at least two elements.
Array with all identical values	The algorithm should correctly count all pairs with identical indices.
Large input array size (close to maximum allowed)	The solution should have a time complexity that scales well, preferably O(n) or O(n log n) using appropriate data structures.
Input array containing negative numbers	The solution should handle negative numbers correctly without any modification.
Input array containing zero	The solution should not have any issues with zero values.
Array with a large number of duplicate elements	Using a hashmap can efficiently count duplicates and avoid quadratic time complexity.
Integer overflow in count of good pairs	Use a data type (e.g., long) that can accommodate a large number of pairs to avoid integer overflow.

Null or empty input array

How to Handle:

Return 0 immediately as no pairs can be formed.

Array with a single element

How to Handle:

Return 0 as a pair requires at least two elements.

Array with all identical values

How to Handle:

The algorithm should correctly count all pairs with identical indices.

Large input array size (close to maximum allowed)

How to Handle:

The solution should have a time complexity that scales well, preferably O(n) or O(n log n) using appropriate data structures.

Input array containing negative numbers

How to Handle:

The solution should handle negative numbers correctly without any modification.

Input array containing zero

How to Handle:

The solution should not have any issues with zero values.

Array with a large number of duplicate elements

How to Handle:

Using a hashmap can efficiently count duplicates and avoid quadratic time complexity.

Integer overflow in count of good pairs

How to Handle:

Use a data type (e.g., long) that can accommodate a large number of pairs to avoid integer overflow.

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 range of values within the input array?
Can the input array contain negative numbers or zero?
Are duplicate numbers allowed in the input array, and if so, do they contribute to the count of good pairs?
What should be returned if the input array is null or empty?
What is the maximum possible length of the input array?

Brute Force Solution

Approach

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

Take the first number in the collection.
Compare it to every other number in the collection, including itself.
If the two numbers are the same, count it as a "good pair".
Move on to the second number in the collection.
Compare it to every other number in the collection, including itself.
If the two numbers are the same, count it as a "good pair".
Repeat this process for each number in the collection.
Once you've gone through all the numbers, add up all the times you found a "good pair" to get the final count.

Code Implementation

def find_number_of_good_pairs_i(numbers):
    number_of_good_pairs = 0

    for first_index in range(len(numbers)):
        # Need to iterate through each number
        # to compare it to the others.

        for second_index in range(len(numbers)):
            # Compare each number with every other number.

            if numbers[first_index] == numbers[second_index]:
                # If a good pair is found, increment.
                number_of_good_pairs += 1

    # Divide by 2 to account for double counting.
    number_of_good_pairs = number_of_good_pairs // 2

    return number_of_good_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, count the occurrences of each unique number in the list.
For each unique number, determine how many pairs it can form. The number of pairs a number can form is calculated using a simple formula: (count * (count - 1)) / 2. This is because if you have 'count' instances of the same number, you can pick any two of them.
Add up the number of pairs from each unique number. The total sum will be the total number of 'good' pairs in the original list.

Code Implementation

def find_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

    total_good_pairs = 0

    # Iterate through the counts of each number.
    for number in number_counts:
        count = number_counts[number]

        # Calculate pairs for a number.
        if count > 1:
            number_of_pairs = (count * (count - 1)) // 2

            # Add the number of pairs to the total.
            total_good_pairs += number_of_pairs

    return total_good_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no pairs can be formed.
Array with a single element	Return 0 as a pair requires at least two elements.
Array with all identical values	The algorithm should correctly count all pairs with identical indices.
Large input array size (close to maximum allowed)	The solution should have a time complexity that scales well, preferably O(n) or O(n log n) using appropriate data structures.
Input array containing negative numbers	The solution should handle negative numbers correctly without any modification.
Input array containing zero	The solution should not have any issues with zero values.
Array with a large number of duplicate elements	Using a hashmap can efficiently count duplicates and avoid quadratic time complexity.
Integer overflow in count of good pairs	Use a data type (e.g., long) that can accommodate a large number of pairs to avoid integer overflow.

Null or empty input array

How to Handle:

Return 0 immediately as no pairs can be formed.

Array with a single element

How to Handle:

Return 0 as a pair requires at least two elements.

Array with all identical values

How to Handle:

The algorithm should correctly count all pairs with identical indices.

Large input array size (close to maximum allowed)

How to Handle:

The solution should have a time complexity that scales well, preferably O(n) or O(n log n) using appropriate data structures.

Input array containing negative numbers

How to Handle:

The solution should handle negative numbers correctly without any modification.

Input array containing zero

How to Handle:

The solution should not have any issues with zero values.

Array with a large number of duplicate elements

How to Handle:

Using a hashmap can efficiently count duplicates and avoid quadratic time complexity.

Integer overflow in count of good pairs

How to Handle:

Use a data type (e.g., long) that can accommodate a large number of pairs to avoid integer overflow.

0/1916 Google questions completed

0/1916 completed