Make All Dominoes the Same

Make All Dominoes the Same – Minimum Rotations

Problem Statement:

You’re given two integer arrays tops[] and bottoms[] representing domino tiles.
Each tile has a top and bottom value between 1 and 6.

You can rotate any domino (i.e., swap tops[i] and bottoms[i]).

Goal:
Find the minimum number of rotations needed so that all the values in either the tops or bottoms array are the same.

If it’s impossible, return -1.

Example:

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

Explanation: Rotate the 2nd and 4th domino so all top values become 2.

Best Data Structure for the Job:

No advanced data structures are needed here — we rely on simple counters and loops. The smart trick is to focus on just two possible candidates: tops[0] and bottoms[0].

Different Approaches

Approach 1: Brute Force

Try all numbers from 1 to 6 and check if it's possible to make all tops or all bottoms equal to that number.

public class BruteForceDomino {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int min = Integer.MAX_VALUE;

        for (int target = 1; target <= 6; target++) {
            int topRotations = 0;
            int bottomRotations = 0;
            boolean canMake = true;

            for (int i = 0; i < tops.length; i++) {
                if (tops[i] != target && bottoms[i] != target) {
                    canMake = false;
                    break;
                } else if (tops[i] != target) {
                    topRotations++;
                } else if (bottoms[i] != target) {
                    bottomRotations++;
                }
            }

            if (canMake) {
                min = Math.min(min, Math.min(topRotations, bottomRotations));
            }
        }

        return min == Integer.MAX_VALUE ? -1 : min;
    }
}

Approach 2: Optimal Greedy (Check Candidate Values Only)

We only need to check two candidates: tops[0] and bottoms[0].

public class OptimalDomino {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int rotations = check(tops[0], tops, bottoms);
        if (rotations != -1 || tops[0] == bottoms[0]) return rotations;
        return check(bottoms[0], tops, bottoms);
    }

    private int check(int target, int[] tops, int[] bottoms) {
        int topRotations = 0;
        int bottomRotations = 0;

        for (int i = 0; i < tops.length; i++) {
            if (tops[i] != target && bottoms[i] != target) {
                return -1;
            } else if (tops[i] != target) {
                topRotations++;
            } else if (bottoms[i] != target) {
                bottomRotations++;
            }
        }

        return Math.min(topRotations, bottomRotations);
    }
}

⚠️Common Mistakes and Pitfalls

  • Trying all 6 values in optimized approach when only 2 are enough

  • Forgetting to check both top and bottom for each domino

  • Not tracking both top and bottom rotation counts separately

  • Returning the wrong rotation count (always return the minimum)

📊Time and Space Complexity

Approach         Time Complexity      Space Complexity
Brute Force         O(6 * N)      O(1)
Optimal Greedy         O(N)      O(1)

🌍Real-world Applications

  • Puzzle games and board mechanics involving tile alignment

  • Hardware systems where dual-sided components need uniform alignment

  • Data normalization problems with two possible value sets


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Pascal's Triangle

 Pascal Vibes — Building Triangles Like a Pro Problem Statement Given an integer numRows , return the first numRows of Pascal's Triangle . Each number in the triangle is the sum of the two numbers directly above it . Example: Input: numRows = 5 Output: [ [ 1 ], [ 1,1 ], [ 1,2,1 ], [ 1,3,3,1 ], [ 1,4,6,4,1 ] ] Best Data Structure for Solving the Problem This is a CLASSIC example of Tabulation-based Dynamic Programming   We're filling a triangle row-by-row where: triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j] So we’ll use: A 2D List<List<Integer>> (or array of arrays) No need for fancy trees, heaps, or graphs here. Just pure math and memory  Different Approaches (from Brute Force to Optimized) Approach 1: Build Row by Row Using Previous Row This is the “OG” method — intuitive and easy to visualize. Start with [1] For each new row: Add 1 at the start and end In-between values are sum of two values above it class ...
Read more

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Tower of Hanoi Modified

Tower of Hanoi Modified – When the First Rod is a No-Go Problem Statement You’re given a classic Tower of Hanoi setup with three rods (A, B, and C) and N disks of different sizes stacked on Rod A , smallest on top. BUT there’s a twist... You cannot move a disk directly between rod A and rod C. You must always pass through rod B when going from A ➡️ C or C ➡️ A.  Goal: Move all disks from Rod A to Rod C , following the usual rules plus this new restriction, and print: The minimum number of moves required. The actual sequence of moves (formatted like Move x from A to B ). Example Input: 2 1 2 Output: 2 Move 1 from A to B Move 1 from B to C 8 Move 1 from A to B Move 1 from B to C Move 2 from A to B Move 1 from C to B Move 1 from B to A Move 2 from B to C Move 1 from A to B Move 1 from B to C Best Data Structure for the Job No need for trees, heaps, or graphs here. Just: Simple recursion  Strings to log ea...
Read more