2364. Count Number of Bad Pairs
Problem Description
In this problem, you are provided with an integer array called nums
, where the array is indexed starting from 0
. You must identify all pairs of indices (i, j)
that qualify as a "bad pair". A pair is designated as a bad pair if it satisfies two conditions:
i < j
(the indexi
comes before indexj
)j - i
is not equal tonums[j] - nums[i]
This means that the relative difference between the indices should equal the relative difference between their respective elements for it to be a good pair; otherwise, it is considered bad.
Your task is to calculate and return the total count of bad pairs in the nums
array.
Intuition
The brute-force approach would be to check all possible pairs (i, j)
where i < j
and count the number of pairs where j - i
does not equal nums[j] - nums[i]
. However, this approach has a time complexity of O(n^2) which would not be efficient for large arrays.
To optimize this, we can make a key observation: instead of focusing on whether a pair is bad, concentrate on finding the good pairs because they adhere to a specific pattern, namely j - i = nums[j] - nums[i]
. This can be rearranged to j - nums[j] = i - nums[i]
. If this property holds true for any two indices, they form a good pair. If it doesn't, they form a bad pair.
The intuition for the solution is to transform the problem such that we keep track of how many times we have seen the same difference (i - nums[i])
before. When we process the array, at each index i
, we calculate this difference and check it against a count tracker. For a new difference value at index i
, all previous occurrences of this value (the count tracked so far) represent the number of good pairs with the new index i
. Hence, bad pairs can be determined by subtracting the number of good pairs at each step from the total number of pairs seen so far.
The Counter dictionary in the solution keeps track of how many times we have seen each difference. For each new element x
at index i
, we increment the counter for i - x
which indicates we've seen another instance where this difference occurs. We then update the answer by adding i
(the total number of pairs with the current index so far) minus the count of this difference (the number of good pairs). The final answer reflects the total number of bad pairs.
This solution provides an efficient way to calculate the number of bad pairs with a time complexity of O(n), which is a significant improvement over the brute-force method.
Solution Approach
The implementation uses a hash map to track the counts of the differences. In Python, this is conveniently handled using the Counter
class from the collections module. The Counter
works like a standard dictionary but is specialized for counting objects. It has methods that make it easy to increment counts for each object.
The key step in the algorithm is to iterate over the array nums
while using the enumerate
function that provides both the index i
and the value x
. The difference i - x
is the transformed value we are interested in. Here's how the algorithm proceeds:
-
Initialize a
Counter
objectcnt
that will track the counts of differences. -
Initialize
ans
to 0, which will keep track of the number of bad pairs. -
Loop through the
nums
array using anenumerate
loop to get both the indexi
and the valuex
at that index. -
For each element, the difference
i - x
is calculated, which will be used to determine if a pair is good.ans
is incremented byi - cnt[i - x]
, which represents the number of bad pairs up to the current indexi
. This is calculated by subtracting the number of good pairs (tracked bycnt[i - x]
) from the total number of pairs that could have been formed with all the previous elements (given byi
).
-
The count for the current difference
i - x
is incremented incnt
to record that we have seen another instance where this difference occurs. -
After the loop ends,
ans
contains the total count of bad pairs, which is returned.
The reason why this approach works is due to the transformation of the problem into a more manageable counting problem. By tracking the occurrence of the differences, we avoid directly comparing every possible pair, which results in a much more efficient algorithm.
The key components of the implementation are:
- Enumeration: Providing both the index and the value to easily calculate our necessary difference.
- Hash Map (
Counter
): For efficient storage and retrieval of counts associated with each difference. This allows us to efficiently keep track of the number of good pairs per difference. - Transformation: Condensing the condition from
j - i != nums[j] - nums[i]
toi - nums[i]
, making it easier to track and count through a hash map.
By utilizing these components, we achieve a linear time solution, which is optimal for this problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Consider the nums
array as [1, 2, 3, 5]
. We want to find all bad pairs where i < j
and j - i
is not equal to nums[j] - nums[i]
.
First, we initialize a Counter
object cnt
and a variable ans
to count the bad pairs, starting with ans
set to 0.
Now, we start iterating through the array with indices and values:
- At
i = 0
,x = 1
, the differencei - x
is-1
. This difference hasn't been seen before, socnt[-1]
is 0. We updateans
with0 - 0 = 0
, and incrementcnt[-1]
. - At
i = 1
,x = 2
, the differencei - x
is-1
again. Now,cnt[-1]
is 1 (from the previous count). We updateans
with1 - 1 = 0
, but we already have0
bad pairs. Thus,ans
stays as0
, and we incrementcnt[-1]
to 2. - At
i = 2
,x = 3
, the differencei - x
is-1
yet again.cnt[-1]
is now 2. We updateans
with2 - 2 = 0
, and the number of bad pairsans
stays at0
. We incrementcnt[-1]
to 3. - At
i = 3
,x = 5
, the differencei - x
is-2
. This is a new difference, socnt[-2]
is 0. We updateans
with3 - 0 = 3
, indicating that up to this index, we have 3 bad pairs. We incrementcnt[-2]
.
By the end of the loop, we have counted ans = 3
bad pairs. To confirm, we can check the conditions for each pair:
(0, 1): 1 - 0 = 2 - 1
(Good pair)(0, 2): 2 - 0 = 3 - 1
(Good pair)(0, 3): 3 - 0 ā 5 - 1
(Bad pair)(1, 2): 2 - 1 = 3 - 2
(Good pair)(1, 3): 3 - 1 ā 5 - 2
(Bad pair)(2, 3): 3 - 2 ā 5 - 3
(Bad pair)
There are indeed 3 bad pairs: (0, 3), (1, 3), (2, 3)
.
The counter at the end of processing will be { -1: 3, -2: 1 }
, reflecting the idea that negative counts corresponded to instances where a good pair did not occur, leading to bad pairs.
This example shows how the algorithm can effectively identify bad pairs by focusing on counting the occurrences of the i - nums[i]
and using that to quickly determine the number of bad pairs without comparing each pair directly.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def countBadPairs(self, nums: List[int]) -> int:
5 # Initialize a counter to keep track of occurrences of differences
6 difference_counter = Counter()
7
8 # Initialize the answer which will store the count of bad pairs
9 bad_pairs_count = 0
10
11 # Enumerate over nums to get index (i) and number (x)
12 for index, number in enumerate(nums):
13 # A pair (j, i) is bad if j < i and i - j != nums[i] - nums[j]
14 # which can be rewritten as i - nums[i] != j - nums[j]
15 # Thus, we count how many indexes do not have the same (index - number) as the current one
16 # The difference (index - number) serves as a key in the counter.
17 bad_pairs_count += index - difference_counter[index - number]
18
19 # Increment the count for this difference in the counter
20 difference_counter[index - number] += 1
21
22 # Return the total count of bad pairs
23 return bad_pairs_count
24```
25
26Please note that you will need to import `List` from `typing` module at the beginning of the code in order to type hint the `nums` parameter as `List[int]`. You should add the following line at the beginning with the other imports:
27
28```python
29from typing import List
30
1class Solution {
2
3 // The function 'countBadPairs' returns the number of 'bad pairs' in the array.
4 // A 'bad pair' (j, k) is defined as one where j < k and nums[j] - nums[k] != j - k.
5 public long countBadPairs(int[] nums) {
6 // This map is used to track the occurrence frequency of calculated values.
7 Map<Integer, Integer> countMap = new HashMap<>();
8 // Initialize 'badPairsCount' which will store the final count of bad pairs.
9 long badPairsCount = 0;
10
11 // Iterate through the array 'nums'.
12 for (int i = 0; i < nums.length; ++i) {
13 // Calculate 'difference' as the difference between the current index and the current element.
14 int difference = i - nums[i];
15
16 // Increment 'badPairsCount' by the number of indices processed minus the number of occurrences of 'difference.'
17 // If 'difference' has not been seen, 'getOrDefault' will return 0, meaning no good pairs have been skipped.
18 badPairsCount += i - countMap.getOrDefault(difference, 0);
19
20 // Update the count of 'difference' in the map for future reference.
21 // The 'merge' method is used to add 1 to the current count of 'difference' or to set it to 1 if not present.
22 countMap.merge(difference, 1, Integer::sum);
23 }
24
25 return badPairsCount; // Return the total count of bad pairs.
26 }
27}
28
1#include <unordered_map>
2#include <vector>
3
4class Solution {
5public:
6 // Function to count the number of 'bad' pairs in the array
7 // A pair (i, j) is considered 'bad' if i < j and j - i != nums[j] - nums[i]
8 long long countBadPairs(std::vector<int>& nums) {
9 std::unordered_map<int, int> count_map; // Map to store the frequency of difference values
10 long long bad_pairs_count = 0; // Initialize the count of bad pairs to 0
11
12 // Iterate over the elements in nums
13 for (int i = 0; i < nums.size(); ++i) {
14 int diff = i - nums[i]; // Calculate the difference between index and value
15
16 // The total number of pairs with elements before index i is i
17 // Subtract the count of the number of 'good' pairs (where the diff is the same)
18 bad_pairs_count += i - count_map[diff];
19
20 // Increment the count of the current difference in the map
21 ++count_map[diff];
22 }
23
24 // Return the final count of bad pairs
25 return bad_pairs_count;
26 }
27};
28
1// Function to count the number of bad pairs in an array.
2// Pairs (i, j) are considered bad if i < j and j - i != nums[j] - nums[i].
3function countBadPairs(nums: number[]): number {
4 // Map to keep track of the number of occurrences of the difference between index and value.
5 const countMap = new Map<number, number>();
6 // Initialize the count of bad pairs.
7 let badPairsCount = 0;
8
9 // Iterate through the array elements.
10 for (let i = 0; i < nums.length; ++i) {
11 // Calculate the difference between the current index and the value at that index.
12 const diff = i - nums[i];
13 // The number of good pairs so far with the same difference is subtracted from the total pairs so far.
14 // This gives the number of bad pairs involving the current element.
15 badPairsCount += i - (countMap.get(diff) ?? 0);
16 // Update the count of good pairs with the current difference in the map.
17 countMap.set(diff, (countMap.get(diff) ?? 0) + 1);
18 }
19
20 // Return the total count of bad pairs.
21 return badPairsCount;
22}
23
Time and Space Complexity
The time complexity of the given code is O(n)
, where n
is the length of the nums
array. The reason for this is that the code uses a single loop that iterates through all elements of nums
, performing a constant amount of work within each iteration. The cnt
Counter dictionary lookup and update operations are O(1)
on average, so they don't change the overall linear time complexity.
The space complexity of the code is also O(n)
because the cnt
Counter dictionary can potentially grow to have as many distinct keys as there are elements in nums
. In the worst case, each iteration introduces a new key-value pair into the cnt
dictionary.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time