Minimum Domino Rotations For Equal Row

Minimum Domino Rotations For Equal Row - Problem

Array Greedy Medium

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

We may rotate the i-th 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.

Input & Output

Example 1 — Basic Case

$ Input: tops = [2,1,2,1], bottoms = [1,2,1,2]

› Output: 2

💡 Note: We can make all tops equal to 2 by rotating dominoes at indices 1 and 3. After rotation: tops = [2,2,2,2]. Total rotations needed: 2.

Example 2 — Impossible Case

$ Input: tops = [3,5,1,2], bottoms = [3,6,3,3]

› Output: -1

💡 Note: No single value appears in every domino position (tops[i] or bottoms[i]), so it's impossible to make all tops or all bottoms uniform.

Example 3 — No Rotations Needed

$ Input: tops = [1,1,1], bottoms = [2,2,2]

› Output: 0

💡 Note: The tops are already all equal to 1, so no rotations are needed. Answer is 0.

Constraints

2 ≤ tops.length == bottoms.length ≤ 2 × 10⁴
1 ≤ tops[i], bottoms[i] ≤ 6

Visualization

Tap to expand

Asked in

a Amazon 15 f Facebook 12 G Google 8

The key insight is that if we can make all dominoes uniform, the target value must appear in every domino position. Since it must appear in the first domino, we only need to check tops[0] and bottoms[0] as potential targets. Best approach is the optimized solution: Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Check First Domino Only	O(n)	O(1)	Only check the two values from the first domino as potential targets
Brute Force - Try All Values	O(n)	O(1)	Try each possible value (1-6) as target and count rotations needed

Optimized - Check First Domino Only — Algorithm Steps

Extract the two values from first domino: tops[0] and bottoms[0]
For each value, try making all tops equal to it
For each value, try making all bottoms equal to it
Return minimum rotations found, or -1 if impossible

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Candidates

Get tops[0]=2 and bottoms[0]=1 as only possible targets

Test Each Target

Check if target 2 or target 1 can make uniform row

Find Minimum

Return the target requiring fewer rotations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int checkRotations(int* tops, int* bottoms, int n, int target, int makeTopsUniform) {
    int rotations = 0;
    
    for (int i = 0; i < n; i++) {
        if (makeTopsUniform) {
            if (tops[i] == target) {
                continue;  // No rotation needed
            } else if (bottoms[i] == target) {
                rotations++;  // Need to rotate
            } else {
                return -1;  // Impossible
            }
        } else {  // make bottoms uniform
            if (bottoms[i] == target) {
                continue;  // No rotation needed
            } else if (tops[i] == target) {
                rotations++;  // Need to rotate
            } else {
                return -1;  // Impossible
            }
        }
    }
    return rotations;
}

int solution(int* tops, int* bottoms, int n) {
    int minRotations = INT_MAX;
    
    // Only check values from first domino as potential targets
    int candidates[2] = {tops[0], bottoms[0]};
    
    for (int i = 0; i < 2; i++) {
        int target = candidates[i];
        
        // Try making all tops equal to target
        int rotations = checkRotations(tops, bottoms, n, target, 1);
        if (rotations != -1 && rotations < minRotations) {
            minRotations = rotations;
        }
        
        // Try making all bottoms equal to target
        rotations = checkRotations(tops, bottoms, n, target, 0);
        if (rotations != -1 && rotations < minRotations) {
            minRotations = rotations;
        }
    }
    
    return minRotations == INT_MAX ? -1 : minRotations;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Simple parsing - count commas to get array size
    int n = 1;
    for (int i = 0; line1[i]; i++) {
        if (line1[i] == ',') n++;
    }
    
    int* tops = malloc(n * sizeof(int));
    int* bottoms = malloc(n * sizeof(int));
    
    // Parse arrays manually
    char* ptr = strtok(line1 + 1, ",]");
    for (int i = 0; i < n; i++) {
        tops[i] = atoi(ptr);
        ptr = strtok(NULL, ",]");
    }
    
    ptr = strtok(line2 + 1, ",]");
    for (int i = 0; i < n; i++) {
        bottoms[i] = atoi(ptr);
        ptr = strtok(NULL, ",]");
    }
    
    int result = solution(tops, bottoms, n);
    printf("%d\n", result);
    
    free(tops);
    free(bottoms);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through dominoes for each of the 4 cases (2 targets × 2 arrays)

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track counts and targets

✓ Linear Space

18.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Check First Domino Only — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler