Skip to main content
Talentd

Minimum Domino Rotations For Equal Row - Solution & Explanation

MediumArrayGreedy20 min readAsked at: Amazon, Microsoft, Meta +1
Practice this problem

Problem Statement

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

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.

We try rotating to make all dominoes` number either one of the first elements from tops or bottoms. We count the rotations for both top and bottom for each target. If any domino can't be converted to the target value at any time, the approach exits early.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(1)

Try this approach in the editor →

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.

Count the maximum appearances by any number from both top and bottom rows. Aim to make this number dominate the row by counting feasible rotations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(1)

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
One-Pass Count Method

Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(1)

Max Frequency Element Method

Time Complexity: O(n), where n is the number of dominoes.
Space Complexity: O(1)

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
One-Pass Count MethodO(n)O(1)Best general solution. Quickly validates candidate values and computes minimum rotations in a single scan.
Max Frequency Element MethodO(n)O(1)Useful when reasoning through value frequencies (1–6). Good alternative if you prefer explicit counting logic.

Video Solution

Minimum Domino Rotations for Equal Row - Leetcode 1007 - Python • NeetCode • 16,454 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Domino Rotations For Equal Row with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays