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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Number of Bad Pairs

Difficulty: Medium

Problem Description

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.

Key Insights

  • A pair (i, j) is bad if the difference between indices j and i does not match the difference between the values nums[j] and nums[i].
  • The condition can be rewritten to check if (nums[j] - j) != (nums[i] - i).
  • This leads to the observation that all pairs with the same value of nums[k] - k are valid and not bad pairs.
  • Using a hash map (or dictionary) can help count occurrences of each unique value of nums[k] - k.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can iterate through the array nums and compute the value of nums[i] - i for each index i. We maintain a count of how many times each unique value appears using a hash map. The total number of pairs will be calculated using the formula for combinations, subtracting the number of valid pairs (those that share the same nums[i] - i value) from the total possible pairs.

Code Solutions

def countBadPairs(nums):
    from collections import defaultdict
    
    n = len(nums)
    total_pairs = n * (n - 1) // 2  # Total possible pairs
    count_map = defaultdict(int)
    
    for i in range(n):
        count_map[nums[i] - i] += 1  # Count occurrences of nums[i] - i
    
    valid_pairs = 0
    for count in count_map.values():
        if count > 1:
            valid_pairs += count * (count - 1) // 2  # Combinations of valid pairs
    
    return total_pairs - valid_pairs  # Bad pairs are total pairs minus valid pairs
← Back to All Questions