[Leetcode] 1128. Number of Equivalent Domino Pairs

https://leetcode.com/problems/number-of-equivalent-domino-pairs/description/?envType=daily-question&envId=2025-05-04

initial

really easy but i was trying to make a set my key for hashmap. U technically can with frozenset but it is easier to maybe use a sorted tuple as key

Also the number of ways to form pairs is n*(n-1)//2.

from collections import defaultdict
class Solution:
    def numEquivDominoPairs(self, dom: List[List[int]]) -> int:
        dic = defaultdict(int)
        for d in dom:
            check=set()
            for ele in d:
                check.add(ele)
            hola = frozenset(check)
            dic[hola]+=1
        print(dic)
        ans=0
        for hi in dic.values():
            if hi>1:
                ans+=hi*(hi-1)//2
        return ans
            

sol

from collections import defaultdict

class Solution:
    def numEquivDominoPairs(self, dom: List[List[int]]) -> int:
        counts = defaultdict(int)
        for d in dom:
            # Create a sorted tuple as the key
            key = tuple(sorted(d))
            counts[key] += 1

        ans = 0
        for count in counts.values():
            if count > 1:
                ans += count * (count - 1) // 2
        return ans

complexity

o(n) for outer loop but we are sorting tuple which is n log n, where n is size of tuple. Since it is 2, 2 log 2 is just 1 so o(1) time.

we iterate through map's keys, which in worst case is m unique keys.

so overall time is o(n) cuz n>m.

space is o(m) where m is # of unique elements in map.