Scale Engineer

Minimum Domino Rotations For Equal Row

Med
#0961Time: O(N * 2^N). The recursion tree has `2^N` leaves. At each leaf node (base case), we perform a check that takes `O(N)` time.Space: O(N). This is due to the recursion stack depth, which can go up to `N`.
Patterns
Greedy
Data structures
Array

Prompt

In a row of dominoes, tops[i] and bottoms[i] represent the top and bottom halves of the ith domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)

We may rotate the ith domino, so that tops[i] and bottoms[i] swap values.

Return the minimum number of rotations so that all the values in tops are the same, or all the values in bottoms are the same.

If it cannot be done, return -1.

 

Example 1:

Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
Output: 2
Explanation: 
The first figure represents the dominoes as given by tops and bottoms: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.

Example 2:

Input: tops = [3,5,1,2,3], bottoms = [3,6,3,3,4]
Output: -1
Explanation: 
In this case, it is not possible to rotate the dominoes to make one row of values equal.

 

Constraints:

  • 2 <= tops.length <= 2 * 104
  • bottoms.length == tops.length
  • 1 <= tops[i], bottoms[i] <= 6

Approaches

3 approaches with complexity analysis and trade-offs.

This approach explores every possible configuration of the domino row. For each of the N dominoes, we can either keep it as is or rotate it. This leads to 2^N possible states. We can use recursion (backtracking) to generate all these states. For each state, we check if either the top row or the bottom row consists of all equal values. We keep track of the minimum number of rotations used to achieve such a state.

Algorithm

  1. Initialize a global variable minRotations to a very large value (e.g., Integer.MAX_VALUE).
  2. Create a recursive function solve(index, tops, bottoms, rotations): a. Base Case: If index == tops.length: i. Check if the tops row is uniform. If yes, update minRotations = min(minRotations, rotations). ii. Check if the bottoms row is uniform. If yes, update minRotations = min(minRotations, rotations). iii. Return. b. Recursive Step: i. Choice 1 (No rotation): Call solve(index + 1, tops, bottoms, rotations). ii. Choice 2 (Rotation): - Swap tops[index] and bottoms[index]. - Call solve(index + 1, tops, bottoms, rotations + 1). - Backtrack: Swap tops[index] and bottoms[index] back to their original values.
  3. Call solve(0, tops, bottoms, 0).
  4. If minRotations is still the initial large value, return -1. Otherwise, return minRotations.

Walkthrough

We define a recursive function, say findMinRotations(index, currentRotations), which explores the possibilities from the index-th domino onwards. The base case for the recursion is when index reaches the end of the array (tops.length). At this point, we have a complete configuration. We then check if the tops array is uniform or if the bottoms array is uniform. To check for uniformity, we can take the first element of a row and see if all other elements are the same. If a row is uniform, we update a global minimum rotations variable with currentRotations if it's smaller. In the recursive step for a given index, we have two choices:

  1. Don't rotate: We make a recursive call findMinRotations(index + 1, currentRotations).
  2. Rotate: We swap tops[index] and bottoms[index], and then make a recursive call findMinRotations(index + 1, currentRotations + 1). After the call returns, we must swap back (backtrack) to restore the state for other branches of the recursion. The initial call would be findMinRotations(0, 0). The final result is the global minimum found, or -1 if it was never updated.
// This approach is too slow and will result in a Time Limit Exceeded error.// It is for demonstration of the brute-force concept only.class Solution {    int minRotations = Integer.MAX_VALUE;     public int minDominoRotations(int[] tops, int[] bottoms) {        solve(0, tops, bottoms, 0);        return minRotations == Integer.MAX_VALUE ? -1 : minRotations;    }     private void solve(int index, int[] tops, int[] bottoms, int rotations) {        if (index == tops.length) {            checkUniform(tops, bottoms, rotations);            return;        }         // Option 1: Don't rotate        solve(index + 1, tops, bottoms, rotations);         // Option 2: Rotate        swap(tops, bottoms, index);        solve(index + 1, tops, bottoms, rotations + 1);        swap(tops, bottoms, index); // Backtrack    }     private void checkUniform(int[] tops, int[] bottoms, int rotations) {        boolean topsUniform = true;        for (int i = 1; i < tops.length; i++) {            if (tops[i] != tops[0]) {                topsUniform = false;                break;            }        }        if (topsUniform) {            minRotations = Math.min(minRotations, rotations);        }         boolean bottomsUniform = true;        for (int i = 1; i < bottoms.length; i++) {            if (bottoms[i] != bottoms[0]) {                bottomsUniform = false;                break;            }        }        if (bottomsUniform) {            minRotations = Math.min(minRotations, rotations);        }    }     private void swap(int[] tops, int[] bottoms, int i) {        int temp = tops[i];        tops[i] = bottoms[i];        bottoms[i] = temp;    }}

Complexity

Time

O(N * 2^N). The recursion tree has `2^N` leaves. At each leaf node (base case), we perform a check that takes `O(N)` time.

Space

O(N). This is due to the recursion stack depth, which can go up to `N`.

Trade-offs

Pros

  • It's a straightforward translation of the problem statement: "try all possibilities".

  • Guaranteed to find the correct answer.

Cons

  • Extremely inefficient and will not pass the time limits for the given constraints.

Solutions

class Solution {private  int n;private  int[] tops;private  int[] bottoms;public  int minDominoRotations(int[] tops, int[] bottoms) {    n = tops.length;    this.tops = tops;    this.bottoms = bottoms;    int ans = Math.min(f(tops[0]), f(bottoms[0]));    return ans > n ? -1 : ans;  }private  int f(int x) {    int cnt1 = 0, cnt2 = 0;    for (int i = 0; i < n; ++i) {      if (tops[i] != x && bottoms[i] != x) {        return n + 1;      }      cnt1 += tops[i] == x ? 1 : 0;      cnt2 += bottoms[i] == x ? 1 : 0;    }    return n - Math.max(cnt1, cnt2);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem