Practice
1. What is the time complexity of the dequeue operation in the optimal circular queue implementation using a fixed-size array with head, tail pointers, and a size variable?
medium
Solution
Step 1: Identify complexity of pointer movement
Dequeue moves head pointer forward by one position modulo capacity, which is a constant time operation.Step 2: Check if any other operations add complexity
No shifting of elements or complex calculations occur; size variable update is O(1).Final Answer:
Option C -> Option CQuick Check:
Dequeue is O(1) due to simple pointer increment and size decrement [OK]
Hint: Pointer increment modulo capacity is O(1) [OK]
Common Mistakes:
- Assuming shifting elements is needed
- Confusing pointer arithmetic with logarithmic time
- Thinking size update is costly
2. Consider this buggy implementation of the pop method in the two-stack queue. What is the bug?
def pop(self) -> int:
while self.push_stack:
self.pop_stack.append(self.push_stack.pop())
return self.pop_stack.pop()
medium
Solution
Step 1: Identify transfer condition
The code transfers elements from push_stack to pop_stack on every pop, regardless of pop_stack state.Step 2: Understand impact
This causes O(n) time on every pop, losing amortized O(1) efficiency.Final Answer:
Option C -> Option CQuick Check:
Transfer only when pop_stack empty -> amortized O(1) [OK]
Hint: Transfer only if pop_stack empty to keep amortized O(1) [OK]
Common Mistakes:
- Transferring every pop causes O(n) pop time
- Not checking empty queue before pop
3. Identify the bug in the following MinStack implementation using a single stack with encoded minimums:
medium
Solution
Step 1: Analyze push condition
The condition 'if diff <= 0:' updates minVal even when diff == 0, i.e., when new element equals current min.Step 2: Understand impact
Updating minVal on equal values causes minVal to be overwritten incorrectly, breaking min tracking when duplicates are popped.Final Answer:
Option C -> Option CQuick Check:
Correct condition is 'diff < 0' to update minVal only on strictly smaller values [OK]
Hint: Only update minVal when new value is strictly less than current min [OK]
Common Mistakes:
- Using <= instead of < causes minVal errors with duplicates
- Incorrect pop minVal update
- Appending wrong values to stack
4. What is the time complexity of the optimal monotonic stack solution that uses an explicit circular array copy (doubling the array) for the Next Greater Element II problem, and why?
medium
Solution
Step 1: Identify loop iterations
The loop runs over doubled array of length 2n, so 2n iterations.Step 2: Analyze stack operations
Each element index is pushed once and popped once at most, so total stack operations are O(n). The doubling does not cause repeated pushes for the same index.Final Answer:
Option A -> Option AQuick Check:
Doubling array length does not multiply complexity beyond linear [OK]
Hint: Each element pushed/popped once -> O(n) despite doubled array [OK]
Common Mistakes:
- Assuming doubling array doubles complexity to O(n²)
- Confusing stack operations with sorting complexity
- Ignoring that indices are pushed only once
5. What is the time complexity of the optimized stack-based approach for validating parentheses in a string of length n, and why might some candidates mistakenly think it is higher?
medium
Solution
Step 1: Identify complexity of outer loop
The algorithm iterates over each character exactly once, so the loop is O(n).Step 2: Check stack operations
Stack push/pop are O(1) operations, so total time remains O(n). No nested loops or repeated scanning.Final Answer:
Option B -> Option BQuick Check:
Single pass with constant-time stack ops -> O(n) time [OK]
Hint: Each character processed once with O(1) stack ops [OK]
Common Mistakes:
- Confusing with brute force O(n^2) approach