Minimum Domino Rotations For Equal Row

Medium
1131.

Minimum Domino Rotations For Equal Row

Minimum Domino Rotations For Equal Row is a medium coding problem on arrays and greedy, asked in Amazon, Google and Microsoft interviews.

A row of dominoes is laid out left to right. Domino i shows tops[i] on its top half and bottoms[i] on its bottom half; every half shows a number from 1 to 6.

A rotation flips one domino so its top and bottom values trade places.

Return the minimum number of rotations after which all top values are equal, or all bottom values are equal. If neither can be achieved, return -1.

Example 1

Input
tops = [3,1,3,3], bottoms = [1,3,4,5]
Output
1
Explanation
Rotating domino 1 makes the top row `[3,3,3,3]`.

Example 2

Input
tops = [2,5,1], bottoms = [6,2,4]
Output
-1
Explanation
No single value appears on every domino.

Example 3

Input
tops = [4,4], bottoms = [4,4]
Output
0

Constraints

  • 2 <= tops.length <= 2 * 10^4
  • bottoms.length == tops.length
  • 1 <= tops[i], bottoms[i] <= 6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} tops
 * @param {number[]} bottoms
 * @return {number}
 */
var minDominoRotations = function(tops, bottoms) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Domino Rotations For Equal Row — Problem & Solution

Minimum Domino Rotations For Equal Row solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Domino Rotations For Equal Row is a medium coding problem on arrays and greedy, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Greedy
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A row of dominoes is laid out left to right. Domino i shows tops[i] on its top half and bottoms[i] on its bottom half; every half shows a number from 1 to 6.

A rotation flips one domino so its top and bottom values trade places.

Return the minimum number of rotations after which all top values are equal, or all bottom values are equal. If neither can be achieved, return -1.

Example 1

Input: tops = [3,1,3,3], bottoms = [1,3,4,5]
Output: 1
Explanation: Rotating domino 1 makes the top row `[3,3,3,3]`.

Example 2

Input: tops = [2,5,1], bottoms = [6,2,4]
Output: -1
Explanation: No single value appears on every domino.

Example 3

Input: tops = [4,4], bottoms = [4,4]
Output: 0

Constraints

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

Hints for Minimum Domino Rotations For Equal Row

  1. Hint 1

    If a whole row ends up showing value x, then x must appear on every domino, in particular on domino 0.

  2. Hint 2

    So only two candidates matter: tops[0] and bottoms[0].

  3. Hint 3

    For a candidate x, fail if some domino shows x on neither half; otherwise the cost for the top row is the number of dominoes whose top is not x, and similarly for the bottom row.

How to solve Minimum Domino Rotations For Equal Row

The common value must appear on the first domino, so there are at most two candidates, and each is checked in one linear pass.

Approach

  1. For each candidate x in {tops[0], bottoms[0]}:
  2. Walk the dominoes. If neither half shows x, the candidate fails.
  3. Otherwise count rotTop (dominoes whose top is not x — they must be flipped to fill the top row) and rotBottom (likewise for the bottom).
  4. The candidate costs min(rotTop, rotBottom). Return the best over the candidates, or -1 if both fail.

Why it works

A domino showing x on one half can always be oriented to put x in the target row, at a cost of one rotation exactly when x is currently on the other side. Choosing the row whose current mismatches are fewer is optimal for that x, and any feasible x must come from domino 0.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • A domino showing x on both halves never needs a rotation — count mismatches, not matches on the other side.
  • Check both rows: making the bottom row uniform may be cheaper than the top.
  • Trying all six values also works; restricting to domino 0's values is just a shortcut.

Reference solution

Python

from typing import List

def minDominoRotations(tops: List[int], bottoms: List[int]) -> int:
    def cost(x):
        rot_top = rot_bottom = 0
        for t, b in zip(tops, bottoms):
            if t != x and b != x:
                return -1
            if t != x:
                rot_top += 1
            if b != x:
                rot_bottom += 1
        return min(rot_top, rot_bottom)

    best = -1
    for x in (tops[0], bottoms[0]):
        c = cost(x)
        if c != -1 and (best == -1 or c < best):
            best = c
    return best

Java

private static int dominoCost(int[] tops, int[] bottoms, int x) {
    int rotTop = 0, rotBottom = 0;
    for (int i = 0; i < tops.length; i++) {
        if (tops[i] != x && bottoms[i] != x) return -1;
        if (tops[i] != x) rotTop++;
        if (bottoms[i] != x) rotBottom++;
    }
    return Math.min(rotTop, rotBottom);
}

public static int minDominoRotations(int[] tops, int[] bottoms) {
    int a = dominoCost(tops, bottoms, tops[0]);
    int b = dominoCost(tops, bottoms, bottoms[0]);
    if (a == -1) return b;
    if (b == -1) return a;
    return Math.min(a, b);
}

C++

int dominoCost1007(vector<int>& tops, vector<int>& bottoms, int x) {
    int rotTop = 0, rotBottom = 0;
    for (size_t i = 0; i < tops.size(); i++) {
        if (tops[i] != x && bottoms[i] != x) return -1;
        if (tops[i] != x) rotTop++;
        if (bottoms[i] != x) rotBottom++;
    }
    return min(rotTop, rotBottom);
}

int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
    int a = dominoCost1007(tops, bottoms, tops[0]);
    int b = dominoCost1007(tops, bottoms, bottoms[0]);
    if (a == -1) return b;
    if (b == -1) return a;
    return min(a, b);
}

JavaScript

var minDominoRotations = function(tops, bottoms) {
    var cost = function(x) {
        var rotTop = 0, rotBottom = 0;
        for (var i = 0; i < tops.length; i++) {
            if (tops[i] !== x && bottoms[i] !== x) return -1;
            if (tops[i] !== x) rotTop++;
            if (bottoms[i] !== x) rotBottom++;
        }
        return Math.min(rotTop, rotBottom);
    };
    var a = cost(tops[0]), b = cost(bottoms[0]);
    if (a === -1) return b;
    if (b === -1) return a;
    return Math.min(a, b);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms