Count Number of Bad Pairs
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.
Examples:
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.
Input: nums = [1, 2, 3, 4, 5]
Output: 0
Explanation: There are no bad pairs.
Constraints:
1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹
Brute Force Approach
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
For every index i, we need to find an index j such that j > i and j - i ≠ nums[j] - nums[i].
To do this, we will simply check all the index j greater than i. If the condition j - i ≠ nums[j] - nums[i] is satisfied, we will increase the count. At the end, we will return the total count of all such pairs.
Easy, right?
Let's walk through an example:
Let’s perform a dry run for nums = [4, 1, 3, 3]:
Count = 0 (to track bad pairs)
Let's iterate over the array
- Index i = 0:
- j = 1: 1 - 0 ≠ 1 - 4 → bad pair, Count = 1
- j = 2: 2 - 0 ≠ 3 - 4 → bad pair, Count = 2
- j = 3: 3 - 0 ≠ 3 - 4 → bad pair, Count = 3
- Index i = 1:
- j = 2: 2 - 1 ≠ 3 - 1 → bad pair, Count = 4
- j = 3: 3 - 1 = 3 - 1 → good pair
- Index i = 2: j = 3: 3 - 2 ≠ 3 - 3 → bad pair, Count = 5
- Index i = 3: no greater index
Result: Total bad pairs = 5
How to implement it in code:
To implement the brute force approach, follow these steps in code:
- Initialize a variable count of type long long to store the number of bad pairs.
- Get the size of the input array nums into a variable n.
- Use a nested loop:
- Outer loop:
- Iterate over index i from 0 to n - 1.
- Inner loop:
- Iterate over index j from i + 1 to n - 1.
- For each pair (i, j), check the condition:
- If j - i ≠ nums[j] - nums[i], increment the count.
- Return the count as the final result.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
long long countBadPairs(vector<int>& nums) {
// Get the size of the input array
int n = nums.size();
// Initialize count to 0 to store the number of bad pairs
long long count = 0;
// Outer loop: Iterate over each index i from 0 to n-1
for(int i = 0; i < n; i++) {
// Inner loop: Iterate over each index j from i+1 to n-1
for(int j = i + 1; j < n; j++) {
// Check if the pair (i, j) is a bad pair
if(j - i != nums[j] - nums[i]) {
// If it's a bad pair, increment the count
count++;
}
}
}
// Return the total number of bad pairs
return count;
}
};2. Java Try on Compiler
class Solution {
public long countBadPairs(int[] nums) {
// Get the size of the input array
int n = nums.length;
// Initialize count to 0 to store the number of bad pairs
long count = 0;
// Outer loop: Iterate over each index i from 0 to n-1
for (int i = 0; i < n; i++) {
// Inner loop: Iterate over each index j from i+1 to n-1
for (int j = i + 1; j < n; j++) {
// Check if the pair (i, j) is a bad pair
if (j - i != nums[j] - nums[i]) {
// If it's a bad pair, increment the count
count++;
}
}
}
// Return the total number of bad pairs
return count;
}
}3. Python Try on Compiler
class Solution:
def countBadPairs(self, nums):
# Get the size of the input array
n = len(nums)
# Initialize count to 0 to store the number of bad pairs
count = 0
# Outer loop: Iterate over each index i from 0 to n-1
for i in range(n):
# Inner loop: Iterate over each index j from i+1 to n-1
for j in range(i + 1, n):
# Check if the pair (i, j) is a bad pair
if j - i != nums[j] - nums[i]:
# If it's a bad pair, increment the count
count += 1
# Return the total number of bad pairs
return count
4. Javascript Try on Compiler
/**
* @param {number[]} nums
* @return {number}
*/
var countBadPairs = function (nums) {
// Get the size of the input array
let n = nums.length;
// Initialize count to 0 to store the number of bad pairs
let count = 0;
// Outer loop: Iterate over each index i from 0 to n-1
for (let i = 0; i < n; i++) {
// Inner loop: Iterate over each index j from i+1 to n-1
for (let j = i + 1; j < n; j++) {
// Check if the pair (i, j) is a bad pair
if (j - i !== nums[j] - nums[i]) {
// If it's a bad pair, increment the count
count++;
}
}
}
// Return the total number of bad pairs
return count;
};Time Complexity: O(n²)
This approach runs two nested loops to find all subarrays, one inside another, where the outer loop runs n times
(i.e. i ranges from 0 to n), and for each iteration of the outer loop, the inner loop(i.e. j ranges from i to n) also runs n-i times.
Analyzing the Loops:
Outer Loop (indexed by i):
It runs from 0 to n-1. So, it iterates n times.
Inner Loop (indexed by j):
For each fixed i, j runs from i+1 to n-1.
When i = 0, j runs n-1 times.
When i = 1, j runs n-2 times.
When i = 2, j runs n-3 times.
…
When i = n-1, j runs 0 time.
Total Iterations:
To find the total number of iterations of the inner loop across all iterations of the outer loop,
we sum up the iterations for each value of i: ∑(i=0 to n−1) (n−i)
This is the sum of an arithmetic series: (n−1)+(n−2)+…+1+0.
If we closely observe and reverse the series
we get 1 + 2 + 3 + … + (n-2) + (n-1) .
That is nothing but the sum of n-1 terms.
So the sum of n numbers from 1 to n is (n*(n+1))/2.
Thus, the total number of operations is ((n-1)*(n))/2.
Simplifying to Big-O Notation:
In Big-O notation, we focus on the term that grows the fastest as n increases, and we ignore constant factors and lower-order terms.
Therefore: O((n*(n-1))/2) ≈ O(n²)
Conclusion: The time complexity of the given code is O(n²).
This is because the nested loops result in a quadratic number of total operations, which dominate the runtime as the input size n becomes large.
Space Complexity: O(n)
Auxiliary Space Complexity: O(1)
We only use a few variables like n (the size of the input array), count (to store the number of bad pairs), and the loop variables i and j.
These variables take constant space, O(1), as they do not depend on the size of the input array.
Therefore, auxiliary space complexity is O(1).
Total Space Complexity: O(n)
The input array nums is given, which requires O(n) space.
Adding this to the auxiliary space gives: Total Space Complexity = O(n)
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), which is not suitable for n ≤ 10⁵. This means that for each test case, where the size of the array is at most 10⁵, the solution might not execute within the given time limits.
Since O(n²) results in a maximum of 10¹⁰ operations (for n = 10⁵), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁵, the solution with 10¹⁰ operations is not efficient enough.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10¹⁰ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(n²) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases.
Can we optimize it?
Yes! There is a better approach to solve this problem.
Curious?
In the previous approach, we checked for all index i whether an index j, which is greater than i, exists such that j - i ≠ nums[j] - nums[i]. However, this approach took O(n²) time, which is not feasible for larger inputs. But this can be optimized. Let's see how.
We need to check whether an index j exists for i such that j > i and j - i ≠ nums[j] - nums[i]. Let's rearrange this equation:
nums[i] − i ≠ nums[j] − j
This means, for an index j, we need to find an index i such that nums[i] - i doesn't equal nums[j] - j, right?
But how can we do this in an optimized way?
What if we store all nums[i] - i values, and when we encounter an index j, we can simply check if we have any value stored equal to nums[j] - j?
If yes, then there will be a good pair between (i, j).
Yes! But wait, this will give us the good pairs, as we will find that nums[j] - j = nums[i] - i. However, we need to find the number of bad pairs, not good pairs.
Okay, that's easy. How many pairs can an array of size n form?
For any given array of size n, we can form pairs by choosing two distinct indices from the array. The number of ways to choose 2 distinct indices from n indices is given by the combination formula: ⁿC₂ = n * (n−1)/2
This formula calculates the number of ways to select 2 items (in this case, indices) from a set of n items, where the order does not matter. The division by 2 accounts for the fact that the order of the selected indices does not matter (i.e., the pair (i, j) is the same as (j, i)).
So, the total number of pairs that can be formed from an array of size n is n * (n - 1) / 2.
There can be two types of pairs: good pairs and bad pairs.
Thus, we have:
Total pairs = Good pairs + Bad pairs
What if I subtract the number of good pairs from this value?
What will I get?
The number of bad pairs, right?
This is the optimized approach!
How can we do it?
We can optimize the solution by iterating over the array and calculating the value nums[j] - j for each index j. This value is our "target."
Now, instead of checking all previous indices i for each j, we can store these values in a hashmap (or dictionary) to make it easy and fast to look up.
Here’s how we do it:
- Iterate over the array: For each index j, calculate the value nums[j] - j (this is our target).
- Check the hashmap: Before storing the target value, we check if it already exists in the hashmap.
- If it does, it means we already encountered some index i before j where nums[i] - i equals the target. In this case, we add the number of times this target has appeared in the hashmap to our count (since each occurrence of the target corresponds to a good pair).
- Update the hashmap: After checking, we increase the count of the target value in the hashmap. This step ensures that future indices can use this target for lookup.
- Find the total number of pairs: The total number of pairs that can be formed in an array of size n is given by the formula n * (n - 1) / 2. This represents all possible pairs of indices (i, j) where i < j.
- Subtract the good pairs from total pairs: After calculating the good pairs using the hashmap, the number of bad pairs can be found by subtracting the count of good pairs from the total number of pairs. So, the final result will be:
Bad pairs = Total pairs − Good pairs
This approach significantly reduces the time complexity by using a hashmap for fast lookups, making it much more efficient than the brute force solution.
Let's understand with an example:
Let's do a dry run of this optimized approach on the example nums = [4, 1, 3, 3].
- count = 0 (this will store the number of good pairs)
- map = {} (hashmap to store occurrences of nums[i] - i)
- Total number of pairs: 4 * 3 / 2 = 6 (calculated using n * (n-1) / 2)
Iteration through the array:
Index j = 0:
- Target = nums[0] - 0 = 4 - 0 = 4
- Check hashmap: map does not contain 4, so no good pairs yet.
- Update hashmap: map[4] = 1
Index j = 1:
- Target = nums[1] - 1 = 1 - 1 = 0
- Check hashmap: map does not contain 0, so no good pairs yet.
- Update hashmap: map[0] = 1
Index j = 2:
- Target = nums[2] - 2 = 3 - 2 = 1
- Check hashmap: map does not contain 1, so no good pairs yet.
- Update hashmap: map[1] = 1
Index j = 3:
- Target = nums[3] - 3 = 3 - 3 = 0
- Check hashmap: map contains 0 (from j = 1), so we have 1 good pair.
- Increment count by 1 (good pairs count becomes 1).
- Update hashmap: map[0] = 2
Total Good Pairs: 1
Total Pairs: 6 (calculated as n * (n - 1) / 2 = 4 * 3 / 2 = 6)
Bad pairs = Total pairs − Good pairs = 6 − 1 = 5
Result: 5 bad pairs.
How to code it up?
- Initialize count and map.
- Loop through the array:
- Calculate the target for each index i.
- Check if the target is present in the hashmap.
- Add the count of good pairs to count.
- Update the hashmap with the current target.
- Calculate total pairs.
- Return the difference between total pairs and good pairs as the number of bad pairs.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
long long countBadPairs(vector<int>& nums) {
// Get the size of the input array
int n = nums.size();
// Create a hashmap to store frequencies of nums[i] - i
unordered_map<int, int> mp;
// Initialize count to store the number of good pairs
long long count = 0;
// Iterate over each index i in the array
for(int i = 0; i < n; i++) {
// Calculate the target value for the current index i
int target = nums[i] - i;
// Check if the target value has appeared before in the hashmap (good pair)
if(mp.find(target) != mp.end()) {
// If found, add the frequency of the target to count
count += mp[target];
}
// Update the hashmap to include the current target value
mp[target]++;
}
// Calculate the total number of pairs in the array: nC2 = n * (n - 1) / 2
// Subtract the number of good pairs from the total pairs to get the number of bad pairs
return (1LL * n * (n - 1) / 2) - count;
}
};2. Java Try on Compiler
import java.util.HashMap;
public class Solution {
public long countBadPairs(int[] nums) {
// Get the size of the input array
int n = nums.length;
// Create a hashmap to store frequencies of nums[i] - i
HashMap<Integer, Integer> mp = new HashMap<>();
// Initialize count to store the number of good pairs
long count = 0;
// Iterate over each index i in the array
for (int i = 0; i < n; i++) {
// Calculate the target value for the current index i
int target = nums[i] - i;
// Check if the target value has appeared before in the hashmap (good pair)
if (mp.containsKey(target)) {
// If found, add the frequency of the target to count
count += mp.get(target);
}
// Update the hashmap to include the current target value
mp.put(target, mp.getOrDefault(target, 0) + 1);
}
// Calculate the total number of pairs in the array: nC2 = n * (n - 1) / 2
// Subtract the number of good pairs from the total pairs to get the number of bad pairs
return (long) n * (n - 1) / 2 - count;
}
}3. Python Try on Compiler
from collections import defaultdict
class Solution:
def countBadPairs(self, nums):
# Get the size of the input array
n = len(nums)
# Create a hashmap to store frequencies of nums[i] - i
mp = defaultdict(int)
# Initialize count to store the number of good pairs
count = 0
# Iterate over each index i in the array
for i in range(n):
# Calculate the target value for the current index i
target = nums[i] - i
# Check if the target value has appeared before in the hashmap (good pair)
if target in mp:
# If found, add the frequency of the target to count
count += mp[target]
# Update the hashmap to include the current target value
mp[target] += 1
# Calculate the total number of pairs in the array: nC2 = n * (n - 1) / 2
# Subtract the number of good pairs from the total pairs to get the number of bad pairs
return (n * (n - 1)) // 2 - count
4. Javascript Try on Compiler
var countBadPairs = function(nums) {
// Get the size of the input array
let n = nums.length;
// Create a hashmap to store frequencies of nums[i] - i
let mp = new Map();
// Initialize count to store the number of good pairs
let count = 0;
// Iterate over each index i in the array
for (let i = 0; i < n; i++) {
// Calculate the target value for the current index i
let target = nums[i] - i;
// Check if the target value has appeared before in the hashmap (good pair)
if (mp.has(target)) {
// If found, add the frequency of the target to count
count += mp.get(target);
}
// Update the hashmap to include the current target value
mp.set(target, (mp.get(target) || 0) + 1);
}
// Calculate the total number of pairs in the array: nC2 = n * (n - 1) / 2
// Subtract the number of good pairs from the total pairs to get the number of bad pairs
return (n * (n - 1)) / 2 - count;
};Time Complexity: O(n)
We iterate over the entire array exactly once, so this step takes O(n) time, where n is the length of the array nums.
- Finding the target value in the hashmap and updating the hashmap both take O(1) time on average. Hashmap lookups and updates are constant-time operations.
- Calculating the total number of bad pairs by subtracting the number of good pairs from the total pairs takes O(1) time.
Hence, the total time complexity of the code is O(n).
Space Complexity: O(n)
- Auxiliary Space Complexity: O(n)
We are using a hashmap (mp) to store the frequency of nums[i] - i values. In the worst case, each nums[i] - i could be distinct, so the hashmap could store up to n unique values.
Thus, the auxiliary space is O(n) due to the hashmap.
- Total Space Complexity: O(n)
The input array nums already occupies O(n) space.
Thus, the total space complexity is O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an array of integer nums and an integer k, return the total number of continuous subarrays whose sum equals k.
Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.
A good subarray is a subarray where:
- its length is at least two, and
- the sum of the elements of the subarray is a multiple of k.