Problem Statement in English

You’re given two integer arrays tops and bottoms, each of length n. Each element in these arrays represents a number on a domino. Your task is to find the minimum number of rotations needed to make all the numbers in either the tops or bottoms array equal.

Approach

To solve the problem, we can use a hashmap to count the occurrences of each number in both tops and bottoms.

The key idea is to check if a number appears in all positions of either tops or bottoms, and then calculate the minimum rotations needed to make all numbers equal.

Solution in Python


class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        hm = defaultdict(int)
        top = defaultdict(int)
        bottom = defaultdict(int)

        l = len(tops)

        for i in range(l):
            t,b = tops[i], bottoms[i]

            hm[t]+=1
            if t != b:
                hm[b]+=1

            top[t]+=1
            bottom[b]+=1

        res = float("inf")

        for k, v in hm.items():
            if v == l:
                res = min(res, l - bottom[k])
                res = min(res, l - top[k])

        return res if res != float("inf") else -1

Complexity

  • Time: $O(n)$
    Since we iterate through the tops and bottoms arrays once to populate the dictionaries, and then iterate through the keys of the hm dictionary, which can have at most $n$ unique keys.

  • Space: $O(n)$
    Since we use three dictionaries (hm, top, and bottom) to store counts of elements, the space complexity is linear with respect to the number of unique elements in the input arrays.

Mistakes I Made

I didn’t add the if condition to whilst upddating the hm dictionary, which caused incorrect results when the same number appeared in both tops and bottoms.

And we are done.