Asteroid Collision

🎯

Asteroid Collision

mediumSTACKAmazonGoogleBloomberg

Imagine a line of asteroids moving in space, some moving left and some moving right. When they collide, only the bigger one survives. Can you predict which asteroids remain after all collisions?

💡 This problem simulates collisions using a stack to track surviving asteroids. Beginners often struggle because the problem involves direction and size conditions that require careful simulation rather than straightforward iteration.

📋

Problem Statement

You are given an array of integers asteroids representing asteroids in a row. For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed. When two asteroids moving in opposite directions collide, the smaller one explodes. If both are the same size, both explode. Asteroids moving in the same direction will never collide. Return an array representing the state of the asteroids after all collisions.

1 ≤ asteroids.length ≤ 10^5-1000 ≤ asteroids[i] ≤ 1000asteroids[i] != 0

💡

Example

Input"[5, 10, -5]"

Output[5, 10]

The asteroid 10 and -5 collide, -5 explodes. 5 and 10 never collide.

Input"[8, -8]"

Output[]

Both asteroids are the same size but opposite directions, so both explode.

Input"[10, 2, -5]"

Output[10]

2 and -5 collide, 2 explodes. Then 10 and -5 collide, -5 explodes.

Input"[-2, -1, 1, 2]"

Output[-2, -1, 1, 2]

No collisions because asteroids moving left are on the left and those moving right are on the right.

• All asteroids moving in the same direction → output is the same as input
• All asteroids moving left → output is the same as input
• All asteroids moving right → output is the same as input
• Large number of asteroids with alternating directions and sizes → output depends on multiple collisions

⚠️

Common Mistakes

Not checking direction before collision

Incorrect collisions between asteroids moving in the same direction

✅ Only resolve collisions when a right-moving asteroid is followed by a left-moving asteroid

Not handling equal size asteroids correctly

Both asteroids survive or both explode incorrectly

✅ Remove both asteroids when sizes are equal during collision

Modifying list while iterating without adjusting index

Index errors or skipping elements

✅ Adjust index after removal or use a stack to avoid this problem

Using recursion or repeated scanning leading to TLE

Time limit exceeded on large inputs

✅ Use stack simulation for O(n) time complexity

🧠

Brute Force (Simulation with Nested Loops)

💡 This approach simulates collisions by repeatedly scanning the array and resolving collisions one by one. It is slow but helps understand the collision process clearly.

Intuition

Check every pair of adjacent asteroids moving towards each other and resolve their collision. Repeat until no collisions remain.

Algorithm

1. Start from the beginning of the array and look for adjacent asteroids moving towards each other (right then left).
2. When found, compare their sizes and remove the smaller one or both if equal.
3. Repeat the scan from the start until no collisions occur in a full pass.
4. Return the remaining asteroids.

💡 This algorithm is hard to see because it requires multiple passes and careful index management to simulate collisions correctly.

</>

Code

def asteroidCollision(asteroids):
    changed = True
    while changed:
        changed = False
        i = 0
        while i < len(asteroids) - 1:
            if asteroids[i] > 0 and asteroids[i+1] < 0:
                if abs(asteroids[i]) == abs(asteroids[i+1]):
                    asteroids.pop(i+1)
                    asteroids.pop(i)
                    changed = True
                    i = max(i-1, 0)
                elif abs(asteroids[i]) > abs(asteroids[i+1]):
                    asteroids.pop(i+1)
                    changed = True
                else:
                    asteroids.pop(i)
                    changed = True
                    i = max(i-1, 0)
            else:
                i += 1
    return asteroids

# Driver code
if __name__ == '__main__':
    print(asteroidCollision([5,10,-5]))  # Output: [5,10]

Line Notes

changed = TrueInitialize flag to track if any collision happened in the pass

while changed:Repeat until no collisions occur in a full pass

if asteroids[i] > 0 and asteroids[i+1] < 0:Check if adjacent asteroids are moving towards each other

asteroids.pop(i+1)Remove the smaller asteroid after collision

i = max(i-1, 0)Step back to re-check previous pairs after modification

import java.util.*;
public class Solution {
    public static int[] asteroidCollision(int[] asteroids) {
        List<Integer> list = new ArrayList<>();
        for (int a : asteroids) list.add(a);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < list.size() - 1; ) {
                int curr = list.get(i);
                int next = list.get(i + 1);
                if (curr > 0 && next < 0) {
                    if (Math.abs(curr) == Math.abs(next)) {
                        list.remove(i + 1);
                        list.remove(i);
                        changed = true;
                        i = Math.max(i - 1, 0);
                    } else if (Math.abs(curr) > Math.abs(next)) {
                        list.remove(i + 1);
                        changed = true;
                    } else {
                        list.remove(i);
                        changed = true;
                        i = Math.max(i - 1, 0);
                    }
                } else {
                    i++;
                }
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) res[i] = list.get(i);
        return res;
    }

    public static void main(String[] args) {
        int[] result = asteroidCollision(new int[]{5,10,-5});
        System.out.println(Arrays.toString(result)); // [5, 10]
    }
}

Line Notes

boolean changed = true;Flag to track if any collision happened in the current iteration

for (int i = 0; i < list.size() - 1; )Iterate through list to find collisions

if (curr > 0 && next < 0)Check if two adjacent asteroids are moving towards each other

list.remove(i + 1);Remove smaller asteroid after collision

i = Math.max(i - 1, 0);Step back to re-check previous pairs after modification

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

vector<int> asteroidCollision(vector<int>& asteroids) {
    bool changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < (int)asteroids.size() - 1;) {
            if (asteroids[i] > 0 && asteroids[i+1] < 0) {
                if (abs(asteroids[i]) == abs(asteroids[i+1])) {
                    asteroids.erase(asteroids.begin() + i + 1);
                    asteroids.erase(asteroids.begin() + i);
                    changed = true;
                    i = max(i - 1, 0);
                } else if (abs(asteroids[i]) > abs(asteroids[i+1])) {
                    asteroids.erase(asteroids.begin() + i + 1);
                    changed = true;
                } else {
                    asteroids.erase(asteroids.begin() + i);
                    changed = true;
                    i = max(i - 1, 0);
                }
            } else {
                i++;
            }
        }
    }
    return asteroids;
}

int main() {
    vector<int> asteroids = {5, 10, -5};
    vector<int> result = asteroidCollision(asteroids);
    for (int a : result) cout << a << " ";
    cout << endl; // Output: 5 10
    return 0;
}

Line Notes

bool changed = true;Flag to track if any collision happened in the current pass

for (int i = 0; i < (int)asteroids.size() - 1;)Iterate through asteroids to find collisions

if (asteroids[i] > 0 && asteroids[i+1] < 0)Check if adjacent asteroids are moving towards each other

asteroids.erase(asteroids.begin() + i + 1);Remove smaller asteroid after collision

i = max(i - 1, 0);Step back to re-check previous pairs after modification

function asteroidCollision(asteroids) {
    let changed = true;
    while (changed) {
        changed = false;
        let i = 0;
        while (i < asteroids.length - 1) {
            if (asteroids[i] > 0 && asteroids[i + 1] < 0) {
                if (Math.abs(asteroids[i]) === Math.abs(asteroids[i + 1])) {
                    asteroids.splice(i, 2);
                    changed = true;
                    i = Math.max(i - 1, 0);
                } else if (Math.abs(asteroids[i]) > Math.abs(asteroids[i + 1])) {
                    asteroids.splice(i + 1, 1);
                    changed = true;
                } else {
                    asteroids.splice(i, 1);
                    changed = true;
                    i = Math.max(i - 1, 0);
                }
            } else {
                i++;
            }
        }
    }
    return asteroids;
}

// Test
console.log(asteroidCollision([5,10,-5])); // [5, 10]

Line Notes

let changed = true;Flag to track if any collision happened in the current iteration

while (changed) {Repeat until no collisions occur in a full pass

if (asteroids[i] > 0 && asteroids[i + 1] < 0)Check if adjacent asteroids are moving towards each other

asteroids.splice(i, 2);Remove both asteroids if they are equal size

i = Math.max(i - 1, 0);Step back to re-check previous pairs after modification

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Each pass can remove at most one asteroid, and each pass scans the array, so worst case O(n^2).

💡 For n=20, this means up to 400 operations, which is inefficient for large inputs.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem mechanics.

🧠

Stack Simulation

💡 Using a stack to simulate the collisions efficiently is the standard approach. It avoids repeated scanning by maintaining only surviving asteroids.

Intuition

Push asteroids moving right onto the stack. When a left-moving asteroid arrives, resolve collisions with stack top until it either explodes or survives.

Algorithm

1. Initialize an empty stack.
2. Iterate over each asteroid:
3. If asteroid moves right (positive), push it onto the stack.
4. If asteroid moves left (negative), pop from stack while top is smaller and moving right, resolving collisions.
5. If the left-moving asteroid survives, push it onto the stack.
6. Return the stack as the final state.

💡 This algorithm is easier to understand once you see the stack as a container of surviving right-moving asteroids.

</>

Code

def asteroidCollision(asteroids):
    stack = []
    for a in asteroids:
        while stack and a < 0 < stack[-1]:
            if stack[-1] < -a:
                stack.pop()
                continue
            elif stack[-1] == -a:
                stack.pop()
            break
        else:
            stack.append(a)
    return stack

# Driver code
if __name__ == '__main__':
    print(asteroidCollision([5,10,-5]))  # Output: [5, 10]

Line Notes

stack = []Initialize stack to keep surviving asteroids

for a in asteroids:Process each asteroid in order

while stack and a < 0 < stack[-1]:Resolve collisions only when current asteroid moves left and stack top moves right

if stack[-1] < -a:If top asteroid is smaller, it explodes (pop)

else: stack.append(a)If current asteroid survives, add it to stack

import java.util.*;
public class Solution {
    public static int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int a : asteroids) {
            collision: {
                while (!stack.isEmpty() && a < 0 && stack.peek() > 0) {
                    if (stack.peek() < -a) {
                        stack.pop();
                        continue;
                    } else if (stack.peek() == -a) {
                        stack.pop();
                    }
                    break collision;
                }
                stack.push(a);
            }
        }
        int[] res = new int[stack.size()];
        for (int i = res.length - 1; i >= 0; i--) res[i] = stack.pop();
        return res;
    }

    public static void main(String[] args) {
        int[] result = asteroidCollision(new int[]{5,10,-5});
        System.out.println(Arrays.toString(result)); // [5, 10]
    }
}

Line Notes

Stack<Integer> stack = new Stack<>();Stack to hold surviving asteroids

for (int a : asteroids)Iterate over each asteroid

while (!stack.isEmpty() && a < 0 && stack.peek() > 0)Resolve collisions when current asteroid moves left and stack top moves right

if (stack.peek() < -a)Pop smaller asteroid from stack

stack.push(a);Push current asteroid if it survives collisions

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

vector<int> asteroidCollision(vector<int>& asteroids) {
    stack<int> st;
    for (int a : asteroids) {
        bool alive = true;
        while (!st.empty() && a < 0 && st.top() > 0) {
            if (st.top() < -a) {
                st.pop();
                continue;
            } else if (st.top() == -a) {
                st.pop();
            }
            alive = false;
            break;
        }
        if (alive) st.push(a);
    }
    vector<int> res(st.size());
    for (int i = (int)st.size() - 1; i >= 0; i--) {
        res[i] = st.top();
        st.pop();
    }
    return res;
}

int main() {
    vector<int> asteroids = {5, 10, -5};
    vector<int> result = asteroidCollision(asteroids);
    for (int a : result) cout << a << " ";
    cout << endl; // Output: 5 10
    return 0;
}

Line Notes

stack<int> st;Stack to hold surviving asteroids

for (int a : asteroids)Process each asteroid in order

while (!st.empty() && a < 0 && st.top() > 0)Resolve collisions when current asteroid moves left and top moves right

if (st.top() < -a)Pop smaller asteroid from stack

if (alive) st.push(a);Push current asteroid if it survives collisions

function asteroidCollision(asteroids) {
    const stack = [];
    for (const a of asteroids) {
        let alive = true;
        while (alive && stack.length && a < 0 && stack[stack.length - 1] > 0) {
            if (stack[stack.length - 1] < -a) {
                stack.pop();
            } else if (stack[stack.length - 1] === -a) {
                stack.pop();
                alive = false;
            } else {
                alive = false;
            }
        }
        if (alive) stack.push(a);
    }
    return stack;
}

// Test
console.log(asteroidCollision([5,10,-5])); // [5, 10]

Line Notes

const stack = [];Stack to keep surviving asteroids

for (const a of asteroids)Iterate over each asteroid

while (alive && stack.length && a < 0 && stack[stack.length - 1] > 0)Resolve collisions when current asteroid moves left and stack top moves right

stack.pop();Remove smaller asteroid from stack

if (alive) stack.push(a);Push current asteroid if it survives collisions

⏱

Complexity

TimeO(n)

SpaceO(n)

Each asteroid is pushed and popped at most once, so linear time and space.

💡 For n=20, this means roughly 20 pushes and pops, very efficient.

Interview Verdict: Accepted

This is the standard efficient solution accepted in interviews.

🧠

Optimized Stack Simulation with Early Break

💡 This approach is a slight refinement of the stack simulation that uses labeled breaks or flags to improve readability and control flow.

Intuition

Use a flag or labeled break to exit collision resolution early when the current asteroid explodes or both explode.

Algorithm

1. Initialize an empty stack.
2. For each asteroid, check collisions with stack top while conditions hold.
3. Use a flag or labeled break to exit collision loop when asteroid explodes or both explode.
4. Push surviving asteroids onto the stack.
5. Return the stack as the final state.

💡 This approach improves code clarity without changing the core logic.

</>

Code

def asteroidCollision(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        while alive and stack and stack[-1] > 0 and a < 0:
            if stack[-1] < -a:
                stack.pop()
            elif stack[-1] == -a:
                stack.pop()
                alive = False
            else:
                alive = False
        if alive:
            stack.append(a)
    return stack

# Driver code
if __name__ == '__main__':
    print(asteroidCollision([5,10,-5]))  # Output: [5, 10]

Line Notes

alive = TrueFlag to track if current asteroid survives collisions

while alive and stack and stack[-1] > 0 and a < 0:Resolve collisions only when conditions for collision hold

if stack[-1] < -a:Pop smaller asteroid from stack

elif stack[-1] == -a:Pop equal asteroid and mark current as exploded

if alive: stack.append(a)Push current asteroid if it survives

import java.util.*;
public class Solution {
    public static int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int a : asteroids) {
            boolean alive = true;
            while (alive && !stack.isEmpty() && stack.peek() > 0 && a < 0) {
                if (stack.peek() < -a) {
                    stack.pop();
                } else if (stack.peek() == -a) {
                    stack.pop();
                    alive = false;
                } else {
                    alive = false;
                }
            }
            if (alive) stack.push(a);
        }
        int[] res = new int[stack.size()];
        for (int i = res.length - 1; i >= 0; i--) res[i] = stack.pop();
        return res;
    }

    public static void main(String[] args) {
        int[] result = asteroidCollision(new int[]{5,10,-5});
        System.out.println(Arrays.toString(result)); // [5, 10]
    }
}

Line Notes

boolean alive = true;Flag to track if current asteroid survives collisions

while (alive && !stack.isEmpty() && stack.peek() > 0 && a < 0)Resolve collisions only when conditions hold

if (stack.peek() < -a)Pop smaller asteroid from stack

else if (stack.peek() == -a)Pop equal asteroid and mark current as exploded

if (alive) stack.push(a);Push current asteroid if it survives

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

vector<int> asteroidCollision(vector<int>& asteroids) {
    stack<int> st;
    for (int a : asteroids) {
        bool alive = true;
        while (alive && !st.empty() && st.top() > 0 && a < 0) {
            if (st.top() < -a) {
                st.pop();
            } else if (st.top() == -a) {
                st.pop();
                alive = false;
            } else {
                alive = false;
            }
        }
        if (alive) st.push(a);
    }
    vector<int> res(st.size());
    for (int i = (int)st.size() - 1; i >= 0; i--) {
        res[i] = st.top();
        st.pop();
    }
    return res;
}

int main() {
    vector<int> asteroids = {5, 10, -5};
    vector<int> result = asteroidCollision(asteroids);
    for (int a : result) cout << a << " ";
    cout << endl; // Output: 5 10
    return 0;
}

Line Notes

bool alive = true;Flag to track if current asteroid survives collisions

while (alive && !st.empty() && st.top() > 0 && a < 0)Resolve collisions only when conditions hold

if (st.top() < -a)Pop smaller asteroid from stack

else if (st.top() == -a)Pop equal asteroid and mark current as exploded

if (alive) st.push(a);Push current asteroid if it survives

function asteroidCollision(asteroids) {
    const stack = [];
    for (const a of asteroids) {
        let alive = true;
        while (alive && stack.length && stack[stack.length - 1] > 0 && a < 0) {
            if (stack[stack.length - 1] < -a) {
                stack.pop();
            } else if (stack[stack.length - 1] === -a) {
                stack.pop();
                alive = false;
            } else {
                alive = false;
            }
        }
        if (alive) stack.push(a);
    }
    return stack;
}

// Test
console.log(asteroidCollision([5,10,-5])); // [5, 10]

Line Notes

let alive = true;Flag to track if current asteroid survives collisions

while (alive && stack.length && stack[stack.length - 1] > 0 && a < 0)Resolve collisions only when conditions hold

stack.pop();Remove smaller asteroid from stack

alive = false;Mark current asteroid as exploded

if (alive) stack.push(a);Push current asteroid if it survives

⏱

Complexity

TimeO(n)

SpaceO(n)

Each asteroid is pushed and popped at most once, so linear time and space.

💡 This approach is as efficient as the previous stack simulation but clearer to read.

Interview Verdict: Accepted

This approach is preferred for clarity and maintainability in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 The stack simulation approach is the best to code in interviews due to its clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code
2. Stack Simulation	O(n)	O(n)	No	N/A	Code this approach
3. Optimized Stack Simulation	O(n)	O(n)	No	N/A	Code for clarity and maintainability

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem.Introduce the stack simulation approach as an efficient solution.Write clean, well-commented code for the stack approach.Test your code with sample and edge cases.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your ability to simulate collisions correctly, optimize with a stack, and handle edge cases and large inputs efficiently.

Common Follow-ups

• What if asteroids have different speeds? → Need more complex simulation or sorting.
• Can you return the order of collisions? → Track collision events during simulation.

💡 Follow-ups test your ability to extend the problem and think beyond the basic solution.

🔍

Pattern Recognition

When to Use

1) Problem involves sequential elements with interactions; 2) Collisions or eliminations based on conditions; 3) Direction or order matters; 4) Need to track surviving elements efficiently.

Signature Phrases

'asteroids moving in opposite directions collide''smaller one explodes''return the state after all collisions'

NOT This Pattern When

Problems involving sorting or greedy without sequential interaction are different patterns.

Similar Problems

Daily Temperatures - uses stack to find next greater elementNext Greater Element - classic monotonic stack problemCar Fleet - simulates collisions with stack-like logic

Practice

1. Consider the following Python code implementing the optimal 132 pattern detection algorithm. What is the return value when the input is [3, 1, 4, 2]?

easy

A. None

B. False

C. Raises an error

D. True

Solution

1. Step 1: Trace the loop with input [3,1,4,2]

   Iterate reversed: 2,4,1,3. Initially, stack=[], third=-inf. - num=2: stack empty, append 2. - num=4: stack top 2 < 4, pop 2, third=2, append 4. - num=1: 1 < third(2), return True.

2. Step 2: Confirm early return

   At num=1, condition triggers return True, so output is True.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Early return on detecting 132 pattern confirmed [OK]

Hint: Early return when num < third triggers True [OK]

Common Mistakes:

• Confusing iteration order
• Misunderstanding when third updates
• Off-by-one in stack operations

2. You are given a string containing only the characters '(', ')', '{', '}', '[' and ']'. You need to determine if the string is valid, meaning every opening bracket has a corresponding closing bracket in the correct order. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that matches pairs as soon as they appear from left to right

B. Dynamic programming approach that stores valid substrings and merges them

C. Brute force approach that repeatedly removes valid pairs until no pairs remain

D. Stack-based approach that pushes opening brackets and matches them with closing brackets

Solution

1. Step 1: Understand problem constraints

   The problem requires matching brackets in correct order, which is naturally suited for a LIFO structure to track the most recent unmatched opening bracket.

2. Step 2: Evaluate approaches

   Greedy fails on nested or interleaved brackets; DP is overkill and complex; brute force is inefficient. Stack-based approach efficiently tracks opening brackets and matches them with closing ones in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stack approach matches pairs in order with linear time [OK]

Hint: Stack matches nested pairs in correct order [OK]

Common Mistakes:

• Assuming greedy matching works for nested brackets

3. Suppose the input stream can contain uppercase and lowercase letters (52 possible characters) instead of only lowercase. Which modification to the optimal solution is correct to handle this variant efficiently?

hard

A. Use a frequency map (dictionary) instead of fixed-size array and keep the queue logic unchanged.

B. Keep the fixed-size frequency array of length 26 and convert uppercase to lowercase before processing.

C. Use two separate frequency arrays for uppercase and lowercase letters and merge results after processing.

D. Use a brute force scan of the entire stream each time since fixed-size arrays no longer apply.

Solution

1. Step 1: Recognize input change

   Input now has 52 characters, so fixed-size array of length 26 is insufficient.

2. Step 2: Choose data structure

   A frequency map (dictionary) can handle arbitrary characters efficiently with O(1) average access.

3. Step 3: Keep queue logic

   The queue logic remains the same, tracking candidates for first unique character.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Dictionary replaces fixed array for larger character set [OK]

Hint: Use dictionary for frequency when character set is larger [OK]

Common Mistakes:

• Trying to map uppercase to lowercase losing case info
• Using two arrays complicates logic unnecessarily
• Reverting to brute force loses efficiency

4. Suppose you want to extend the one-queue stack implementation to support a multiPop(k) operation that pops the top k elements at once. Which modification maintains correct stack order and efficient operations?

hard

A. Perform k consecutive pop() calls on the queue, each O(1), total O(k).

B. Modify push to rotate the queue k times after each push to prepare for multiPop.

C. Use two queues instead, transferring elements to support batch pop efficiently.

D. Store elements in a separate stack data structure internally to support multiPop efficiently.

Solution

1. Step 1: Understand multiPop operation

   multiPop(k) means popping top k elements in stack order.

2. Step 2: Analyze one-queue approach

   Since pop is O(1), performing k pops consecutively is O(k) and maintains order.

3. Step 3: Evaluate other options

   Rotating queue k times after push breaks order; two queues add complexity; using stack internally violates constraints.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Consecutive pops maintain order and are efficient in one-queue approach [OK]

Hint: multiPop(k) = k consecutive O(1) pops in one-queue stack [OK]

Common Mistakes:

• Trying to rotate queue multiple times per push unnecessarily
• Switching to two queues without reason
• Using stack internally violating problem constraints

5. Suppose the sliding window maximum problem is modified so that the window size k can vary dynamically during the iteration. Which of the following approaches correctly adapts the monotonic deque solution to handle this efficiently?

hard

A. Adjust the window boundary checks and remove indices outside the current window size dynamically without rebuilding the deque

B. Rebuild the deque from scratch each time the window size changes

C. Switch to a max heap data structure since deque cannot handle variable window sizes

D. Use a brute force approach for variable window sizes to avoid complexity

Solution

1. Step 1: Understand dynamic window size impact

   Window boundaries change, so indices outside the current window must be removed accordingly.

2. Step 2: Adapt monotonic deque maintenance

   Instead of rebuilding, update boundary checks and pop indices outside the new window size dynamically.

3. Step 3: Evaluate alternatives

   Rebuilding deque or switching to heap is inefficient; brute force is too slow.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Dynamic boundary checks maintain O(n) amortized complexity [OK]

Hint: Update boundary removals dynamically, avoid rebuilding [OK]

Common Mistakes:

• Rebuilding deque wastes time
• Assuming heap is better for variable k