From Theory to Mastery

[!NOTE] This module explores the core principles of Stacks & Queues Practice Problems, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

You know push and pop. Now let’s solve problems that appear in Google, Amazon, and Meta interviews.

1. Daily Temperatures

Problem: Given [73, 74, 75, 71, 69, 72, 76, 73]. Return [1, 1, 4, 2, 1, 1, 0, 0]. (How many days until a warmer temperature?)

Constraints:

  • 1 <= temperatures.length <= 10^5
  • 30 <= temperatures[i] <= 100

Edge Cases & Clarifying Questions

  • Q: What if there is no future day with a warmer temperature? A: Return 0 for that day.
  • Q: What if all temperatures are the same or strictly decreasing? A: Return 0 for all days.

Intuition

Brute Force: The simplest approach is for every day, scan all subsequent days to find the first day that is warmer. The time complexity for this is O(N^2), which is too slow given the constraint of N = 10^5.

Optimized: Monotonic Stack: We want the Next Greater Element. Instead of rescanning future days, we can keep track of days waiting for a warmer temperature. Use a Decreasing Monotonic Stack storing indices.

  • If current > top, we found a warmer day for top. Pop and calculate distance.
  • If current <= top, push the current index onto the stack.

Common Pitfalls:

  • Storing temperature values instead of indices in the stack. We need the indices to calculate the distance.
  • Forgetting to process remaining elements (they naturally default to 0 if the result array is initialized with 0s).

Interactive Analysis

Watch how the monotonic stack resolves the next warmer temperature.

Temperatures

Stack (Indices)

Start scanning...

Solutions

Java
Go
public int[] dailyTemperatures(int[] temperatures) {
  int n = temperatures.length;
  int[] res = new int[n];
  Deque<Integer> stack = new ArrayDeque<>(); // Indices

  for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
      int prevIndex = stack.pop();
      res[prevIndex] = i - prevIndex; // Distance
    }
    stack.push(i);
  }
  return res;
}

func dailyTemperatures(temperatures []int) []int {
  n := len(temperatures)
  res := make([]int, n)
  stack := []int{} // Indices

  for i, t := range temperatures {
    for len(stack) > 0 && t > temperatures[stack[len(stack)-1]] {
      idx := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      res[idx] = i - idx
    }
    stack = append(stack, i)
  }
  return res;
}

Complexity

Strategy Time Space Notes
Brute Force O(N^2) O(1) Too slow. Time Limit Exceeded.
Monotonic Stack O(N) O(N) Each index is pushed and popped at most once.

2. Largest Rectangle in Histogram

Problem: Given heights [2, 1, 5, 6, 2, 3]. Find the area of the largest rectangle.

Constraints:

  • 1 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^4

Edge Cases & Clarifying Questions

  • Q: What if all heights are 0? A: The area is 0.
  • Q: What if all bars have the same height? A: The area is the height multiplied by the number of bars.

Intuition

Brute Force: For every bar, find the left and right boundaries where the height is greater than or equal to the current bar’s height. The area with the current bar as the minimum height is current_height * (right - left + 1). Time complexity is O(N^2), which is too slow.

Optimized: Monotonic Stack: This is the Next Smaller Element (and Previous Smaller Element) problem! We can do this in one pass with a Monotonic Increasing Stack.

  • Pop Condition: When current height is less than stack top. The popped bar is taller than current.
  • Area: h * (i - new_top - 1).

Common Pitfalls:

  • Forgetting to process the remaining elements in the stack after the loop ends. A common trick is to use a dummy -1 index.
  • Calculating width incorrectly. It should be current_index - stack.peek() - 1 after popping.

Interactive Analysis

Watch how the stack calculates area.

  1. Push index if height is increasing.
  2. Pop if height decreases. Calculate area for popped bar.

Histogram [2, 1, 5, 6, 2, 3]

Stack (Indices)

Start scanning...
Max Area: 0

Solutions

Java
Go
public int largestRectangleArea(int[] heights) {
  Deque<Integer> stack = new ArrayDeque<>();
  stack.push(-1); // Sentinel for left boundary
  int maxArea = 0;

  for (int i = 0; i < heights.length; i++) {
    while (stack.peek() != -1 && heights[i] <= heights[stack.peek()]) {
      int h = heights[stack.pop()];
      int w = i - stack.peek() - 1; // Right - Left - 1
      maxArea = Math.max(maxArea, h * w);
    }
    stack.push(i);
  }

  // Clean up remaining stack
  while (stack.peek() != -1) {
    int h = heights[stack.pop()];
    int w = heights.length - stack.peek() - 1;
    maxArea = Math.max(maxArea, h * w);
  }

  return maxArea;
}

func largestRectangleArea(heights []int) int {
  stack := []int{-1} // Sentinel
  maxArea := 0

  for i, h := range heights {
    for len(stack) > 1 && h <= heights[stack[len(stack)-1]] {
      height := heights[stack[len(stack)-1]]
      stack = stack[:len(stack)-1]
      width := i - stack[len(stack)-1] - 1
      if area := height * width; area > maxArea {
        maxArea = area
      }
    }
    stack = append(stack, i)
  }

  // Remaining
  for len(stack) > 1 {
    height := heights[stack[len(stack)-1]]
    stack = stack[:len(stack)-1]
    width := len(heights) - stack[len(stack)-1] - 1
    if area := height * width; area > maxArea {
      maxArea = area
    }
  }

  return maxArea;
}

Complexity

Strategy Time Space Notes
Brute Force O(N^2) O(1) Checking all left/right pairs.
Monotonic Stack O(N) O(N) One pass.

3. Implement Queue using Stacks

Problem: Implement a FIFO Queue using only two LIFO Stacks.

Constraints:

  • 1 <= x <= 9
  • At most 100 calls to push, pop, peek, and empty.
  • All calls to pop and peek are valid.

Edge Cases & Clarifying Questions

  • Q: What happens if we call pop on an empty queue? A: The problem guarantees valid calls, but normally we would return a sentinel or throw an exception.

Intuition

Brute Force: For every push operation, we can push onto s1. For every pop operation, we can transfer all elements from s1 to s2, pop the top of s2, and transfer everything back to s1. This makes pop O(N) and push O(1).

Optimized: Amortized O(1): Instead of transferring elements back and forth, keep elements in s2!

  1. Push (s1): Incoming elements always go to s1.
  2. Pop / Peek (s2): Outgoing elements come from s2. If s2 is empty, pour all elements from s1 into s2. This reverses order (LIFO + LIFO = FIFO).

Common Pitfalls:

  • Transferring elements back to s1 after a pop. This defeats the optimization.
  • Not transferring all elements from s1 when pouring.

Interactive Analysis

Watch how pouring elements from Stack 1 to Stack 2 reverses their order.

Stack 1 (In)

Stack 2 (Out)

Queue initialized.

Solutions

Java
Go
class MyQueue {
  Deque<Integer> in = new ArrayDeque<>();
  Deque<Integer> out = new ArrayDeque<>();

  public void push(int x) {
    in.push(x);
  }

  public int pop() {
    peek(); // Ensure out has elements
    return out.pop();
  }

  public int peek() {
    if (out.isEmpty()) {
      while (!in.isEmpty()) {
        out.push(in.pop());
      }
    }
    return out.peek();
  }
}

type MyQueue struct {
    in, out []int
}

func (this *MyQueue) Push(x int) {
    this.in = append(this.in, x)
}

func (this *MyQueue) Pop() int {
    this.Peek()
    val := this.out[len(this.out)-1]
    this.out = this.out[:len(this.out)-1]
    return val
}

func (this *MyQueue) Peek() int {
    if len(this.out) == 0 {
        for len(this.in) > 0 {
            val := this.in[len(this.in)-1]
            this.in = this.in[:len(this.in)-1]
            this.out = append(this.out, val)
        }
    }
    return this.out[len(this.out)-1]
}

Complexity

Strategy Time Space Notes
Brute Force O(N) per pop/push O(N) Transferring back and forth.
Amortized O(1) Amortized O(N) Each element is transferred at most once.