Minimum Domino Rotations For Equal Row
MedPrompt
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 * 104bottoms.length == tops.length1 <= 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
- Initialize a global variable
minRotationsto a very large value (e.g.,Integer.MAX_VALUE). - Create a recursive function
solve(index, tops, bottoms, rotations): a. Base Case: Ifindex == tops.length: i. Check if thetopsrow is uniform. If yes, updateminRotations = min(minRotations, rotations). ii. Check if thebottomsrow is uniform. If yes, updateminRotations = min(minRotations, rotations). iii. Return. b. Recursive Step: i. Choice 1 (No rotation): Callsolve(index + 1, tops, bottoms, rotations). ii. Choice 2 (Rotation): - Swaptops[index]andbottoms[index]. - Callsolve(index + 1, tops, bottoms, rotations + 1). - Backtrack: Swaptops[index]andbottoms[index]back to their original values. - Call
solve(0, tops, bottoms, 0). - If
minRotationsis still the initial large value, return -1. Otherwise, returnminRotations.
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:
- Don't rotate: We make a recursive call
findMinRotations(index + 1, currentRotations). - Rotate: We swap
tops[index]andbottoms[index], and then make a recursive callfindMinRotations(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 befindMinRotations(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
Solution
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.