Jobs

Interviews

Discussions

Count Number of Bad Pairs

Medium

Asked by:

4 views

Topics:

Arrays

You are given a 0-indexed integer array nums. A pair of indices (i, j) is a bad pair if i < j and j - i != nums[j] - nums[i].

Return the total number of bad pairs in nums.

Example 1:

Input: nums = [4,1,3,3]
Output: 5
Explanation: The pair (0, 1) is a bad pair since 1 - 0 != 1 - 4.
The pair (0, 2) is a bad pair since 2 - 0 != 3 - 4, 2 != -1.
The pair (0, 3) is a bad pair since 3 - 0 != 3 - 4, 3 != -1.
The pair (1, 2) is a bad pair since 2 - 1 != 3 - 1, 1 != 2.
The pair (2, 3) is a bad pair since 3 - 2 != 3 - 3, 1 != 0.
There are a total of 5 bad pairs, so we return 5.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 0
Explanation: There are no bad pairs.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Try coding it in LeetCode

Count Number of Bad Pairs

Medium

Asked by:

4 views

Topics:

Arrays

You are given a 0-indexed integer array nums. A pair of indices (i, j) is a bad pair if i < j and j - i != nums[j] - nums[i].

Return the total number of bad pairs in nums.

Example 1:

Input: nums = [4,1,3,3]
Output: 5
Explanation: The pair (0, 1) is a bad pair since 1 - 0 != 1 - 4.
The pair (0, 2) is a bad pair since 2 - 0 != 3 - 4, 2 != -1.
The pair (0, 3) is a bad pair since 3 - 0 != 3 - 4, 3 != -1.
The pair (1, 2) is a bad pair since 2 - 1 != 3 - 1, 1 != 2.
The pair (2, 3) is a bad pair since 3 - 2 != 3 - 3, 1 != 0.
There are a total of 5 bad pairs, so we return 5.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 0
Explanation: There are no bad pairs.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

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 that the numbers in the input array can take?
Can the input array be empty or null?
Are there any constraints on the size of the input array?
Can you define more precisely what constitutes a 'bad pair' regarding potential integer overflow if we are calculating differences?
If no 'bad pairs' exist, what should the function return?

Brute Force Solution

Approach

The brute force approach to finding bad pairs involves checking every possible pair of numbers to see if it fits the 'bad' criteria. We compare each number with every other number in the list to make sure we didn't miss any bad pairs.

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

Start with the first number in the list.
Compare this number to every other number that comes after it in the list.
For each comparison, determine if the pair is a 'bad pair' according to the given rule.
If the pair is bad, count it.
Move to the next number in the list and repeat the process, comparing it to all the numbers that come after it.
Keep doing this until you have gone through all the numbers in the list.
The final count is the total number of bad pairs.

Code Implementation

def count_number_bad_pairs_brute_force(numbers):
    bad_pair_count = 0

    # Iterate through all possible pairs
    for first_index in range(len(numbers)):

        # Compare the current number with all subsequent numbers
        for second_index in range(first_index + 1, len(numbers)):

            # This is the core logic to detect if the pair is bad
            if numbers[first_index] - numbers[second_index] != first_index - second_index:

                bad_pair_count += 1

    return bad_pair_count

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through the input list of n elements. For each element, it compares it with every subsequent element in the list to check for bad pairs. In the worst-case scenario, the outer loop runs n times, and the inner loop runs approximately n/2 times on average. Therefore, the total number of comparisons grows proportionally to n * n/2, which simplifies to O(n²).

Space Complexity

O(1) – The provided brute force approach iterates through the input list using index variables. It does not create any auxiliary data structures like arrays, hashmaps, or sets to store intermediate results. The only memory used consists of a few constant-size variables to track indices and the bad pair count, irrespective of the input size N (where N is the number of elements in the list). Therefore, the space complexity is constant.

Optimal Solution

Approach

The inefficient solution compares every pair, but that's slow. The optimal approach counts how many pairs are *not* bad, then subtracts that from the total number of possible pairs. This avoids unnecessary comparisons.

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

Figure out the total number of pairs there could possibly be in the list.
Go through the list and keep track of how many times each number appears, but only consider the numbers we've seen so far.
As we go through the list, for each number we encounter, check how many times a number 'like' it has appeared before. 'Like' in this case means the original list positions of the two numbers have the same difference as the numbers themselves.
The numbers that are 'like' each other are considered the 'good' pairs.
Add up all the 'good' pairs we found.
Subtract the number of 'good' pairs from the total possible number of pairs to find the number of 'bad' pairs.

Code Implementation

def count_bad_pairs(numbers):
    list_length = len(numbers)
    total_pairs = list_length * (list_length - 1) // 2

    good_pairs = 0
    previous_numbers = {}

    for index, number in enumerate(numbers):
        difference = number - index

        #Check if we've seen a 'like' number before.
        if difference in previous_numbers:
            good_pairs += previous_numbers[difference]

        # Update the count of the current difference.
        if difference in previous_numbers:
            previous_numbers[difference] += 1
        else:
            previous_numbers[difference] = 1

    # Calculate the number of bad pairs.
    return total_pairs - good_pairs

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list of size n once. Inside the loop, it performs constant-time operations: calculating the difference, checking for existing counts in a hash map (or similar data structure providing average O(1) lookup/insertion), and updating the count. Since the loop runs n times and each iteration takes constant time on average, the overall time complexity is O(n).

Space Complexity

O(N) – The provided solution involves keeping track of the count of each number encountered so far. This requires a data structure, such as a hash map or dictionary, to store the numbers and their frequencies. In the worst case, all N numbers in the input array are distinct, resulting in the hash map storing N key-value pairs. Therefore, the auxiliary space used by the algorithm scales linearly with the input size N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty array or null input	Return 0 if the input array is null or empty, as there are no pairs.
Array with only one element	Return 0, as a pair requires at least two elements.
Array with all identical elements	The solution should correctly calculate the number of bad pairs when all elements are the same, which will be n * (n - 1) / 2.
Array with a large number of elements (performance)	Use an efficient algorithm (e.g., using a HashMap or frequency counting) to avoid O(n^2) time complexity for large inputs.
Array contains very large numbers (potential overflow during calculations)	Use appropriate data types (e.g., long) to prevent integer overflow when calculating differences or performing other arithmetic operations.
Array with negative numbers	The solution should correctly handle negative numbers in the array.
Array with duplicate elements and bad pairs exist.	The counting method correctly identifies different indices i and j even if nums[i] == nums[j] so long as i < j isn't satisfied and handles the duplicates correctly.
Maximum array size limit reached	The solution should consider memory usage and potential out-of-memory errors when dealing with very large arrays; an iterative method with constant memory is preferable.

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 that the numbers in the input array can take?
Can the input array be empty or null?
Are there any constraints on the size of the input array?
Can you define more precisely what constitutes a 'bad pair' regarding potential integer overflow if we are calculating differences?
If no 'bad pairs' exist, what should the function return?

Brute Force Solution

Approach

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

Start with the first number in the list.
Compare this number to every other number that comes after it in the list.
For each comparison, determine if the pair is a 'bad pair' according to the given rule.
If the pair is bad, count it.
Move to the next number in the list and repeat the process, comparing it to all the numbers that come after it.
Keep doing this until you have gone through all the numbers in the list.
The final count is the total number of bad pairs.

Code Implementation

def count_number_bad_pairs_brute_force(numbers):
    bad_pair_count = 0

    # Iterate through all possible pairs
    for first_index in range(len(numbers)):

        # Compare the current number with all subsequent numbers
        for second_index in range(first_index + 1, len(numbers)):

            # This is the core logic to detect if the pair is bad
            if numbers[first_index] - numbers[second_index] != first_index - second_index:

                bad_pair_count += 1

    return bad_pair_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Figure out the total number of pairs there could possibly be in the list.
Go through the list and keep track of how many times each number appears, but only consider the numbers we've seen so far.
As we go through the list, for each number we encounter, check how many times a number 'like' it has appeared before. 'Like' in this case means the original list positions of the two numbers have the same difference as the numbers themselves.
The numbers that are 'like' each other are considered the 'good' pairs.
Add up all the 'good' pairs we found.
Subtract the number of 'good' pairs from the total possible number of pairs to find the number of 'bad' pairs.

Code Implementation

def count_bad_pairs(numbers):
    list_length = len(numbers)
    total_pairs = list_length * (list_length - 1) // 2

    good_pairs = 0
    previous_numbers = {}

    for index, number in enumerate(numbers):
        difference = number - index

        #Check if we've seen a 'like' number before.
        if difference in previous_numbers:
            good_pairs += previous_numbers[difference]

        # Update the count of the current difference.
        if difference in previous_numbers:
            previous_numbers[difference] += 1
        else:
            previous_numbers[difference] = 1

    # Calculate the number of bad pairs.
    return total_pairs - good_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array or null input	Return 0 if the input array is null or empty, as there are no pairs.
Array with only one element	Return 0, as a pair requires at least two elements.
Array with all identical elements	The solution should correctly calculate the number of bad pairs when all elements are the same, which will be n * (n - 1) / 2.
Array with a large number of elements (performance)	Use an efficient algorithm (e.g., using a HashMap or frequency counting) to avoid O(n^2) time complexity for large inputs.
Array contains very large numbers (potential overflow during calculations)	Use appropriate data types (e.g., long) to prevent integer overflow when calculating differences or performing other arithmetic operations.
Array with negative numbers	The solution should correctly handle negative numbers in the array.
Array with duplicate elements and bad pairs exist.	The counting method correctly identifies different indices i and j even if nums[i] == nums[j] so long as i < j isn't satisfied and handles the duplicates correctly.
Maximum array size limit reached	The solution should consider memory usage and potential out-of-memory errors when dealing with very large arrays; an iterative method with constant memory is preferable.