We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Number of Bad Pairs

Number: 2448

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Given a 0-indexed integer array nums, a pair of indices (i, j) is called a bad pair if i < j and j - i != nums[j] - nums[i]. The task is to return the total number of bad pairs in nums.

Key Insights

  • Instead of directly counting bad pairs, count the total number of pairs and subtract the number of good pairs.
  • A good pair satisfies j - i == nums[j] - nums[i], which can be rearranged to nums[i] - i == nums[j] - j.
  • Use a hash table to count the frequency of each value of (nums[i] - i).
  • The number of good pairs for a particular key is c * (c - 1) / 2 if the frequency is c.
  • Total pairs can be calculated using the formula n * (n - 1) / 2, where n is the length of the array.

Space and Time Complexity

Time Complexity: O(n) because we iterate through the array once and perform O(1) operations inside the loop. Space Complexity: O(n) in the worst-case scenario where all (nums[i] - i) values are unique, storing counts for each index.

Solution

The solution involves two main steps:

  1. Calculate the total number of index pairs using the combinatorial formula.
  2. Use a hash table (or dictionary) to count the frequency of the value (nums[i] - i) for each index. For each key in the hash table, compute the number of good pairs using the formula (frequency * (frequency - 1) / 2) and subtract the sum of these counts from the total pairs to get the number of bad pairs. The key trick is to transform the condition for a good pair, leading to an efficient grouping based on the computed key.

Code Solutions

# Python solution for counting bad pairs

def count_bad_pairs(nums):
    # Calculate total pairs using the formula n * (n - 1) / 2
    n = len(nums)
    total_pairs = n * (n - 1) // 2
    
    # Dictionary to count frequency of the key (nums[i] - i)
    diff_count = {}
    for i, num in enumerate(nums):
        # Compute the key for the current index
        key = num - i
        # Increase count of this key by 1 (using dict.get for default 0)
        diff_count[key] = diff_count.get(key, 0) + 1

    # Calculate the total number of good pairs from the frequencies
    good_pairs = 0
    for count in diff_count.values():
        if count > 1:
            good_pairs += count * (count - 1) // 2

    # Bad pairs are total pairs minus good pairs
    return total_pairs - good_pairs

# Example usage:
nums = [4,1,3,3]
print(count_bad_pairs(nums))  # Expected output: 5
← Back to All Questions