Leetcode 2364: Count Number of Bad Pairs

Input: The input consists of a single 0-indexed integer array nums, where each element represents a number in the array.

Example: nums = [2, 5, 3, 6, 7]

Constraints:

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9

Output: The output should be a single integer, representing the total number of bad pairs in the array nums.

Example: Output: 4

Constraints:

Goal: We need to count the number of pairs (i, j) such that i < j and j - i is not equal to nums[j] - nums[i].

Steps:

• We can use a hashmap to keep track of the differences between indices and the corresponding values in the array.

• For each index i, calculate the difference j - nums[j] and use the hashmap to count how many times that difference has occurred for previous indices.

• Accumulate the count of bad pairs based on the differences.

Goal: Constraints ensure the number of elements and their values are within acceptable limits.

Steps:

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9

Assumptions:

• The array contains at least one element.

• Input: Input: nums = [2, 5, 3, 6, 7]

• Explanation: For the given array, the bad pairs are the pairs of indices (i, j) where i < j, and the condition j - i != nums[j] - nums[i] holds. The total bad pairs in this example are 4.

Approach: The approach to solving this problem involves using a hashmap to track the difference between indices and their respective values efficiently.

Observations:

• To determine if a pair is bad, we need to check the difference between indices and their corresponding values.

• Using a hashmap will allow us to efficiently track and calculate the number of bad pairs.

• A hashmap will allow for constant time lookup and update, which will help in counting the bad pairs efficiently.

Steps:

• Initialize a hashmap to store the difference (index - value) as the key and the count as the value.

• Iterate over the array and for each element, check if the current difference exists in the hashmap.

• If it does, increment the count of bad pairs.

• Finally, return the total count of bad pairs.

Empty Inputs:

• The problem guarantees that the input array will have at least one element, so no need to handle empty arrays.

Large Inputs:

• The solution should be efficient enough to handle arrays of size up to 100,000.

Special Values:

• If all the elements are the same, there will be no bad pairs, as the condition will always hold.

Constraints:

• Ensure the solution runs in O(n) time to handle large inputs within the constraints.

long long countBadPairs(vector<int>& nums, long cnt = 0) {
    unordered_map<int,int> mp;
    for(int i = 0; i < nums.size(); i++)
        cnt += i - mp[i - nums[i]]++;
    return cnt;
}

1 : Function Declaration

long long countBadPairs(vector<int>& nums, long cnt = 0) {

This is the function declaration. It initializes a variable 'cnt' to count the bad pairs.

2 : Variable Initialization

    unordered_map<int,int> mp;

This line declares an unordered map 'mp' to store the frequency of the differences between elements in the vector and their indices.

3 : Loop Start

    for(int i = 0; i < nums.size(); i++)

This starts a loop over all elements in the 'nums' vector. The loop index 'i' iterates through the elements.

4 : Count Calculation

        cnt += i - mp[i - nums[i]]++;

This line updates the 'cnt' by calculating the number of bad pairs for each index 'i'. It uses the unordered map to find how many times the difference (i - nums[i]) has occurred previously.

5 : Return Statement

    return cnt;

This returns the final count of bad pairs after iterating over all elements in the 'nums' vector.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the length of the input array, as we are iterating over the array once and performing constant-time operations for each element.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n), as we are storing differences in a hashmap, which requires space proportional to the number of unique differences.

Leetcode 2364: Count Number of Bad Pairs

Explore →