2364. Count Number of Bad Pairs LeetCode Solution

In this guide, you will get 2364. Count Number of Bad Pairs LeetCode Solution with the best time and space complexity. The solution to Count Number of Bad Pairs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Count Number of Bad Pairs solution in C++
  4. Count Number of Bad Pairs solution in Java
  5. Count Number of Bad Pairs solution in Python
  6. Additional Resources
2364. Count Number of Bad Pairs LeetCode Solution image

Problem Statement of Count Number of Bad Pairs

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 <= 105
1 <= nums[i] <= 109

See also  826. Most Profit Assigning Work LeetCode Solution

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

2364. Count Number of Bad Pairs LeetCode Solution in C++

class Solution {
 public:
  long long countBadPairs(vector<int>& nums) {
    long ans = 0;
    unordered_map<int, int> count;  // (nums[i] - i)

    for (int i = 0; i < nums.size(); ++i)
      //     count[nums[i] - i] := the number of good pairs
      // i - count[nums[i] - i] := the number of bad pairs
      ans += i - count[nums[i] - i]++;

    return ans;
  }
};
/* code provided by PROGIEZ */

2364. Count Number of Bad Pairs LeetCode Solution in Java

class Solution {
  public long countBadPairs(int[] nums) {
    long ans = 0;
    Map<Integer, Long> count = new HashMap<>(); // (nums[i] - i)

    for (int i = 0; i < nums.length; ++i) {
      //     count[nums[i] - i] := the number of good pairs
      // i - count[nums[i] - i] := the number of bad pairs
      ans += i - count.getOrDefault(nums[i] - i, 0L);
      count.merge(nums[i] - i, 1L, Long::sum);
    }

    return ans;
  }
}
// code provided by PROGIEZ

2364. Count Number of Bad Pairs LeetCode Solution in Python

class Solution:
  def countBadPairs(self, nums: list[int]) -> int:
    ans = 0
    count = collections.Counter()  # (nums[i] - i)

    for i, num in enumerate(nums):
      #     count[nums[i] - i] := the number of good pairs
      # i - count[nums[i] - i] := the number of bad pairs
      ans += i - count[num - i]
      count[num - i] += 1

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: