[LeetCode] 2364. Count Number of Bad Pairs (Python)

Problem

Solution

HashMap

i < j 이면서 j - i != nums[j] - nums[i] 인 bad pairs의 갯수를 리턴하는 문제.

• bad pair 정의 if i < j && j - i != nums[j] - nums[i]
• bad pair의 쌍 개수 구하기

관점을 바꿔서 i - nums[i] == j - nums[j] 인 good pairs를 구한 뒤 전체 - good pairs를 구한다.

즉, nums[i] - i 값이 동일한 숫자끼리 good pair가 된다.
그러므로, 특정 값 key = nums[i] - i를 기준으로 그룹을 만들고, 동일한 값이 등장할 때마다 good pair를 세면, 전체 쌍에서 빼서 bad pair를 구할 수 있다.

 

아래는 처음에 2중 for문으로 bruteforce로 풀었다가 time out 이 발생했던 코드..ㅠㅠ

# solve 1)
class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        def isBadPair(i: int, j: int, subtractedNum:int ) -> bool:
            if i < j and (j-i) != subtractedNum:
                return True
            return False

        answer = 0
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if isBadPair(i, j, nums[j] - nums[i]):
                    answer += 1

        return answer

# solve 2)
class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        answer = 0
        map = defaultdict(int)

        for i in range(len(nums)):
            map[i] = nums[i] - i

        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if map[i] != map[j]:
                    answer += 1
        return answer

Code

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        answer = 0
        map = defaultdict(int)
        n = len(nums)
        totalPairs = n*(n-1)//2
        numGoodPairs = 0

        for i in range(len(nums)):
            subtractNum = nums[i] - i
            if subtractNum in map:
                map[subtractNum] += 1
            else:
                map[subtractNum] = 1
        
        for k, v in map.items():

            if v > 1:
                numGoodPairs += v*(v-1)//2

        return totalPairs - numGoodPairs

• 모든 pair 수에서 GoodPairs 수를 빼서 BadPairs 의 개수를 구한다.

 

<다른 풀이>

from collections import Counter
from typing import List

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        n = len(nums)
        total_pairs = n * (n - 1) // 2  # 전체 쌍 개수
        
        cnt = Counter()
        good_pairs = 0
        
        for i, x in enumerate(nums):
            key = x - i
            good_pairs += cnt[key]  # 현재까지 등장한 같은 (nums[i] - i) 개수만큼 good pair 추가
            cnt[key] += 1  # 현재 (nums[i] - i) 개수 증가
        
        return total_pairs - good_pairs  # bad pair 개수 = 전체 쌍 - good pair

 

Complexity

Time Complexity

nums 길이만큼 순회하므로 => O(N)

Space Complexity

• best case -> 모든 nums[i]-i 값이 동일한 경우 O(1)
• worst case -> 모든 nums[i]-i 값이 다른 경우 O(N)