Minimum Domino Rotations For Equal Row solution and explanation
Google
9 more videos on this problem
Minimum Domino Rotations for Equal Row - Leetcode 1007 - PythonNeetCode · 8:52 · 16K views
Minimum Domino Rotations For Equal Row | Leetcode 1007Techdose · 14:50 · 2K views
Minimum Domino Rotations For Equal Row - LeetCode 1007 - Python [O(n) time, O(1) space!]Deepti Talesra · 10:39 · 2K views
LeetCode 1007 | Minimum Domino Rotations for Equal Row | Algorithm Explained (Java)Xavier Elon · 9:12 · 1K views
Minimum Domino Rotations For Equal Row | Leetcode 1007 | Maths | Live coding session 🔥🔥Coding Decoded · 15:46 · 1K views
Minimum Domino Rotations For Equal Row | Leet code 1007 | Theory explained + Python codeSai Anish Malla · 13:05 · 608 views
Minimum Domino Rotations For Equal Row | Leetcode 1007 | leetcode solutionEasyLeetcode · 8:35 · 540 views
Leetcode - Minimum Domino Rotations For Equal Row (Python)Timothy H Chang · 7:38 · 421 views
Minimum Domino Rotations For Equal Row | LeetCode 1007 | Java | Hindi | #leetcode #leetcodejavaAll Rounder Coders · 21:43 · 149 views
Daily Leetcode #719: Mar 20, 2022 - 1007. Minimum Domino Rotations For Equal RowProgramming Live with Larry · 5:49 · 149 views
The problem
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
Approach overview
Problem Overview: You are given two arrays tops and bottoms representing a row of dominoes. Each domino can be rotated. The task is to compute the minimum number of rotations required so that all values in either the top row or bottom row become the same. If no such configuration exists, return -1.
Approach 1: One-Pass Count Method (O(n) time, O(1) space)
This approach exploits a key observation: if a solution exists, the final value must be either tops[0] or bottoms[0]. Iterate through the dominoes once and count how many rotations are required to make every value equal to the candidate. During the scan, check whether the candidate exists in at least one side of each domino. Maintain counters for rotations needed to align the top row and the bottom row separately. If at any index the candidate appears on neither side, that candidate is invalid. This is a classic greedy validation with constant memory and a single linear scan.
Approach 2: Max Frequency Element Method (O(n) time, O(1) space)
Another strategy counts how frequently each domino value appears across both rows. Since domino values range from 1 to 6, maintain small frequency arrays for tops, bottoms, and matches where both sides already contain the same value. A value can fill an entire row only if its total occurrences cover all positions after accounting for overlaps. For each value from 1 to 6, compute the minimum rotations required: either rotate bottoms to match tops or vice versa. This method relies on frequency counting and works well when reasoning about candidate values explicitly within the small fixed domain of domino numbers.
Both solutions rely on simple array traversal and constant-size counters. The greedy validation ensures that every domino can support the chosen value before counting rotations.
Recommended for interviews: The One-Pass Count Method is what interviewers typically expect. It shows you recognized the candidate-value constraint and implemented a linear greedy check with constant space. The frequency method is also valid but slightly more mechanical. Demonstrating the one-pass logic signals stronger problem insight.
Approach 1: One-Pass Count Method
This approach is based on selecting a target number to either dominate the top or bottom row and counting the minimum rotations needed.
We first choose a target which could dominate the row: either tops[0] or bottoms[0]. Then we iterate over each domino, using an additional check to verify if that target can fully dominate a row. If we face a domino where neither side contains the target, it's not possible for that target to dominate the row.
def minDominoRotations(tops: List[int], bottoms: List[int]) -> int:
def check(x):
rotations_a = rotations_b = 0
for i in range(len(tops)):
if tops[i] != x and bottoms[i] != x:
return float('inf')
elif tops[i] != x:
rotations_a += 1
elif bottoms[i] != x:
rotations_b += 1
return min(rotations_a, rotations_b)
rotations = min(check(tops[0]), check(bottoms[0]))
return -1 if rotations == float('inf') else rotationsclass Solution {
public int minDominoRotations(int[] tops, int[] bottoms) {
int check(int val, int[] A, int[] B) {
int rotations_a = 0, rotations_b = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] != val && B[i] != val) return Integer.MAX_VALUE;
else if (A[i] != val) rotations_a++;
else if (B[i] != val) rotations_b++;
}
return Math.min(rotations_a, rotations_b);
}
int minRotations = Math.min(check(tops[0], tops, bottoms), check(bottoms[0], tops, bottoms));
return minRotations == Integer.MAX_VALUE ? -1 : minRotations;
}
}#include <vector>
#include <algorithm>
using namespace std;
int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
auto check = [&](int x) {
int rotations_a = 0, rotations_b = 0;
for (int i = 0; i < tops.size(); i++) {
if (tops[i] != x && bottoms[i] != x) return INT_MAX;
else if (tops[i] != x) rotations_a++;
else if (bottoms[i] != x) rotations_b++;
}
return min(rotations_a, rotations_b);
};
int rotations = check(tops[0]);
rotations = min(rotations, check(bottoms[0]));
return rotations == INT_MAX ? -1 : rotations;
}var minDominoRotations = function(tops, bottoms) {
const check = (x) => {
let rotations_a = 0, rotations_b = 0;
for (let i = 0; i < tops.length; ++i) {
if (tops[i] !== x && bottoms[i] !== x) return Number.MAX_SAFE_INTEGER;
else if (tops[i] !== x) rotations_a++;
else if (bottoms[i] !== x) rotations_b++;
}
return Math.min(rotations_a, rotations_b);
};
let minRotations = Math.min(check(tops[0]), check(bottoms[0]));
return minRotations === Number.MAX_SAFE_INTEGER ? -1 : minRotations;
};#include <stdbool.h>
int minDominoRotations(int* tops, int topsSize, int* bottoms, int bottomsSize) {
int myMin(int a, int b) {
return a < b ? a : b;
}
bool canConvert(int targetValue) {
int topRotations = 0, bottomRotations = 0;
for (int i = 0; i < topsSize; i++) {
if (tops[i] != targetValue && bottoms[i] != targetValue) {
return false;
} else if (tops[i] != targetValue) {
topRotations++;
} else if (bottoms[i] != targetValue) {
bottomRotations++;
}
}
return myMin(topRotations, bottomRotations);
}
int target1 = tops[0];
int target2 = bottoms[0];
int result1 = canConvert(target1) ? canConvert(target1) : -1;
int result2 = canConvert(target2) ? canConvert(target2) : -1;
if (result1 == -1) return result2;
if (result2 == -1) return result1;
return myMin(result1, result2);
}public class Solution {
public int MinDominoRotations(int[] tops, int[] bottoms) {
int Check(int x) {
int rotations_a = 0, rotations_b = 0;
for (int i = 0; i < tops.Length; ++i) {
if (tops[i] != x && bottoms[i] != x) return int.MaxValue;
else if (tops[i] != x) rotations_a++;
else if (bottoms[i] != x) rotations_b++;
}
return Math.Min(rotations_a, rotations_b);
}
int rotations = Math.Min(Check(tops[0]), Check(bottoms[0]));
return rotations == int.MaxValue ? -1 : rotations;
}
}This Python solution involves defining a check() function to determine the minimum number of rotations for a candidate number. The candidate numbers are taken from the initial values of the tops and bottoms lists.
Time Complexity: O(n), where n is the length of the input lists.
Space Complexity: O(1)
Approach 2: Max Frequency Element Method
To solve the problem using this approach, we evaluate the elements with the most appearance that could be converted to make a row uniform. This involves utilizing frequency maps to identify potential candidates quickly and checking their feasibility.
def minDominoRotations(tops: List[int], bottoms: List[int]) -> int:
maxFreq = set([tops[0], bottoms[0]])
for val in maxFreq:
rotations_t, rotations_b = 0, 0
for i in range(len(tops)):
if tops[i] != val and bottoms[i] != val:
rotations_t = rotations_b = float('inf')
break
elif tops[i] != val:
rotations_t += 1
elif bottoms[i] != val:
rotations_b += 1
rotations = min(rotations_t, rotations_b)
if rotations != float('inf'):
return rotations
return -1class Solution {
public int minDominoRotations(int[] tops, int[] bottoms) {
int[] count = new int[7];
int n = tops.length;
for (int i = 0; i < n; ++i) {
count[tops[i]]++;
count[bottoms[i]]++;
}
for (int i = 1; i <= 6; ++i) {
if (count[i] >= n) {
int maxFreq = 0, topFreq = 0, bottomFreq = 0;
for (int j = 0; j < n; ++j) {
if (tops[j] != i && bottoms[j] != i) {
maxFreq = Integer.MAX_VALUE;
break;
}
if (tops[j] != i) ++topFreq;
if (bottoms[j] != i) ++bottomFreq;
}
if (maxFreq != Integer.MAX_VALUE)
return Math.min(topFreq, bottomFreq);
}
}
return -1;
}
}#include <vector>
#include <unordered_map>
#include <algorithm>
#include <climits>
using namespace std;
int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
unordered_map<int, int> count;
for (int i = 0; i < tops.size(); ++i) {
count[tops[i]]++;
count[bottoms[i]]++;
}
for (auto& c : count) {
if (c.second >= tops.size()) {
int countT = 0, countB = 0;
for (int i = 0; i < tops.size(); ++i) {
if (tops[i] != c.first && bottoms[i] != c.first) return -1;
if (tops[i] != c.first) countT++;
if (bottoms[i] != c.first) countB++;
}
return min(countT, countB);
}
}
return -1;
}var minDominoRotations = function(tops, bottoms) {
const candidates = [tops[0], bottoms[0]];
for (const val of candidates) {
let rotations_a = 0, rotations_b = 0;
for (let i = 0; i < tops.length; ++i) {
if (tops[i] !== val && bottoms[i] !== val) {
rotations_a = rotations_b = Number.MAX_SAFE_INTEGER;
break;
} else if (tops[i] !== val) rotations_a++;
else if (bottoms[i] !== val) rotations_b++;
}
const rotations = Math.min(rotations_a, rotations_b);
if (rotations !== Number.MAX_SAFE_INTEGER) return rotations;
}
return -1;
};#include <limits.h>
int minDominoRotations(int* tops, int topsSize, int* bottoms, int bottomsSize) {
int myMin(int a, int b) {
return a < b ? a : b;
}
int count[7] = {0};
for (int i = 0; i < topsSize; ++i) {
count[tops[i]]++;
count[bottoms[i]]++;
}
int maxFreq = 0;
int potential[] = {tops[0], bottoms[0]};
int total = 0;
for (int i = 0; i < 2; ++i) {
total = 0;
for (int j = 0; j < topsSize; ++j) {
if (tops[j] != potential[i] && bottoms[j] != potential[i]) {
total = -1;
break;
}
total += tops[j] != potential[i];
}
if (total != -1) maxFreq = myMin(total, maxFreq == 0 ? total : maxFreq);
}
return maxFreq == 0 ? -1 : maxFreq;
}public class Solution {
public int MinDominoRotations(int[] tops, int[] bottoms) {
int maxFreq = tops[0];
int rotations_t, rotations_b;
for (int candidate = 0; candidate < 2; ++candidate) {
int val = candidate == 0 ? tops[0] : bottoms[0];
rotations_t = rotations_b = 0;
for (int i = 0; i < tops.Length; ++i) {
if (tops[i] != val && bottoms[i] != val) {
rotations_t = rotations_b = int.MaxValue;
break;
} else if (tops[i] != val) rotations_t++;
else if (bottoms[i] != val) rotations_b++;
}
int rotations = Math.Min(rotations_t, rotations_b);
if (rotations != int.MaxValue) return rotations;
}
return -1;
}
}This Python solution uses a set for both first elements of tops and bottoms arrays to count necessary rotations by checking overall match feasibility.
Time Complexity: O(n), where n is the length of the input lists.
Space Complexity: O(1)
Approach 3: Greedy
According to the problem description, we know that in order to make all values in tops or all values in bottoms the same, the value must be one of tops[0] or bottoms[0].
Therefore, we design a function f(x) to represent the minimum number of rotations required to make all values equal to x. Then the answer is min{f(tops[0]), f(bottoms[0])}.
The calculation method of function f(x) is as follows:
We use two variables cnt1 and cnt2 to count the number of occurrences of x in tops and bottoms, respectively. We subtract the maximum value of cnt1 and cnt2 from n, which is the minimum number of rotations required to make all values equal to x. Note that if there are no values equal to x in tops and bottoms, the value of f(x) is a very large number, which we represent as n+1.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function minDominoRotations(tops: number[], bottoms: number[]): number {
const n = tops.length;
const f = (x: number): number => {
let [cnt1, cnt2] = [0, 0];
for (let 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);
};
const ans = Math.min(f(tops[0]), f(bottoms[0]));
return ans > n ? -1 : ans;
}func minDominoRotations(tops []int, bottoms []int) int {
n := len(tops)
f := func(x int) int {
cnt1, cnt2 := 0, 0
for i, a := range tops {
b := bottoms[i]
if a != x && b != x {
return n + 1
}
if a == x {
cnt1++
}
if b == x {
cnt2++
}
}
return n - max(cnt1, cnt2)
}
ans := min(f(tops[0]), f(bottoms[0]))
if ans > n {
return -1
}
return ans
}impl Solution {
pub fn min_domino_rotations(tops: Vec<i32>, bottoms: Vec<i32>) -> i32 {
let n = tops.len() as i32;
let f = |x: i32| -> i32 {
let mut cnt1 = 0;
let mut cnt2 = 0;
for i in 0..n as usize {
if tops[i] != x && bottoms[i] != x {
return n + 1;
}
if tops[i] == x {
cnt1 += 1;
}
if bottoms[i] == x {
cnt2 += 1;
}
}
n - cnt1.max(cnt2)
};
let ans = f(tops[0]).min(f(bottoms[0]));
if ans > n { -1 } else { ans }
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| One-Pass Count Method | Time Complexity: O(n), where n is the length of the input lists. |
| Max Frequency Element Method | Time Complexity: O(n), where n is the length of the input lists. |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| One-Pass Count Method | O(n) | O(1) | Best general solution. Quickly validates candidate values and computes minimum rotations in a single scan. |
| Max Frequency Element Method | O(n) | O(1) | Useful when reasoning through value frequencies (1–6). Good alternative if you prefer explicit counting logic. |
Frequently asked questions
Is Minimum Domino Rotations For Equal Row easy or hard?
Minimum Domino Rotations For Equal Row is considered a medium difficulty problem. The challenge lies in recognizing that only two candidate values need to be checked and designing a linear pass that validates the candidate while counting rotations.
Minimum Domino Rotations For Equal Row Python/Java solution
Python and Java implementations follow the same greedy logic: test candidate values from the first domino and count required rotations during a single pass. Both implementations achieve O(n) time and O(1) space using simple loops and integer counters.
How to solve Minimum Domino Rotations For Equal Row in O(n)?
Pick a candidate value (either tops[0] or bottoms[0]) and iterate through the dominoes. For each index, ensure the candidate appears in at least one side; otherwise the candidate is invalid. Count rotations needed to align the top or bottom row. The minimum valid rotation count across candidates gives the result in O(n) time.
What is the best approach for Minimum Domino Rotations For Equal Row?
The best approach is the One-Pass Count Method. It checks whether either tops[0] or bottoms[0] can be the final uniform value and counts the rotations required while scanning the arrays once. This greedy validation runs in O(n) time with O(1) extra space.
Is Minimum Domino Rotations For Equal Row asked at Google/Amazon/Meta?
Minimum Domino Rotations For Equal Row is a common medium-level array and greedy interview problem. Variations of this question have appeared in interviews at companies like Amazon, Google, and Meta to evaluate problem-solving with constraints and linear scans.
What data structure is used in Minimum Domino Rotations For Equal Row?
The solution primarily uses arrays and simple counters. The algorithm performs linear traversal with integer counters to track rotations and candidate validity, making it a straightforward array and greedy problem.
What is the time complexity of Minimum Domino Rotations For Equal Row?
The optimal solution runs in O(n) time where n is the number of dominoes. Each domino is examined once to verify whether a candidate value can fill the row and to count the required rotations. Space complexity remains O(1) because only a few counters are used.