Minimum Domino Rotations For Equal Row

medium greedy array dominoes

Problem

You are given two arrays tops and bottoms representing a row of dominoes; the i-th domino shows tops[i] on top and bottoms[i] on bottom. In one rotation you may swap the top and bottom of a single domino. Return the minimum number of rotations so that all values in tops are the same, or all values in bottoms are the same. If it cannot be done, return -1.

Inputtops = [2, 1, 2, 4, 2, 2], bottoms = [5, 2, 6, 2, 3, 2]

Output2

Rotating the 2nd and 4th dominoes brings every value in the top row to 2.

tops (comma-separated, 1–6)

bottoms (comma-separated, 1–6)

def min_domino_rotations(tops, bottoms):
    n = len(tops)

    def rotations(target):
        top_rot, bot_rot = 0, 0
        for i in range(n):
            if tops[i] != target and bottoms[i] != target:
                return float("inf")
            if tops[i] != target:
                top_rot += 1
            if bottoms[i] != target:
                bot_rot += 1
        return min(top_rot, bot_rot)

    ans = min(rotations(tops[0]), rotations(bottoms[0]))
    return -1 if ans == float("inf") else ans

function minDominoRotations(tops, bottoms) {
  const n = tops.length;

  function rotations(target) {
    let topRot = 0, botRot = 0;
    for (let i = 0; i < n; i++) {
      if (tops[i] !== target && bottoms[i] !== target) return Infinity;
      if (tops[i] !== target) topRot++;
      if (bottoms[i] !== target) botRot++;
    }
    return Math.min(topRot, botRot);
  }

  const ans = Math.min(rotations(tops[0]), rotations(bottoms[0]));
  return ans === Infinity ? -1 : ans;
}

class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int ans = Math.min(rotations(tops, bottoms, tops[0]),
                           rotations(tops, bottoms, bottoms[0]));
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private int rotations(int[] tops, int[] bottoms, int target) {
        int topRot = 0, botRot = 0;
        for (int i = 0; i < tops.length; i++) {
            if (tops[i] != target && bottoms[i] != target) return Integer.MAX_VALUE;
            if (tops[i] != target) topRot++;
            if (bottoms[i] != target) botRot++;
        }
        return Math.min(topRot, botRot);
    }
}

int rotations(vector<int>& tops, vector<int>& bottoms, int target) {
    int topRot = 0, botRot = 0;
    for (int i = 0; i < (int)tops.size(); i++) {
        if (tops[i] != target && bottoms[i] != target) return INT_MAX;
        if (tops[i] != target) topRot++;
        if (bottoms[i] != target) botRot++;
    }
    return min(topRot, botRot);
}

int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
    int ans = min(rotations(tops, bottoms, tops[0]),
                  rotations(tops, bottoms, bottoms[0]));
    return ans == INT_MAX ? -1 : ans;
}

Explanation

The key realization is that if some value v can fill an entire row, then every domino must already have v on at least one of its two sides. In particular, the very first domino must show v too. So there are only two candidate values worth trying: tops[0] and bottoms[0].

For a candidate target, we scan all dominoes. If any domino has target on neither side, that target is impossible (we return infinity). Otherwise we count topRot = how many tops are not target (these would need a flip to make the top row uniform) and botRot the same for the bottom row.

Making the top row all target costs topRot flips; making the bottom row all target costs botRot flips. We take the smaller of the two for that candidate.

We run this for both candidate values and keep the overall minimum. If neither works, the answer is -1.

Example: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]. Trying target = 2, every domino has a 2 somewhere, and flipping the two dominoes whose top isn't 2 makes the whole top row equal to 2 — so the answer is 2.

Time: O(n) Space: O(1)