Practice
1. Given the following Python code for asteroid collision, what is the output when the input is [8, -8, 5, -10]?
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
print(asteroidCollision([8, -8, 5, -10]))
easy
Solution
Step 1: Trace collision between 8 and -8
8 and -8 are equal size but opposite direction, both explode -> stack empty.Step 2: Process 5 and then -10
5 is pushed; -10 collides with 5, since 10 > 5, 5 pops, -10 remains and is pushed.Final Answer:
Option B -> Option BQuick Check:
Final stack contains only [-10] after resolving collisions [OK]
Hint: Equal size opposite asteroids both explode [OK]
Common Mistakes:
- Forgetting to pop both equal asteroids
- Appending asteroid after it exploded
- Not handling multiple collisions in while loop
2. What is the time complexity of the optimized stack simulation algorithm for the asteroid collision problem, given n asteroids in the input list?
medium
Solution
Step 1: Analyze iteration over asteroids
The algorithm iterates over each asteroid once.Step 2: Analyze stack operations
Each asteroid can be pushed once and popped once, so total stack operations are O(n).Final Answer:
Option A -> Option AQuick Check:
Each asteroid processed at most twice (push/pop) [OK]
Hint: Each asteroid pushed and popped once max [OK]
Common Mistakes:
- Assuming nested while loop causes O(n^2)
- Confusing stack operations with sorting
- Ignoring amortized analysis of stack pops
3. The following code attempts to implement a stack using two queues with a costly push operation:
from collections import deque
class MyStack:
def __init__(self):
self.q1 = deque()
self.q2 = deque()
def push(self, x: int) -> None:
self.q2.append(x)
while self.q1:
self.q2.append(self.q1.popleft())
# Missing swap here
def pop(self) -> int:
return self.q1.popleft()
def top(self) -> int:
return self.q1[0]
def empty(self) -> bool:
return not self.q1
medium
Solution
Step 1: Analyze push method
Elements are moved from q1 to q2, but q1 and q2 are never swapped, so q1 remains empty after push.Step 2: Consequence on pop and top
Pop and top operate on q1, which is empty, causing errors or incorrect behavior.Final Answer:
Option A -> Option AQuick Check:
Swapping queues after push is essential to maintain main queue reference [OK]
Hint: Missing queue swap after push breaks main queue reference [OK]
Common Mistakes:
- Forgetting to swap queues after push
- Accessing wrong queue in pop or top
- Checking emptiness incorrectly
4. What is the time complexity of the optimal monotonic stack solution for the Largest Rectangle in Histogram problem, and why?
medium
Solution
Step 1: Analyze stack operations
Each bar is pushed once and popped at most once, so total stack operations are O(n).Step 2: Confirm no nested loops over all elements
Loops run linearly, no repeated scanning of all elements inside inner loops.Final Answer:
Option A -> Option AQuick Check:
Linear time complexity due to amortized stack operations [OK]
Hint: Each element pushed/popped once -> O(n) time [OK]
Common Mistakes:
- Assuming stack operations cause O(n log n) or O(n^2)
- Confusing nested loops in brute force with stack approach
5. What is the time complexity of the optimal monotonic stack solution for the online stock span problem when processing n prices?
medium
Solution
Step 1: Analyze stack operations
Each price index is pushed exactly once and popped at most once from the stack.Step 2: Calculate amortized complexity
Since each element is pushed and popped once, total operations are O(n), making the algorithm O(n) amortized time.Final Answer:
Option B -> Option BQuick Check:
Monotonic stack amortized analysis is standard for O(n) [ERROR]
Hint: Each element pushed and popped once -> O(n) amortized [ERROR]
Common Mistakes:
- Assuming nested loop causes O(n^2)
- Thinking binary search is used in stack