Minimum Domino Rotations

▶

Steps

setup

Initialize candidates from first domino

We select the two candidate values to check: A[0] = 2 and B[0] = 5. These are the only possible values that can fill the entire top or bottom row after rotations.

💡 Choosing candidates from the first domino limits the search space to only two values, making the algorithm efficient.

Line:

candidates = [A[0], B[0]]

💡 Only these two values can possibly fill the entire row after rotations.

setup

Start checking candidate 2

We begin checking if all dominoes can be rotated to have the value 2 on either top or bottom. Initialize rotation counts rotations_a and rotations_b to zero.

💡 Rotation counts track how many dominoes need to be flipped to get candidate 2 on top or bottom.

Line:

rotations_a = rotations_b = 0

💡 We prepare to count rotations needed for candidate 2.

compare

Check domino 0 for candidate 2

At index 0, top is 2 which matches candidate 2, so no rotation needed on top. Bottom is 5 which does not match candidate, so rotations_b increments by 1.

💡 If top matches candidate, rotations_a stays same; if bottom doesn't match, rotations_b increments.

Line:

if A[i] != x:
    rotations_a += 1
elif B[i] != x:
    rotations_b += 1

💡 We track rotations needed on each side to achieve uniform candidate value.

compare

Check domino 1 for candidate 2

At index 1, top is 1 which does not match candidate 2, bottom is 2 which matches candidate. So rotations_a increments by 1 because top needs rotation.

💡 If top doesn't match candidate but bottom does, increment rotations_a.

Line:

if A[i] != x:
    rotations_a += 1
elif B[i] != x:
    rotations_b += 1

💡 Rotation counts reflect how many dominoes need flipping on each side.

compare

Check domino 2 for candidate 2

At index 2, top is 2 which matches candidate, bottom is 6 which does not. rotations_b increments by 1.

💡 If top matches candidate, rotations_a stays same; if bottom doesn't match, rotations_b increments.

Line:

if A[i] != x:
    rotations_a += 1
elif B[i] != x:
    rotations_b += 1

💡 Rotation counts continue to track needed flips.

compare

Check domino 3 for candidate 2

At index 3, top is 4 and bottom is 2. Top does not match candidate, bottom matches, so rotations_a increments by 1.

💡 Increment rotations_a when top doesn't match but bottom does.

Line:

if A[i] != x:
    rotations_a += 1
elif B[i] != x:
    rotations_b += 1

💡 Rotation counts reflect flips needed on top side.

compare

Check domino 4 for candidate 2

At index 4, top is 2 matching candidate, bottom is 3 not matching. rotations_b increments by 1.

💡 Increment rotations_b when bottom doesn't match candidate but top does.

Line:

if A[i] != x:
    rotations_a += 1
elif B[i] != x:
    rotations_b += 1

💡 Rotation counts continue to accumulate needed flips.

compare

Check domino 5 for candidate 2

At index 5, top is 2 matching candidate, bottom is 2 matching candidate. No rotations needed for this domino.

💡 If both sides match candidate, no rotations needed.

Line:

if A[i] != x and B[i] != x:
    return -1
elif A[i] != x:
    rotations_a += 1
elif B[i] != x:
    rotations_b += 1

💡 Domino already matches candidate on both sides, no flips needed.

prune

Calculate minimum rotations for candidate 2

All dominoes can be rotated to candidate 2. Minimum rotations is the smaller of rotations_a (2) and rotations_b (3), which is 2.

💡 We pick the minimal rotations needed to make all dominoes show candidate 2 on one side.

Line:

return min(rotations_a, rotations_b)

💡 Minimum rotations is the answer if candidate is feasible.

prune

Return result without checking candidate 5

Since candidate 2 returned a valid rotation count (2), the algorithm returns 2 immediately without checking candidate 5.

💡 Early exit saves time by avoiding unnecessary checks.

Line:

if rotations != -1:
    return rotations

💡 Early exit optimizes performance by stopping once a solution is found.

def minDominoRotations(A, B):
    def check(x):
        rotations_a = rotations_b = 0  # STEP 2
        for i in range(len(A)):
            if A[i] != x and B[i] != x:
                return -1  # STEP 5
            elif A[i] != x:
                rotations_a += 1  # STEP 4-6
            elif B[i] != x:
                rotations_b += 1  # STEP 4-6
        return min(rotations_a, rotations_b)  # STEP 9

    rotations = check(A[0])  # STEP 1, 3
    if rotations != -1:  # STEP 10
        return rotations
    else:
        return check(B[0])

📊

Minimum Domino Rotations - Watch the Algorithm Execute, Step by Step

Watching each comparison and rotation count update helps you understand how the greedy approach efficiently finds the minimum rotations or detects failure early.

setup

candidate

2

0

1

1

2

2

4

3

2

4

2

5

setup

i

2

0

1

1

2

2

4

3

2

4

2

5

compare

i

2

0

1

1

2

2

4

3

2

4

2

5

Result: {"rotations_a":0,"rotations_b":1}

compare

candidate

2

0

i

1

1

2

2

4

3

2

4

2

5

Result: {"rotations_a":1,"rotations_b":1}

compare

candidate

2

0

1

1

i

2

2

4

3

2

4

2

5

Result: {"rotations_a":1,"rotations_b":2}

compare

candidate

2

0

1

1

2

2

i

4

3

2

4

2

5

Result: {"rotations_a":2,"rotations_b":2}

compare

candidate

2

0

1

1

2

2

4

3

i

2

4

2

5

Result: {"rotations_a":2,"rotations_b":3}

compare

candidate

2

0

1

1

2

2

4

3

2

4

i

2

5

Result: {"rotations_a":2,"rotations_b":3}

prune

candidate

2

0

1

1

2

2

4

3

2

4

2

5

Result: 2

prune

2

0

1

1

2

2

4

3

2

4

2

5

Result: 2

Key Takeaways

✓ The algorithm only needs to check two candidate values from the first domino to find a solution or determine impossibility.

This insight is hard to see from code alone because it’s not obvious why only two candidates suffice.

✓ Rotation counts track how many dominoes need flipping on top or bottom to achieve uniformity, enabling a greedy minimal rotation calculation.

Visualizing these counts clarifies how the algorithm accumulates necessary flips step-by-step.

✓ Early exit occurs as soon as a candidate yields a valid rotation count, avoiding unnecessary checks and improving efficiency.

Seeing the early return in action helps understand the algorithm’s optimization.

Practice

1. You have different types of boxes, each with a number of boxes and units per box. You want to load a truck with a limited capacity to maximize total units. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Divide and conquer by splitting box types and merging results

B. Greedy algorithm sorting box types by units per box in descending order and picking boxes until the truck is full

C. Breadth-first search exploring all possible box selections up to truck capacity

D. Dynamic programming considering all combinations of boxes and capacities

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing units loaded on a truck with limited capacity by selecting boxes with different units per box.

2. Step 2: Identify optimal approach

   Since the problem involves discrete box counts and a capacity constraint, the greedy approach does not always guarantee an optimal solution. Dynamic programming considering all combinations ensures the optimal solution by exploring all feasible selections.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP guarantees optimality for knapsack-like problems with discrete items [OK]

Hint: Use DP for discrete knapsack problems to guarantee optimality [OK]

Common Mistakes:

• Assuming greedy always works
• Trying BFS which is inefficient
• Ignoring capacity constraints

2. You are given a positive integer n. The task is to find the largest integer less than or equal to n such that its digits are in non-decreasing order from left to right. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Divide and conquer splitting the number into halves and solving recursively

B. Dynamic Programming that tries all digit combinations to build the largest monotone number

C. Brute force decrementing from n downwards checking monotonicity for each number

D. Greedy algorithm scanning digits from right to left, adjusting digits and setting trailing digits to 9

Solution

1. Step 1: Understand the problem constraints

   The problem requires the largest number ≤ n with digits in non-decreasing order, which suggests a digit-wise adjustment rather than enumerating all numbers.

2. Step 2: Identify the approach that efficiently fixes digits from right to left

   The greedy right-to-left scan decreases digits when a violation is found and sets subsequent digits to 9, ensuring the largest monotone number ≤ n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy right-to-left fix is optimal and efficient [OK]

Hint: Greedy right-to-left digit fix ensures optimal monotone number [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Assuming DP is needed for digit monotonicity
• Believing divide and conquer applies here

3. What is the time complexity of the optimal two-pass greedy candy distribution algorithm for an input array of length n?

medium

A. O(n) because each pass scans the array once

B. O(n^2) due to nested loops in adjustment

C. O(n log n) due to sorting or priority queue usage

D. O(n) but with O(n) auxiliary space for candies array

Solution

1. Step 1: Identify loops in the algorithm

   Two separate passes over the array, each iterating from start to end or end to start once.

2. Step 2: Analyze complexity of each pass

   Each pass is O(n), no nested loops or sorting involved, so total time is O(n). Also, the candies array requires O(n) auxiliary space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two linear scans and O(n) space for candies array [OK]

Hint: Two linear passes -> O(n) time and O(n) space [OK]

Common Mistakes:

• Confusing repeated adjustment brute force with optimal approach
• Assuming sorting is needed
• Ignoring that passes are sequential, not nested

4. The following code attempts to form the largest number from a list of integers. Which line contains a subtle bug that causes incorrect output on inputs like [0, 0, 0]?

medium

A. Line 8: Returning concatenated string without zero check

B. Line 4-6: Custom comparator function

C. Line 7: Sorting with custom comparator

D. Line 3: Converting integers to strings

Solution

1. Step 1: Trace output for input [0,0,0]

   After sorting, nums_str is ['0', '0', '0'], concatenation is '000'.

2. Step 2: Identify missing check for all zeros

   Without checking if first element is '0', the function returns '000' instead of '0'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding a check to return '0' if nums_str[0] == '0' fixes the bug [OK]

Hint: Check if first string is '0' to handle all-zero case [OK]

Common Mistakes:

• Forgetting all-zero check
• Incorrect comparator logic
• Sorting without custom comparator

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