Count Number of Bad Pairs

MediumArrayHash TableMathCounting

Solution

counter는 i - nums[i]의 개수를 저장
counter를 통해서, 올바른 pair의 개수를 저장
전체 pair의 개수는 (n * (n - 1)) / 2이므로, 전체 pair에서 올바른 pair의 개수를 제외

export function countBadPairs(nums: number[]): number {
  const n = nums.length;
  const totalPairs = (n * (n - 1)) / 2;
  const counter = new Map<number, number>();
 
  let validPairs = 0;
  for (let i = 0; i < n; i++) {
    const count = counter.get(i - nums[i]) ?? 0;
    counter.set(i - nums[i], count + 1);
    validPairs += count;
  }
  return totalPairs - validPairs;
}

Complexity

Time: $O(n)$
Space: $O(n)$

LeetCode

Count Number of Bad Pairs

https://leetcode.com/problems/count-number-of-bad-pairs