Practice
1. Given the following Python code for the Basic Calculator, what is the value of
result immediately after processing the character ')' at index 6 in the input string "(1+(2-3))"?
def calculate(s: str) -> int:
stack = []
result = 0
sign = 1
num = 0
for i, c in enumerate(s):
if c.isdigit():
num = num * 10 + int(c)
elif c in '+-':
result += sign * num
num = 0
sign = 1 if c == '+' else -1
elif c == '(': # Push current result and sign
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif c == ')': # Add last number and combine
result += sign * num
num = 0
result *= stack.pop()
result += stack.pop()
result += sign * num
return result
easy
Solution
Step 1: Trace characters up to index 6
Input: "(1+(2-3))" - i=0:'(' push 0 and 1, result=0, sign=1 - i=1:'1' num=1 - i=2:'+' result=0+1*1=1, num=0, sign=1 - i=3:'(' push 1 and 1, result=0, sign=1 - i=4:'2' num=2 - i=5:'-' result=0+1*2=2, num=0, sign=-1 - i=6:'3' num=3Step 2: Process character at index 6 (')')
At ')': result += sign*num = 2 + (-1)*3 = -1 num=0 result *= stack.pop() -> result *= 1 -> -1 result += stack.pop() -> -1 + 1 = 0Final Answer:
Option A -> Option AQuick Check:
Result after popping stack is 0 [OK]
Hint: Remember to apply sign*num before popping stack [OK]
Common Mistakes:
- Forgetting to add last number before popping stack
2. Consider the following Python function implementing the optimized monotonic stack approach for sum of subarray minimums. What is the final returned value when calling
sumSubarrayMins([3,1,2,4])?easy
Solution
Step 1: Trace stack operations for input [3,1,2,4]
Push indices 0(3), then at i=1(1), pop 0 because 1<3, add 3*(1-(-1))*(1-0)=3*1*1=3; push 1. Continue similarly for indices 2 and 3.Step 2: Calculate final result after processing sentinel
After processing all elements and sentinel, sum is 17 modulo 10^9+7.Final Answer:
Option A -> Option AQuick Check:
Matches known correct output for this input [OK]
Hint: Sentinel ensures all elements processed; final sum is 17 [OK]
Common Mistakes:
- Off-by-one in counting subarrays
- Forgetting sentinel element
3. 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
4. The following code attempts to compute the largest rectangle area in a histogram using a monotonic stack. Identify the line containing the subtle bug that causes incorrect area calculation in some cases.
def largestRectangleArea(heights):
n = len(heights)
left = [-1] * n
right = [n] * n
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
left[i] = stack[-1] if stack else -1
stack.append(i)
stack.clear()
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
right[i] = stack[-1] if stack else n
stack.append(i)
max_area = 0
for i in range(n):
width = right[i] - left[i] - 1
area = heights[i] * width
max_area = max(max_area, area)
return max_areamedium
Solution
Step 1: Compare left boundary condition with right boundary
Left boundary uses '>=' but right boundary also uses '>='; originally left boundary used '>' causing inconsistency.Step 2: Identify impact of using '>' instead of '>='
Using '>' misses popping bars equal in height, leading to wrong left boundaries and smaller area.Final Answer:
Option D -> Option DQuick Check:
Changing '>' to '>=' in left boundary fixes the bug [OK]
Hint: Use consistent '>=' in both boundary computations [OK]
Common Mistakes:
- Mixing '>' and '>=' causing inconsistent boundaries
- Forgetting to clear stack before right boundary pass
5. 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
Solution
Step 1: Understand multiPop operation
multiPop(k) means popping top k elements in stack order.Step 2: Analyze one-queue approach
Since pop is O(1), performing k pops consecutively is O(k) and maintains order.Step 3: Evaluate other options
Rotating queue k times after push breaks order; two queues add complexity; using stack internally violates constraints.Final Answer:
Option A -> Option AQuick 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