Minimum Domino Rotations For Equal Row

Medium Arrays & Hashing Greedy Original on LeetCode

Reported atGoogle

Minimum Domino Rotations For Equal Row is a medium arrays & hashing problem solved with the greedy pattern. The best approach, optimal (only the first domino's faces), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every face value) up.

Problem

A row of dominoes is described by two arrays: tops[i] and bottoms[i] are the numbers (from 1 to 6) on the upper and lower half of the i-th domino. In one rotation you may flip a single domino, swapping its top and bottom values.

Return the minimum number of rotations needed so that all values in tops are equal, or all values in bottoms are equal. If neither can be achieved, return -1.

Examples

Example 1

Input
tops = [3, 1, 3, 3, 2], bottoms = [1, 3, 4, 3, 3]
Output
2
Why
Every domino shows a 3 on some side. Flipping dominoes 1 and 4 makes the top row all 3s.

Example 2

Input
tops = [1, 2, 3], bottoms = [2, 3, 1]
Output
-1
Why
No single value appears on every domino, so no row can be made uniform.

Example 3

Input
tops = [6, 6, 6], bottoms = [1, 6, 2]
Output
0
Why
The top row is already all 6s.

Constraints

  • 2 <= tops.length == bottoms.length <= 2 * 10^4
  • 1 <= tops[i], bottoms[i] <= 6

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every face value)O(6 · n)O(1)
Optimal (only the first domino's faces)O(n)O(1)

1Brute force (try every face value)

TimeO(6 · n)Six passes over the dominoes.
SpaceO(1)Only counters.

For each value 1..6, check whether every domino shows it on at least one side. If so, the cost of a uniform top row is the number of tops that differ from it, and similarly for the bottom row. Take the smallest cost over all feasible values.

  1. For v in 1..6: topFlips = 0, bottomFlips = 0, ok = true.
  2. For each domino i: if tops[i] != v and bottoms[i] != v, ok = false; else count tops[i] != v and bottoms[i] != v.
  3. If ok, best = min(best, topFlips, bottomFlips).
  4. Return best, or -1 if no value was feasible.
class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int n = tops.length;
        int best = Integer.MAX_VALUE;
        for (int v = 1; v <= 6; v++) {
            int topFlips = 0, bottomFlips = 0;
            boolean ok = true;
            for (int i = 0; i < n; i++) {
                if (tops[i] != v && bottoms[i] != v) {
                    ok = false;
                    break;
                }
                if (tops[i] != v) topFlips++;
                if (bottoms[i] != v) bottomFlips++;
            }
            if (ok) best = Math.min(best, Math.min(topFlips, bottomFlips));
        }
        return best == Integer.MAX_VALUE ? -1 : best;
    }
}

2Optimal (only the first domino's faces)

TimeO(n)At most two passes over the dominoes.
SpaceO(1)Only counters.

Whatever value fills a row must appear on the first domino, so the only candidates are tops[0] and bottoms[0]. Check each candidate with one pass, counting flips for both rows, and return the cheaper feasible result.

  1. Write check(v): one pass; return -1 if some domino lacks v, else min(tops != v, bottoms != v).
  2. a = check(tops[0]). If a != -1 return a. (If bottoms[0] also works, every domino holds both values, so its cost is the same.)
  3. Otherwise return check(bottoms[0]).
class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int a = check(tops[0], tops, bottoms);
        if (a != -1) return a;
        return check(bottoms[0], tops, bottoms);
    }

    private int check(int v, int[] tops, int[] bottoms) {
        int topFlips = 0, bottomFlips = 0;
        for (int i = 0; i < tops.length; i++) {
            if (tops[i] != v && bottoms[i] != v) return -1;
            if (tops[i] != v) topFlips++;
            if (bottoms[i] != v) bottomFlips++;
        }
        return Math.min(topFlips, bottomFlips);
    }
}

Edge cases to test

  • One row is already uniform (answer 0)
  • A domino with the same value on both halves never needs a flip
  • The value works but it is cheaper to fill the bottom row than the top row
  • No value is shared by all dominoes (answer -1)

Hints

Hint 1

Fix a target value v. If some domino has v on neither side, v is impossible. Otherwise count how many tops and how many bottoms are not v.

Hint 2

There are only six possible values, so trying all of them is already linear.

Hint 3

Even better: the target must appear on the first domino, so only tops[0] and bottoms[0] are worth checking.

FAQ

What is the best time complexity for Minimum Domino Rotations For Equal Row?

Optimal (only the first domino's faces) runs in O(n) time and O(1) extra space. At most two passes over the dominoes.

Which pattern does Minimum Domino Rotations For Equal Row use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.

Is there a brute force solution for Minimum Domino Rotations For Equal Row?

Yes. Brute force (try every face value) takes O(6 · n) time and O(1) space. For each value 1..6, check whether every domino shows it on at least one side.

Which edge cases should I test for Minimum Domino Rotations For Equal Row?

One row is already uniform (answer 0); A domino with the same value on both halves never needs a flip; The value works but it is cheaper to fill the bottom row than the top row; No value is shared by all dominoes (answer -1).