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 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. Given the following code for the Task Scheduler, what is the returned value for leastInterval(['A','A','B'], 2)?

easy

A. 3

B. 5

C. 6

D. 4

Solution

1. Step 1: Initialize frequencies and max-heap

   Tasks: A(2), B(1). Max-heap: [-2, -1].

2. Step 2: Simulate scheduling cycles

   Cycle 1: pop -2 (A), decrement to -1 and store; pop -1 (B), decrement to 0 ignore; cycle=2, heap not empty -> time += n+1=3.
   Cycle 2: pop -1 (A), decrement to 0 ignore; cycle=1, heap empty -> time += cycle=1.
   Total time = 3 + 1 = 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual simulation matches 4 units [OK]

Hint: Count cycles and add idle if heap not empty [OK]

Common Mistakes:

• Off-by-one in cycle count
• Adding n+1 even when heap empty
• Ignoring decrement of counts

3. The following code attempts to compute the minimum number of platforms needed. Identify the line containing the subtle bug that can cause incorrect platform count when a train arrives exactly at the departure time of another train.

medium

A. Line with 'while heap and heap[0] < arrival:'

B. Line with 'trains = sorted(zip(arrivals, departures), key=lambda x: x[0])'

C. Line with 'heapq.heappush(heap, departure)'

D. Line with 'max_platforms = max(max_platforms, len(heap))'

Solution

1. Step 1: Understand the bug

   The condition 'heap[0] < arrival' pops platforms only if departure is strictly less than arrival, missing the case when departure == arrival.

2. Step 2: Correct condition

   Changing condition to 'heap[0] <= arrival' correctly frees platforms when a train arrives exactly at departure time, avoiding overcounting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Condition must include equality to avoid platform overcount [OK]

Hint: Use <= to free platform when arrival equals departure [OK]

Common Mistakes:

• Using < instead of <= in heap pop condition
• Not sorting trains by arrival time
• Forgetting to update max_platforms

4. Suppose the problem changes: you can reuse indices multiple times (cycles allowed). Which modification to the BFS approach ensures correct minimum jumps without infinite loops?

hard

A. Remove the visited set to allow revisiting indices for better paths.

B. Keep the visited set but reset it after each BFS level to allow revisits in next level.

C. Keep the visited set as is to prevent revisiting and infinite loops.

D. Use a distance array to track minimum jumps to each index and update it if a shorter path is found.

Solution

1. Step 1: Understand cycles and revisits

   Allowing reuse means indices can be revisited, so visited set alone blocks better paths.

2. Step 2: Use distance array for shortest paths

   Tracking minimum jumps per index and updating when a shorter path is found prevents infinite loops and finds optimal jumps.

3. Step 3: Why other options fail

   Removing visited causes infinite loops; resetting visited loses pruning; keeping visited blocks revisits.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Distance array with updates handles cycles correctly [OK]

Hint: Distance array needed when revisits allowed [OK]

Common Mistakes:

• Removing visited set causing infinite loops
• Resetting visited incorrectly
• Assuming original BFS works unchanged

5. Suppose trains can arrive and depart multiple times (reusing platforms), or the station allows fractional arrival/departure times. Which modification to the min-heap approach correctly handles these cases?

hard

A. Use brute force nested loops to check all overlaps since fractional times break heap ordering

B. Sort arrivals and departures separately and use two pointers to count overlaps

C. Keep the min-heap but change the comparison to strictly less than (<) to handle fractional times

D. Use a balanced BST instead of a min-heap to handle fractional times and reuse efficiently

Solution

1. Step 1: Identify challenges with fractional and multiple reuse

   Fractional times and multiple reuse require precise ordering and efficient insertion/removal of intervals.

2. Step 2: Choose data structure

   A balanced BST supports ordered insertions, deletions, and queries with fractional keys better than a min-heap, which assumes discrete ordering.

3. Step 3: Why other options fail

   Two pointers fail with fractional times due to equality checks; changing comparison in heap breaks correctness; brute force is inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Balanced BST handles fractional and reuse efficiently [OK]

Hint: Balanced BST supports fractional keys and dynamic reuse [OK]

Common Mistakes:

• Assuming min-heap works unchanged with fractional times
• Using two pointers without handling fractional equality
• Resorting to brute force for efficiency