Count Number of Bad Pairs

MEDIUM

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.

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⁹

Approaches

Checkout 2 different approaches to solve Count Number of Bad Pairs. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

The most straightforward approach is to check every possible pair of indices (i, j) where i < j. For each pair, we directly evaluate the condition j - i != nums[j] - nums[i]. If the condition holds true, we increment a counter for bad pairs.

Algorithm

Initialize a counter badPairsCount to 0.
Get the length of the array, n.
Use a nested loop:
- The outer loop iterates i from 0 to n-2.
- The inner loop iterates j from i+1 to n-1.
Inside the inner loop, check the condition: if (j - i != nums[j] - nums[i]).
If the condition is true, increment badPairsCount.
After the loops complete, return badPairsCount.

This method uses a nested loop structure to generate all unique pairs of indices (i, j) with i < j. The outer loop runs from i = 0 to n-2, and the inner loop runs from j = i + 1 to n-1. Inside the inner loop, we perform the check j - i != nums[j] - nums[i]. A running counter, initialized to zero, is incremented each time we find such a 'bad pair'. The final value of this counter is the result. Note that the count can exceed the capacity of a 32-bit integer, so a long should be used for the counter.

class Solution {
    public long countBadPairs(int[] nums) {
        long badPairsCount = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // The condition for a bad pair
                if ((long)j - i != (long)nums[j] - nums[i]) {
                    badPairsCount++;
                }
            }
        }
        return badPairsCount;
    }
}

Complexity Analysis

Time Complexity: O(n^2), where n is the number of elements in `nums`. We use nested loops to check every possible pair `(i, j)` with `i < j`, which amounts to `n * (n - 1) / 2` checks.Space Complexity: O(1), as we only use a constant amount of extra space for loop variables and the counter.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space.

Cons:

Highly inefficient for the given constraints (n <= 10^5), leading to a Time Limit Exceeded (TLE) error on most platforms.

Code Solutions

Checking out 3 solutions in different languages for Count Number of Bad Pairs. Click on different languages to view the code.

class Solution {
public
  long countBadPairs(int[] nums) {
    Map<Integer, Integer> cnt = new HashMap<>();
    long ans = 0;
    for (int i = 0; i < nums.length; ++i) {
      int x = i - nums[i];
      ans += i - cnt.getOrDefault(x, 0);
      cnt.merge(x, 1, Integer : : sum);
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Count Number of Bad Pairs

Patterns:

MathCounting

Data Structures:

ArrayHash Table