#2364

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Number of Bad Pairs

Count the number of bad pairs in an array where the difference between indices and values does not match.

Problem Statement

You are given a 0-indexed integer array nums. A pair of indices (i, j) is considered a bad pair if i < j and j - i is not equal to nums[j] - nums[i]. Your task is to return the total number of bad pairs in the array.

For example, given nums = [4,1,3,3], you should find the pairs where the condition j - i != nums[j] - nums[i] holds. The pairs that fit this criterion should be counted and returned.

Examples

Example 1

Input: nums = [4,1,3,3]

Output: 5

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

There are no bad pairs.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109

Solution Approach

Array Scanning Plus Hash Lookup

To solve this problem, we can scan through the array while maintaining a hash map to store previously seen values of the differences between the index and the value. This allows us to efficiently count non-bad pairs, and subtract them from the total possible pairs to find the number of bad pairs.

Mathematical Simplification

Instead of checking each pair individually, it's beneficial to use the fact that a non-bad pair satisfies the condition j - i = nums[j] - nums[i]. This transforms the problem into counting non-bad pairs and subtracting from the total number of pairs to find the bad ones.

Optimized Time Complexity

By using a hash table to store the computed differences as we iterate through the array, we can achieve an O(n) time complexity, making the solution efficient even for large input sizes. This approach avoids the need for a nested loop.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) because we scan the array once and perform constant-time operations with the hash table. The space complexity is O(n) due to the storage required for the hash table.

What Interviewers Usually Probe

Candidate's ability to recognize the connection between index and value differences.
Efficiency in counting bad pairs by leveraging hash tables.
Understanding of transforming a complex problem into a counting problem.

Common Pitfalls or Variants

Common pitfalls

Not recognizing the need for a hash table to track index-value differences.
Misunderstanding the problem by attempting to check each pair directly with nested loops, leading to O(n^2) complexity.
Overlooking the importance of transforming the problem to count non-bad pairs.

Follow-up variants

Handling larger arrays efficiently (up to length 10^5).
Adjusting the solution for arrays containing negative numbers or large values.
Finding the number of non-bad pairs instead of bad pairs.

FAQ

What is a bad pair in the "Count Number of Bad Pairs" problem?

A bad pair is a pair of indices (i, j) such that i < j and the condition j - i != nums[j] - nums[i] holds true.

How can I optimize the solution for the "Count Number of Bad Pairs" problem?

By using array scanning with a hash table to track the differences between the index and value, you can optimize the solution to run in O(n) time complexity.

What is the time complexity of the "Count Number of Bad Pairs" solution?

The solution runs in O(n) time complexity due to the efficient array scanning and hash table usage.

What is the key idea for solving the "Count Number of Bad Pairs" problem?

The key idea is to count non-bad pairs first by leveraging the condition j - i = nums[j] - nums[i] and subtracting from the total possible pairs.

How do hash tables help solve the "Count Number of Bad Pairs" problem?

Hash tables store previously seen differences between indices and values, allowing you to efficiently count pairs that satisfy the condition for non-bad pairs.

terminal

Solution

Solution 1: Equation Transformation + Hash Table

According to the problem description, for any $i \lt j$, if $j - i \neq \textit{nums}[j] - \textit{nums}[i]$, then $(i, j)$ is a bad pair.

1

2

3

4

5

6

7

8

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        cnt = Counter()
        ans = 0
        for i, x in enumerate(nums):
            ans += i - cnt[i - x]
            cnt[i - x] += 1
        return ans

Continue Practicing

#2442 count number of distinct integers after reverse operations #2001 number of pairs of interchangeable rectangles #1994 the number of good subsets