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?)

Intuition: Monotonic Stack

We want the Next Greater Element. Use a Decreasing Monotonic Stack storing indices.

• If current > top, we found a warmer day for top. Pop and calculate distance.

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;
}

---

2. Largest Rectangle in Histogram

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

Intuition

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).

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
Monotonic Stack	O(N)	O(N)	One pass.

---

3. Implement Queue using Stacks

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

Intuition

1. Push (s1): Incoming.
2. Pop (s2): Outgoing. If s2 empty, pour s1 into s2. This reverses order (LIFO + LIFO = FIFO).

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]
}