Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2364.html

2364. Count Number of Bad Pairs

• Difficulty: Medium.
• Related Topics: Array, Hash Table.
• Similar Questions: K-diff Pairs in an Array, Subarray Sums Divisible by K, Count Nice Pairs in an Array, Count Number of Pairs With Absolute Difference K, Count Equal and Divisible Pairs in an Array.

Problem

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

Solution (Java, C++, Python)

• Java
• Python
• C++
• Go
• TypeScript

• class Solution {
      public long countBadPairs(int[] nums) {
          HashMap<Integer, Integer> seen = new HashMap<>();
          long count = 0;
          for (int i = 0; i < nums.length; i++) {
              int diff = i - nums[i];
              if (seen.containsKey(diff)) {
                  count += (i - seen.get(diff));
              } else {
                  count += i;
              }
              seen.put(diff, seen.getOrDefault(diff, 0) + 1);
          }
          return count;
      }
  }
  
  ############
  
  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;
      }
  }
  

• class Solution:
      def countBadPairs(self, nums: List[int]) -> int:
          arr = [i - v for i, v in enumerate(nums)]
          cnt = Counter(arr)
          n = len(arr)
          return sum(v * (n - v) for v in cnt.values()) >> 1
  
  ############
  
  # 2364. Count Number of Bad Pairs
  # https://leetcode.com/problems/count-number-of-bad-pairs/
  
  class Solution:
      def countBadPairs(self, nums: List[int]) -> int:
          n = len(nums)
          total = n * (n - 1) // 2
          good = 0
          
          mp = defaultdict(int)
          # j - i != nums[j] - nums[i]
          # Bad = j - nums[j] != i - nums[i]
          
          for i, x in enumerate(nums):
              good += mp[x - i]
              mp[x - i] += 1
          
          return total - good
  
  

• class Solution {
  public:
      long long countBadPairs(vector<int>& nums) {
          unordered_map<int, int> cnt;
          long long ans = 0;
          for (int i = 0; i < nums.size(); ++i) {
              int x = i - nums[i];
              ans += i - cnt[x];
              ++cnt[x];
          }
          return ans;
      }
  };
  

• func countBadPairs(nums []int) (ans int64) {
  	cnt := map[int]int{}
  	for i, x := range nums {
  		x = i - x
  		ans += int64(i - cnt[x])
  		cnt[x]++
  	}
  	return
  }
  

• function countBadPairs(nums: number[]): number {
      const cnt = new Map<number, number>();
      let ans = 0;
      for (let i = 0; i < nums.length; ++i) {
          const x = i - nums[i];
          ans += i - (cnt.get(x) ?? 0);
          cnt.set(x, (cnt.get(x) ?? 0) + 1);
      }
      return ans;
  }
  
  

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

All Problems

All Solutions