Minimum Domino Rotations

📋

Problem

Imagine you have a row of dominoes, each with two numbers on top and bottom. You want to make all the numbers on one side the same by flipping some dominoes. How few flips do you need?

You are given two arrays A and B of equal length n, representing the top and bottom halves of n dominoes. Each domino has a number from 1 to 6 on each half. You can rotate the i-th domino, swapping A[i] and B[i]. Return the minimum number of rotations so that all values in A are the same, or all values in B are the same. If it cannot be done, return -1.

1 ≤ n ≤ 10^51 ≤ A[i], B[i] ≤ 6

Edge cases: All dominoes already have the same number on top → output 0All dominoes have the same number on bottom → output 0Only one domino → output 0

</>

IDE

def minDominoRotations(A: list[int], B: list[int]) -> int:public int minDominoRotations(int[] A, int[] B)int minDominoRotations(vector<int> &A, vector<int> &B)function minDominoRotations(A, B)

def minDominoRotations(A, B):
    # Write your solution here
    pass

class Solution {
    public int minDominoRotations(int[] A, int[] B) {
        // Write your solution here
        return -1;
    }
}

#include <vector>
using namespace std;

int minDominoRotations(vector<int> &A, vector<int> &B) {
    // Write your solution here
    return -1;
}

function minDominoRotations(A, B) {
    // Write your solution here
    return -1;
}

Common Bugs to Avoid

Wrong: -1 when solution existsFailing to check both arrays for candidate values or breaking early incorrectly.✅ Ensure to check both A[i] and B[i] for each candidate and only break when neither matches.

Wrong: Non-zero rotations when arrays are uniformNot handling uniform arrays as a special case returning 0 rotations.✅ Add checks for uniformity of A or B arrays and return 0 immediately.

Wrong: Incorrect rotations count due to counting only one sideCounting rotations only for A or only for B, missing the minimum rotations option.✅ Count rotations needed to unify A and separately for B, then take the minimum.

Wrong: Timeout on large inputsUsing O(6*n) or brute force approach instead of optimized O(n) greedy.✅ Check only candidates A[0] and B[0] and count rotations in a single pass.

Wrong: Returns rotations when no solution existsNot returning -1 when no candidate can unify arrays.✅ Return -1 if no candidate satisfies the condition after checking all.

✓

Test Cases

Try testing your solution on empty and single-element inputs to catch base case bugs.

Focus on the greedy optimization: only two candidates need checking, not all six.

Optimize your solution to O(n) by counting rotations in a single pass with early exit.

t1_01basic

Input{"A":[2,1,2,4,2,2],"B":[5,2,6,2,3,2]}

Expected2

⏱ Performance - must finish in 2000ms

Rotate the second and fourth dominoes to make all values in A equal to 2.

💡 Check each number from 1 to 6 as a candidate for unification.

💡 Count rotations needed to make all elements in A or B equal to the candidate.

💡 Return the minimum rotations among all candidates or -1 if impossible.

Why it failed: Incorrect output means failure to correctly count rotations or check both arrays. Fix by ensuring you check both A and B for each candidate and count rotations properly.

✓ Correctly identifies minimum rotations for the canonical example.

t1_02basic

Input{"A":[3,5,1,2,3],"B":[3,6,3,3,4]}

Expected-1

⏱ Performance - must finish in 2000ms

Rotating the second domino makes all values in A equal to 3 with 1 rotation.

💡 Try candidates 1 through 6 and count rotations needed.

💡 Remember to check both top and bottom arrays for each candidate.

💡 Minimum rotations is 1 by rotating the second domino to get all 3s on top.

Why it failed: Failing here usually means not checking all candidates or not counting rotations correctly. Fix by iterating candidates 1-6 and counting rotations on both arrays.

✓ Correctly finds minimum rotations for a different input.

t2_01edge

Input{"A":[],"B":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty input means no dominoes to rotate; all values on one side are trivially equal, so return 0.

💡 Check if input arrays are empty before processing.

💡 If no dominoes, no rotations are needed as arrays are trivially uniform.

💡 Return 0 immediately for empty input.

Why it failed: Code crashes or returns wrong value on empty input. Fix by adding a check for empty arrays and returning 0.

✓ Handles empty input gracefully.

t2_02edge

Input{"A":[4],"B":[3]}

Expected0

⏱ Performance - must finish in 2000ms

Only one domino; no rotations needed as all values on one side are trivially equal.

💡 Consider the single element case separately.

💡 No rotations needed if only one domino.

💡 Return 0 when n=1.

Why it failed: Fails to return 0 for single element input. Fix by returning 0 when input length is 1.

✓ Correctly returns 0 for single domino.

t2_03edge

Input{"A":[1,1,1,1],"B":[2,2,2,2]}

Expected0

⏱ Performance - must finish in 2000ms

All dominoes already have the same number on top; no rotations needed.

💡 Check if all elements in A are the same.

💡 If yes, rotations needed is zero.

💡 Return 0 immediately if top is uniform.

Why it failed: Fails to detect uniform top array and returns non-zero. Fix by checking uniformity of A before counting rotations.

✓ Detects uniform top array and returns 0.

t2_04edge

Input{"A":[2,2,2,2],"B":[1,1,1,1]}

Expected0

⏱ Performance - must finish in 2000ms

All dominoes already have the same number on bottom; no rotations needed.

💡 Check if all elements in B are the same.

💡 If yes, rotations needed is zero.

💡 Return 0 immediately if bottom is uniform.

Why it failed: Fails to detect uniform bottom array and returns non-zero. Fix by checking uniformity of B before counting rotations.

✓ Detects uniform bottom array and returns 0.

t3_01corner

Input{"A":[1,2,1,1,1,2,2,2],"B":[2,1,2,2,2,2,2,2]}

Expected1

⏱ Performance - must finish in 2000ms

Minimum rotations is 2 to make all values in B equal to 2 by rotating first and second dominoes.

💡 Check candidates only from A[0] and B[0] to optimize.

💡 Count rotations needed for these candidates only.

💡 Minimum rotations is 2 by rotating dominoes to get all 2s on bottom.

Why it failed: Fails greedy optimization by checking all candidates instead of only A[0] and B[0]. Fix by limiting candidates to these two values.

✓ Correctly applies greedy optimization checking only two candidates.

t3_02corner

Input{"A":[1,1,1,1,1],"B":[2,2,2,2,3]}

Expected0

⏱ Performance - must finish in 2000ms

All dominoes have the same number on top; no rotations needed even though bottom is not uniform.

💡 Check if top is uniform before considering rotations.

💡 If uniform, rotations needed is zero regardless of bottom.

💡 Return 0 immediately if top is uniform.

Why it failed: Fails to short-circuit when top is uniform and returns incorrect rotations. Fix by adding early return for uniform top array.

✓ Correctly returns 0 for uniform top array.

t3_03corner

Input{"A":[1,2,3,4,5],"B":[6,6,6,6,6]}

Expected0

⏱ Performance - must finish in 2000ms

No number can unify top or bottom arrays; return -1.

💡 Check all candidates and verify if any can unify arrays.

💡 If none can unify, return -1.

💡 Return -1 when no candidate satisfies the condition.

Why it failed: Returns a non -1 value when no candidate can unify arrays. Fix by ensuring to return -1 if no candidate works.

✓ Correctly returns -1 when unification impossible.

t4_01performance

Input{"A":[1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6],"B":[6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1,6,5,4,3,2,1]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) solution must complete within 2 seconds.

💡 Use O(n) greedy approach checking only two candidates.

💡 Avoid checking all 6 candidates to reduce complexity.

💡 Count rotations in a single pass with early exit.

Why it failed: Solution exceeds time limit due to O(6*n) or worse complexity. Fix by implementing O(n) greedy approach checking only A[0] and B[0] candidates.

✓ Solution runs efficiently in O(n) time.

Practice

1. You are given a list of non-negative integers and need to arrange them to form the largest possible number when concatenated. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming to find the maximum concatenation by exploring all subsequences

B. Sorting the numbers as strings using a custom comparator that compares concatenations

C. Greedy approach by always picking the largest integer first

D. Brute force generating all permutations and selecting the maximum concatenation

Solution

1. Step 1: Understand the problem requires ordering numbers to maximize concatenation

   The key is to compare pairs by concatenating in both possible orders and deciding which order yields a larger combined string.

2. Step 2: Recognize that sorting with a custom comparator based on concatenation comparisons guarantees optimal order

   This approach ensures the final concatenation is lexicographically largest, unlike greedy or DP which do not handle pairwise ordering correctly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Custom comparator sorting is the standard solution for this problem [OK]

Hint: Compare concatenations as strings to decide order [OK]

Common Mistakes:

• Assuming greedy pick of largest integer works
• Using DP which is unnecessary
• Brute force is correct but inefficient

2. Consider the following Python code for forming the largest number from the list [3, 30, 34, 5]. What is the final returned string?

easy

A. 534330

B. 53430

C. 534303

D. 534330

Solution

1. Step 1: Convert numbers to strings: ['3', '30', '34', '5']

   We compare pairs by concatenation: '5'+'34' vs '34'+'5' -> '534' > '345', so '5' before '34'. Similarly for others.

2. Step 2: Sort using custom comparator to get order: ['5', '34', '3', '30']

   Concatenate to get '534330'. The check for leading zero is false since first is '5'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Concatenation order matches expected largest number [OK]

Hint: Compare concatenations 'a+b' and 'b+a' to order strings [OK]

Common Mistakes:

• Off-by-one in sorting
• Ignoring leading zero case
• Misordering '30' and '3'

3. Consider the following Python function that calculates the minimum number of platforms needed. Given the input arrivals = [900, 940, 950] and departures = [910, 1200, 1120], what is the value of max_platforms after processing the second train (index 1)?

easy

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Sort trains by arrival time

   Sorted trains: [(900, 910), (940, 1200), (950, 1120)]

2. Step 2: Process trains up to index 1

   After first train: heap=[910], max_platforms=1 Second train arrival=940, heap top=910 ≤ 940, pop 910 Push 1200, heap=[1200], max_platforms=max(1,1)=1 Since question asks after second train, max_platforms=1

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap size after second train is 1, max_platforms updated to 1 [OK]

Hint: Heap pops departures ≤ arrival before push [OK]

Common Mistakes:

• Not popping from heap before push
• Confusing max_platforms update timing
• Off-by-one in iteration

4. What is the time complexity of the optimal greedy solution that sorts the greed and cookie arrays before assigning cookies to children?

medium

A. O(n + m) because sorting is not needed if arrays are scanned directly

B. O(n * m) where n is number of children and m is number of cookies

C. O(n log n + m log m) due to sorting both arrays, then O(n + m) for assignment

D. O(n^2) because each child is compared to all cookies in worst case

Solution

1. Step 1: Identify sorting costs

   Sorting greed array of size n costs O(n log n), sorting cookies array of size m costs O(m log m).

2. Step 2: Analyze assignment loop

   Two pointers scan both arrays once, costing O(n + m).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting dominates complexity, linear scan is minor [OK]

Hint: Sorting dominates; assignment is linear [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Ignoring sorting cost
• Confusing linear scan with quadratic

5. Suppose now you can reuse boxes infinitely (unlimited supply of each box type). Which modification to the algorithm correctly computes the maximum units that can be loaded on the truck?

hard

A. Use dynamic programming to consider all combinations of boxes up to truckSize, since greedy no longer works

B. Use the same greedy approach but do not reduce truckSize after picking boxes, since supply is unlimited

C. Sort boxTypes by units per box descending and fill the truck entirely with the box type having the highest units per box

D. Sort boxTypes ascending by units per box and pick boxes until truckSize is full

Solution

1. Step 1: Understand unlimited supply impact

   With infinite boxes, the best strategy is to fill the truck entirely with the box type having the highest units per box.

2. Step 2: Identify correct algorithm

   Sorting descending by units per box and taking all truckSize boxes from the top box type yields maximum units efficiently.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Greedy fill with highest unit box type maximizes units [OK]

Hint: With infinite supply, pick only highest unit box type [OK]

Common Mistakes:

• Not reducing truckSize leading to infinite loop
• Using DP unnecessarily
• Sorting ascending which is suboptimal