Minimum Domino Rotations

🎯

Minimum Domino Rotations

mediumGREEDYAmazonGoogleFacebook

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?

💡 This problem is a classic greedy challenge where beginners often struggle to identify the right candidate values to check and how to efficiently count rotations. It requires understanding that only certain target values can possibly unify the row, and checking those candidates carefully.

📋

Problem Statement

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

💡

Example

Input"A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]"

Output2

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

Input"A = [3,5,1,2,3], B = [3,6,3,3,4]"

Output-1

No way to make all values in A or B the same by rotations.

• All dominoes already have the same number on top → output 0
• All dominoes have the same number on bottom → output 0
• Only one domino → output 0
• No possible number can unify top or bottom → output -1

⚠️

Common Mistakes

Checking all numbers 1 to 6 without early break

Unnecessary computation and slower runtime

✅ Only check candidates from first domino

Not handling the case when A[i] and B[i] both equal candidate

Incorrect rotation count, possibly overcounting

✅ Count rotations only when side differs from candidate

Returning 0 rotations without verifying all dominoes

Incorrect answer if some dominoes can't be unified

✅ Verify all dominoes before returning 0

Not returning -1 when no candidate works

Incorrect positive answer or runtime error

✅ Return -1 explicitly if no candidate is feasible

🧠

Brute Force (Check All Possible Numbers)

💡 This approach tries every possible number from 1 to 6 as the target and counts rotations needed. It is straightforward and helps understand the problem constraints and feasibility checks.

Intuition

Since domino numbers range from 1 to 6, try each number as the target to unify either top or bottom. For each candidate, check if all dominoes can be rotated to have that number on top or bottom, counting rotations.

Algorithm

1. For each number from 1 to 6:
2. Initialize rotation counts for making all tops or all bottoms equal to this number.
3. Iterate through all dominoes:
4. If neither top nor bottom has the candidate number, break and discard this candidate.
5. Otherwise, count rotations needed to make all tops or all bottoms equal to candidate.
6. Return the minimum rotations among all candidates or -1 if none possible.

💡 The nested loops and multiple candidate checks make this approach easy to understand but inefficient for large inputs.

</>

Code

def minDominoRotations(A, B):
    n = len(A)
    min_rotations = float('inf')
    for target in range(1, 7):
        rotations_a = 0
        rotations_b = 0
        for i in range(n):
            if A[i] != target and B[i] != target:
                break
            elif A[i] != target:
                rotations_a += 1
            elif B[i] != target:
                rotations_b += 1
        else:
            min_rotations = min(min_rotations, rotations_a, rotations_b)
    return min_rotations if min_rotations != float('inf') else -1

# Driver code
if __name__ == '__main__':
    A = [2,1,2,4,2,2]
    B = [5,2,6,2,3,2]
    print(minDominoRotations(A, B))  # Output: 2

Line Notes

for target in range(1, 7):Try each possible number from 1 to 6 as the candidate target

if A[i] != target and B[i] != target:If neither side has the target, this candidate is invalid

rotations_a += 1Count rotation needed to make top equal to target

rotations_b += 1Count rotation needed to make bottom equal to target

else:Executed only if loop wasn't broken, meaning candidate is valid

return min_rotations if min_rotations != float('inf') else -1Return minimum rotations found or -1 if none

public class Solution {
    public int minDominoRotations(int[] A, int[] B) {
        int n = A.length;
        int minRotations = Integer.MAX_VALUE;
        for (int target = 1; target <= 6; target++) {
            int rotationsA = 0, rotationsB = 0;
            boolean possible = true;
            for (int i = 0; i < n; i++) {
                if (A[i] != target && B[i] != target) {
                    possible = false;
                    break;
                } else if (A[i] != target) {
                    rotationsA++;
                } else if (B[i] != target) {
                    rotationsB++;
                }
            }
            if (possible) {
                minRotations = Math.min(minRotations, Math.min(rotationsA, rotationsB));
            }
        }
        return minRotations == Integer.MAX_VALUE ? -1 : minRotations;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] A = {2,1,2,4,2,2};
        int[] B = {5,2,6,2,3,2};
        System.out.println(sol.minDominoRotations(A, B)); // Output: 2
    }
}

Line Notes

for (int target = 1; target <= 6; target++) {Try each candidate number from 1 to 6

if (A[i] != target && B[i] != target) {If neither side matches target, candidate invalid

rotationsA++;Count rotations needed to make top equal target

rotationsB++;Count rotations needed to make bottom equal target

if (possible) {Update minimum rotations if candidate feasible

return minRotations == Integer.MAX_VALUE ? -1 : minRotations;Return result or -1 if impossible

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minDominoRotations(vector<int>& A, vector<int>& B) {
    int n = A.size();
    int minRotations = INT_MAX;
    for (int target = 1; target <= 6; target++) {
        int rotationsA = 0, rotationsB = 0;
        bool possible = true;
        for (int i = 0; i < n; i++) {
            if (A[i] != target && B[i] != target) {
                possible = false;
                break;
            } else if (A[i] != target) {
                rotationsA++;
            } else if (B[i] != target) {
                rotationsB++;
            }
        }
        if (possible) {
            minRotations = min(minRotations, min(rotationsA, rotationsB));
        }
    }
    return minRotations == INT_MAX ? -1 : minRotations;
}

int main() {
    vector<int> A = {2,1,2,4,2,2};
    vector<int> B = {5,2,6,2,3,2};
    cout << minDominoRotations(A, B) << endl; // Output: 2
    return 0;
}

Line Notes

for (int target = 1; target <= 6; target++) {Check each possible target number

if (A[i] != target && B[i] != target) {If neither side matches target, candidate invalid

rotationsA++;Count rotations to make top equal target

rotationsB++;Count rotations to make bottom equal target

if (possible) {Update minimum rotations if candidate feasible

return minRotations == INT_MAX ? -1 : minRotations;Return minimum rotations or -1 if impossible

var minDominoRotations = function(A, B) {
    const n = A.length;
    let minRotations = Infinity;
    for (let target = 1; target <= 6; target++) {
        let rotationsA = 0, rotationsB = 0;
        let possible = true;
        for (let i = 0; i < n; i++) {
            if (A[i] !== target && B[i] !== target) {
                possible = false;
                break;
            } else if (A[i] !== target) {
                rotationsA++;
            } else if (B[i] !== target) {
                rotationsB++;
            }
        }
        if (possible) {
            minRotations = Math.min(minRotations, Math.min(rotationsA, rotationsB));
        }
    }
    return minRotations === Infinity ? -1 : minRotations;
};

// Test
const A = [2,1,2,4,2,2];
const B = [5,2,6,2,3,2];
console.log(minDominoRotations(A, B)); // Output: 2

Line Notes

for (let target = 1; target <= 6; target++) {Try each candidate number from 1 to 6

if (A[i] !== target && B[i] !== target) {If neither side matches target, candidate invalid

rotationsA++;Count rotations needed to make top equal target

rotationsB++;Count rotations needed to make bottom equal target

if (possible) {Update minimum rotations if candidate feasible

return minRotations === Infinity ? -1 : minRotations;Return minimum rotations or -1 if impossible

⏱

Complexity

TimeO(6 * n)

SpaceO(1)

We try 6 candidates and for each candidate iterate over n dominoes once, so total O(6n) = O(n). Space is constant as only counters are used.

💡 For n=100,000, this means about 600,000 operations, which is efficient enough for interviews.

Interview Verdict: Accepted

Though not the most optimal, this approach is efficient enough and easy to implement, making it a good baseline solution.

🧠

Optimized Greedy (Check Only Two Candidates)

💡 This approach leverages the insight that only the numbers on the first domino can be the candidates to unify the row, reducing checks from 6 to 2 candidates.

Intuition

Since the final uniform number must appear on every domino's top or bottom, it must be either A[0] or B[0]. Check only these two candidates to minimize rotations.

Algorithm

1. Set candidates as A[0] and B[0].
2. For each candidate:
3. Iterate through all dominoes:
4. If neither side has candidate, discard candidate.
5. Count rotations needed to make all tops or all bottoms equal to candidate.
6. Return minimum rotations among candidates or -1 if none.

💡 This reduces unnecessary checks and speeds up the solution while preserving correctness.

</>

Code

def minDominoRotations(A, B):
    def check(x):
        rotations_a = rotations_b = 0
        for i in range(len(A)):
            if A[i] != x and B[i] != x:
                return float('inf')
            elif A[i] != x:
                rotations_a += 1
            elif B[i] != x:
                rotations_b += 1
        return min(rotations_a, rotations_b)

    rotations = min(check(A[0]), check(B[0]))
    return rotations if rotations != float('inf') else -1

# Driver code
if __name__ == '__main__':
    A = [2,1,2,4,2,2]
    B = [5,2,6,2,3,2]
    print(minDominoRotations(A, B))  # Output: 2

Line Notes

def check(x):Helper function to count rotations for candidate x

if A[i] != x and B[i] != x:If neither side matches candidate, no solution for x

rotations_a += 1Count rotations to make top equal candidate

rotations_b += 1Count rotations to make bottom equal candidate

return min(rotations_a, rotations_b)Return minimal rotations for candidate x

rotations = min(check(A[0]), check(B[0]))Check only two candidates from first domino

return rotations if rotations != float('inf') else -1Return result or -1 if impossible

public class Solution {
    public int minDominoRotations(int[] A, int[] B) {
        int rotationsA = check(A[0], A, B);
        int rotationsB = check(B[0], A, B);
        int rotations = Math.min(rotationsA, rotationsB);
        return rotations == Integer.MAX_VALUE ? -1 : rotations;
    }

    private int check(int x, int[] A, int[] B) {
        int rotationsA = 0, rotationsB = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] != x && B[i] != x) return Integer.MAX_VALUE;
            else if (A[i] != x) rotationsA++;
            else if (B[i] != x) rotationsB++;
        }
        return Math.min(rotationsA, rotationsB);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] A = {2,1,2,4,2,2};
        int[] B = {5,2,6,2,3,2};
        System.out.println(sol.minDominoRotations(A, B)); // Output: 2
    }
}

Line Notes

int rotationsA = check(A[0], A, B);Check rotations for candidate A[0]

int rotationsB = check(B[0], A, B);Check rotations for candidate B[0]

if (A[i] != x && B[i] != x) return Integer.MAX_VALUE;No solution if neither side matches candidate

rotationsA++;Count rotations to make top equal candidate

rotationsB++;Count rotations to make bottom equal candidate

return Math.min(rotationsA, rotationsB);Return minimal rotations for candidate

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int check(int x, vector<int>& A, vector<int>& B) {
    int rotationsA = 0, rotationsB = 0;
    for (int i = 0; i < A.size(); i++) {
        if (A[i] != x && B[i] != x) return INT_MAX;
        else if (A[i] != x) rotationsA++;
        else if (B[i] != x) rotationsB++;
    }
    return min(rotationsA, rotationsB);
}

int minDominoRotations(vector<int>& A, vector<int>& B) {
    int rotations = min(check(A[0], A, B), check(B[0], A, B));
    return rotations == INT_MAX ? -1 : rotations;
}

int main() {
    vector<int> A = {2,1,2,4,2,2};
    vector<int> B = {5,2,6,2,3,2};
    cout << minDominoRotations(A, B) << endl; // Output: 2
    return 0;
}

Line Notes

int rotations = min(check(A[0], A, B), check(B[0], A, B));Check only two candidates from first domino

if (A[i] != x && B[i] != x) return INT_MAX;No solution if neither side matches candidate

rotationsA++;Count rotations to make top equal candidate

rotationsB++;Count rotations to make bottom equal candidate

return min(rotationsA, rotationsB);Return minimal rotations for candidate

var minDominoRotations = function(A, B) {
    const check = (x) => {
        let rotationsA = 0, rotationsB = 0;
        for (let i = 0; i < A.length; i++) {
            if (A[i] !== x && B[i] !== x) return Infinity;
            else if (A[i] !== x) rotationsA++;
            else if (B[i] !== x) rotationsB++;
        }
        return Math.min(rotationsA, rotationsB);
    };
    const rotations = Math.min(check(A[0]), check(B[0]));
    return rotations === Infinity ? -1 : rotations;
};

// Test
const A = [2,1,2,4,2,2];
const B = [5,2,6,2,3,2];
console.log(minDominoRotations(A, B)); // Output: 2

Line Notes

const check = (x) => {Helper function to count rotations for candidate x

if (A[i] !== x && B[i] !== x) return Infinity;No solution if neither side matches candidate

rotationsA++;Count rotations to make top equal candidate

rotationsB++;Count rotations to make bottom equal candidate

const rotations = Math.min(check(A[0]), check(B[0]));Check only two candidates from first domino

return rotations === Infinity ? -1 : rotations;Return result or -1 if impossible

⏱

Complexity

TimeO(n)

SpaceO(1)

Only two candidates checked, each requiring one pass over n dominoes, so O(2n) = O(n). Space is constant.

💡 For n=100,000, this means about 200,000 operations, faster than brute force.

Interview Verdict: Accepted

This is the preferred approach in interviews due to its efficiency and simplicity.

🧠

Single Pass Counting with Early Exit

💡 This approach combines candidate checking and counting rotations in a single pass with early termination to improve runtime in practice.

Intuition

Track counts of how many dominoes already have the candidate number on top or bottom, and how many rotations are needed. If at any point a domino cannot be made to match candidate, stop early.

Algorithm

1. Set candidates as A[0] and B[0].
2. For each candidate:
3. Initialize rotation counts and feasibility flag.
4. Iterate through dominoes:
5. If domino can't match candidate, break early.
6. Otherwise, update rotation counts.
7. Return minimum rotations or -1 if impossible.

💡 Early exit reduces unnecessary work when candidate is invalid, improving average runtime.

</>

Code

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

    rotations = check(A[0])
    if rotations != -1:
        return rotations
    else:
        return check(B[0])

# Driver code
if __name__ == '__main__':
    A = [2,1,2,4,2,2]
    B = [5,2,6,2,3,2]
    print(minDominoRotations(A, B))  # Output: 2

Line Notes

if A[i] != x and B[i] != x:Early exit if domino can't match candidate

rotations_a += 1Count rotations to make top equal candidate

rotations_b += 1Count rotations to make bottom equal candidate

return min(rotations_a, rotations_b)Return minimal rotations if candidate feasible

rotations = check(A[0])Check first candidate

if rotations != -1:Return if first candidate feasible, else check second

public class Solution {
    public int minDominoRotations(int[] A, int[] B) {
        int rotations = check(A[0], A, B);
        if (rotations != -1) return rotations;
        return check(B[0], A, B);
    }

    private int check(int x, int[] A, int[] B) {
        int rotationsA = 0, rotationsB = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] != x && B[i] != x) return -1;
            else if (A[i] != x) rotationsA++;
            else if (B[i] != x) rotationsB++;
        }
        return Math.min(rotationsA, rotationsB);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] A = {2,1,2,4,2,2};
        int[] B = {5,2,6,2,3,2};
        System.out.println(sol.minDominoRotations(A, B)); // Output: 2
    }
}

Line Notes

if (A[i] != x && B[i] != x) return -1;Early exit if domino can't match candidate

rotationsA++;Count rotations to make top equal candidate

rotationsB++;Count rotations to make bottom equal candidate

return Math.min(rotationsA, rotationsB);Return minimal rotations if candidate feasible

int rotations = check(A[0], A, B);Check first candidate

if (rotations != -1) return rotations;Return if first candidate feasible, else check second

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int check(int x, vector<int>& A, vector<int>& B) {
    int rotationsA = 0, rotationsB = 0;
    for (int i = 0; i < A.size(); i++) {
        if (A[i] != x && B[i] != x) return -1;
        else if (A[i] != x) rotationsA++;
        else if (B[i] != x) rotationsB++;
    }
    return min(rotationsA, rotationsB);
}

int minDominoRotations(vector<int>& A, vector<int>& B) {
    int rotations = check(A[0], A, B);
    if (rotations != -1) return rotations;
    return check(B[0], A, B);
}

int main() {
    vector<int> A = {2,1,2,4,2,2};
    vector<int> B = {5,2,6,2,3,2};
    cout << minDominoRotations(A, B) << endl; // Output: 2
    return 0;
}

Line Notes

if (A[i] != x && B[i] != x) return -1;Early exit if domino can't match candidate

rotationsA++;Count rotations to make top equal candidate

rotationsB++;Count rotations to make bottom equal candidate

return min(rotationsA, rotationsB);Return minimal rotations if candidate feasible

int rotations = check(A[0], A, B);Check first candidate

if (rotations != -1) return rotations;Return if first candidate feasible, else check second

var minDominoRotations = function(A, B) {
    const check = (x) => {
        let rotationsA = 0, rotationsB = 0;
        for (let i = 0; i < A.length; i++) {
            if (A[i] !== x && B[i] !== x) return -1;
            else if (A[i] !== x) rotationsA++;
            else if (B[i] !== x) rotationsB++;
        }
        return Math.min(rotationsA, rotationsB);
    };
    let rotations = check(A[0]);
    if (rotations !== -1) return rotations;
    return check(B[0]);
};

// Test
const A = [2,1,2,4,2,2];
const B = [5,2,6,2,3,2];
console.log(minDominoRotations(A, B)); // Output: 2

Line Notes

if (A[i] !== x && B[i] !== x) return -1;Early exit if domino can't match candidate

rotationsA++;Count rotations to make top equal candidate

rotationsB++;Count rotations to make bottom equal candidate

return Math.min(rotationsA, rotationsB);Return minimal rotations if candidate feasible

let rotations = check(A[0]);Check first candidate

if (rotations !== -1) return rotations;Return if first candidate feasible, else check second

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass per candidate with early exit reduces average runtime but worst case remains O(n). Space is constant.

💡 Early breaks help in practice, especially when invalid candidates appear early.

Interview Verdict: Accepted

This approach is a practical optimization of the previous method, often preferred in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, use the optimized greedy approach checking only two candidates with early exit for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Check All Numbers 1-6)	O(6n) = O(n)	O(1)	No	N/A	Mention only - demonstrates understanding but inefficient
2. Optimized Greedy (Check Two Candidates)	O(n)	O(1)	No	N/A	Preferred approach to code in interviews
3. Single Pass with Early Exit	O(n) average, worst O(n)	O(1)	No	N/A	Good practical optimization, mention if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding. Next, present the optimized greedy solution and finally discuss edge cases and testing.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach checking all numbers 1 to 6.Step 3: Explain the optimization to check only the two candidates from the first domino.Step 4: Implement the optimized solution with early exit.Step 5: Test with edge cases and discuss complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to identify candidate values, count rotations correctly, optimize checks, and handle edge cases efficiently.

Common Follow-ups

• What if domino values are not limited to 1-6? → Use a hash map or set to find candidates.
• Can you do it in one pass? → Yes, by combining checks and counts with early breaks.

💡 These follow-ups test your ability to generalize and optimize your solution beyond the basic constraints.

🔍

Pattern Recognition

When to Use

1) Problem involves making all elements equal by minimal operations; 2) Limited candidate values; 3) Operations can be counted greedily; 4) Feasibility depends on candidate presence in all elements.

Signature Phrases

'minimum number of rotations''make all values in A or B the same'

NOT This Pattern When

Problems requiring dynamic programming or backtracking for complex state transitions

Similar Problems

Minimum Swaps To Make Sequences Increasing - similar candidate checking and counting swapsFlip String to Monotone Increasing - counting minimal flips to unify stringMinimum Number of Arrows to Burst Balloons - greedy coverage and counting

Practice

1. You are given an array where each element represents the maximum jump length from that position. You need to determine if you can reach the last index starting from the first index. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Dynamic Programming with bottom-up tabulation to check reachability for each index

B. Breadth-first search using a queue to explore reachable indices level by level

C. Depth-first search exploring all possible jump paths recursively without memoization

D. Greedy algorithm tracking the maximum reachable index while iterating through the array

Solution

1. Step 1: Understand problem constraints

   The problem requires checking if the last index is reachable from the first index using jumps defined by array values.

2. Step 2: Identify optimal approach

   Greedy approach efficiently tracks the furthest reachable index in one pass, guaranteeing O(n) time complexity, unlike exhaustive search or DP which are slower.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy approach is linear and optimal for this problem [OK]

Hint: Greedy tracks max reachable index in one pass [OK]

Common Mistakes:

• Confusing DP with greedy, thinking recursion is needed

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

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

4. What is the time complexity of the optimal min-heap based algorithm to find the minimum cost to connect n sticks, and why?

medium

A. O(n log n) because each of the n-1 merges involves two heap pops and one push, each O(log n)

B. O(n log k) where k is the maximum stick length, due to heapifying by stick size

C. O(n) because heap operations are constant time on average

D. O(n^2) because each merge requires scanning all sticks

Solution

1. Step 1: Identify number of operations

   There are n sticks, so n-1 merges are needed.

2. Step 2: Analyze heap operations per merge

   Each merge requires two pops and one push on a min-heap, each operation O(log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   (n-1) merges x 3 heap ops x O(log n) -> O(n log n) [OK]

Hint: Heap operations cost O(log n) each, repeated n times [OK]

Common Mistakes:

• Assuming heap operations are O(1) average
• Confusing n with maximum stick length k
• Thinking merges scan all sticks leading to O(n^2)

5. The following code attempts to find the largest monotone increasing digits number less than or equal to n. Identify the bug that causes incorrect results on some inputs.

def monotoneIncreasingDigits(n: int) -> int:
    digits = list(map(int, str(n)))
    marker = len(digits)
    for i in range(len(digits) - 1, 0, -1):
        if digits[i] < digits[i - 1]:
            digits[i - 1] -= 1
            marker = i
    return int(''.join(map(str, digits)))

medium

A. The code does not set digits after the marker to 9, missing the largest monotone number

B. The code decrements digits[i - 1] without checking if it causes new violations earlier

C. The code converts digits back to integer before fixing all digits, causing runtime errors

D. The code ignores the case when all digits are equal, returning incorrect output

Solution

1. Step 1: Analyze the loop effect

   The loop decrements digits[i - 1] when a violation is found and updates marker, but does not fix digits after marker.

2. Step 2: Identify missing step to set trailing digits to 9

   Without setting digits from marker to end to 9, the number may not be the largest monotone number ≤ n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing trailing digit fix leads to smaller-than-necessary result [OK]

Hint: Always set trailing digits to 9 after decrement to maximize number [OK]

Common Mistakes:

• Forgetting to set trailing digits to 9
• Assuming one decrement fixes all violations
• Ignoring edge cases with equal digits