Thomas Ngo

Software Engineer

2 minute read

Problem Statement

leetcode problem link

Intuition

To solve the domino rotation problem, we need to determine if there’s a value that appears in every domino either on the top or the bottom, and then calculate the minimum number of rotations required to make all values in one row equal. The key insight is that only values between 1 and 6 (since domino faces range from 1 to 6) are candidates.

Approach

  1. Count Occurrences: Use two dictionaries to store indices where each value appears in the tops and bottoms.
  2. Find Valid Candidates: A value is a valid candidate if, when combining indices from both the top and bottom, we can cover all domino positions.
  3. Compute Minimum Rotations: For each valid candidate, calculate how many rotations are needed by subtracting the maximum count (either top or bottom) from the total number of dominoes.
  4. Return Result: Return the minimum number of rotations needed, or -1 if no valid candidate exists.

Complexity

  • Time complexity:
    \(O(n)\)
    We iterate through the dominoes a constant number of times.

  • Space complexity:
    \(O(n)\)
    We store the positions of each domino face in dictionaries.

Code

from collections import defaultdict

class Solution(object):
    def minDominoRotations(self, tops, bottoms):
        """
        :type tops: List[int]
        :type bottoms: List[int]
        :rtype: int
        """
        N = len(tops)
        tops_count = defaultdict(list)
        bottoms_count = defaultdict(list)
        for i, top in enumerate(tops):
            tops_count[top].append(i)
        for i, bottom in enumerate(bottoms):
            bottoms_count[bottom].append(i)

        valid_candidates = []
        for i in range(1, 7):
            if i in tops_count and i in bottoms_count:
                curr_set = set()
                for index in tops_count[i]:
                    curr_set.add(index)
                for index in bottoms_count[i]:
                    curr_set.add(index)
                if len(curr_set) == N:
                    valid_candidates.append(i)

        if not valid_candidates:
            return -1

        curr_max = 0
        for candidate in valid_candidates:
            top_count = len(tops_count[candidate])
            bottom_count = len(bottoms_count[candidate])
            curr_max = max(top_count, bottom_count)

        return N - curr_max

Editorial

Approach 1: Greedy.

class Solution:
    def minDominoRotations(self, A: List[int], B: List[int]) -> int:
        def check(x):
            """
            Return min number of swaps
            if one could make all elements in A or B equal to x.
            Else return -1.
            """
            # how many rotations should be done
            # to have all elements in A equal to x
            # and to have all elements in B equal to x
            rotations_a = rotations_b = 0
            for i in range(n):
                # rotations couldn't be done
                if A[i] != x and B[i] != x:
                    return -1
                # A[i] != x and B[i] == x
                elif A[i] != x:
                    rotations_a += 1
                # A[i] == x and B[i] != x
                elif B[i] != x:
                    rotations_b += 1
            # min number of rotations to have all
            # elements equal to x in A or B
            return min(rotations_a, rotations_b)

        n = len(A)
        rotations = check(A[0])
        # If one could make all elements in A or B equal to A[0]
        if rotations != -1 or A[0] == B[0]:
            return rotations
        # If one could make all elements in A or B equal to B[0]
        else:
            return check(B[0])

You may also enjoy