Afasari

(Re)Start Learning Data Structure and Algorithm - Part 5, Stack

LeetCode 20: Valid Parentheses

Β 1. Title & Problem Goal

  1. Analysis & Constraints
  1. Approaches Comparison Table
Approach Logic Time Space Pros/Cons
Brute Force Repeatedly replace matching pairs (e.g., (), {}, []) with an empty string until none remain. 𝑂(𝑛^2) 𝑂(1) Simple to grasp but highly inefficient for large strings.
Stack (Optimal) Push opening brackets onto a Last-In-First-Out (LIFO) stack. Pop the top when a closing bracket is met and check for a match. 𝑂(𝑛) O(𝑛) Highly efficient; handles nested structures perfectly.
Recursion Treat each balanced segment as a sub-problem, recursing whenever a new open bracket starts. 𝑂(𝑛) 𝑂(𝑛) More complex to implement and risk of stack overflow on deep nesting.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative Cases:

  1. Optimal Code & Why (Golang)

Why this is optimal: A stack is the ideal data structure because the last bracket opened is the first one that should be closed (LIFO principle). Using a map for bracket pairs makes the code cleaner and easily extensible for more bracket types.

func isValid(s string) bool {
    // 1. Early exit for odd length
    if len(s)%2 != 0 {
        return false
    }

    // 2. Map closing brackets to opening ones
    pairs := map[rune]rune{
        ')': '(',
        ']': '[',
        '}': '{',
    }

    // 3. Stack to store opening brackets
    stack := []rune{}

    for _, char := range s {
        // If it's a closing bracket
        if opener, ok := pairs[char]; ok {
            // Check if stack is empty or top doesn't match
            if len(stack) == 0 || stack[len(stack)-1] != opener {
                return false
            }
            // Pop from stack
            stack = stack[:len(stack)-1]
        } else {
            // Push opening bracket onto stack
            stack = append(stack, char)
        }
    }

    // 4. Return true if all brackets were matched
    return len(stack) == 0
}
  1. Reflection / Mistake Log

LeetCode 155: Min Stack

  1. Title & Problem Goal
  1. Analysis & Constraints (2026 Data)
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Search on getMin Standard stack; iterate through all elements to find min. 𝑂(𝑛) for getMin 𝑂(𝑛) Fails the 𝑂(1) requirement.
Two Stacks (Optimal) Main stack for values; β€œMin Stack” to store the minimum at each state. 𝑂(1) 𝑂(𝑛) Easy to implement and very reliable.
Value & Min Pair Store each element as a pair: (value, min_at_this_level). 𝑂(1) 𝑂(𝑛) Cleanest code; similar to two stacks but uses one slice of structs.
Math Trick (Encoding) Store 2*val - min to derive the previous min. 𝑂(1) 𝑂(1) extra Avoids extra space but risky due to Integer Overflow in 2026 systems.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative Cases:

  1. Optimal Code & Why (Golang)

Why this is optimal: This implementation uses a β€œValue & Min Pair” approach with a slice of structs. It ensures that every time we push a value, we calculate the minimum relative to that specific stack depth. This avoids the overhead of managing two separate slices while maintaining 𝑂(1) access.

type Node struct {
    val int
    min int
}

type MinStack struct {
    stack []Node
}

func Constructor() MinStack {
    return MinStack{stack: []Node{}}
}

func (this *MinStack) Push(val int) {
    newMin := val
    // If stack isn't empty, compare new val with current min
    if len(this.stack) > 0 {
        currentMin := this.stack[len(this.stack)-1].min
        if currentMin < newMin {
            newMin = currentMin
        }
    }
    // Push the pair onto the stack
    this.stack = append(this.stack, Node{val: val, min: newMin})
}

func (this *MinStack) Pop() {
    if len(this.stack) > 0 {
        this.stack = this.stack[:len(this.stack)-1]
    }
}

func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1].val
}

func (this *MinStack) GetMin() int {
    return this.stack[len(this.stack)-1].min
}
  1. Reflection / Mistake Log

LeetCode 150: Evaluate Reverse Polish Notation

  1. Title & Problem Goal
  1. Analysis & Constraints (2026 Data)
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Recursive Evaluate from the end of the array backwards. 𝑂(𝑛) 𝑂(𝑛) More complex to implement; risk of stack overflow on very long expressions.
Stack (Optimal) Push numbers; when an operator is found, pop the last two, apply operator, and push result. 𝑂(𝑛) 𝑂(𝑛) Most Optimized. Cleanest implementation of LIFO logic.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative Cases:

  1. Optimal Code & Why (Golang)

Why this is optimal: A stack is the natural data structure for RPN because an operator always applies to the two most recently seen (or computed) values. Using a switch statement makes the logic for different operators highly readable.

func evalRPN(tokens []string) int {
    stack := []int{}

    for _, t := range tokens {
        // 1. Check if token is an operator
        if t == "+" || t == "-" || t == "*" || t == "/" {
            // 2. Pop the two most recent operands
            // Important: second pop is the left-side operand
            v2 := stack[len(stack)-1]
            v1 := stack[len(stack)-2]
            stack = stack[:len(stack)-2]

            // 3. Apply operation and push result
            switch t {
            case "+":
                stack = append(stack, v1+v2)
            case "-":
                stack = append(stack, v1-v2)
            case "*":
                stack = append(stack, v1*v2)
            case "/":
                stack = append(stack, v1/v2)
            }
        } else {
            // 4. Token is a number, convert and push
            val, _ := strconv.Atoi(t)
            stack = append(stack, val)
        }
    }

    return stack[0]
}
  1. Reflection / Mistake Log

LeetCode 739: Daily Temperatures

Β 1. Title & Problem Goal

  1. Analysis & Constraints (2026 Data)
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Brute Force For each day, iterate through all following days until a warmer one is found. 𝑂(𝑛2) O(1) Simple but unusable for large 𝑛.
Monotonic Stack Use a stack to store indices of temperatures. If current temp is warmer than stack top, pop and calculate distance. 𝑂(𝑛) 𝑂(𝑛) Most Optimized. Each element is pushed/popped exactly once.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative Cases:

  1. Optimal Code & Why (Golang)

Why this is optimal: The monotonic stack stores indices of days whose β€œwarmer day” hasn’t been found. When we encounter a temperature warmer than the one at the index on top of the stack, we know we’ve found the β€œwait time” for that day. This ensures we only process each element once, resulting in linear time.

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    ans := make([]int, n)
    // Monotonic stack to store indices
    stack := []int{}

    for i, currTemp := range temperatures {
        // While stack is not empty AND current temp is warmer than stack top index's temp
        for len(stack) > 0 && currTemp > temperatures[stack[len(stack)-1]] {
            // Pop the index
            prevIndex := stack[len(stack)-1]
            stack = stack[:len(stack)-1]

            // Calculate the distance (wait time)
            ans[prevIndex] = i - prevIndex
        }
        // Push current index onto stack
        stack = append(stack, i)
    }

    return ans
}
  1. Reflection / Mistake Log

LeetCode 853: Car Fleet

  1. Title & Problem Goal
  1. Analysis & Constraints
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Simulation Model every mile marker step-by-step. 𝑂(π‘‡π‘Žπ‘Ÿπ‘”π‘’π‘‘Γ—π‘›) 𝑂(𝑛) Highly inefficient for large targets.
Monotonic Stack Store arrival times. If a car behind takes less/equal time than the car ahead, it merges (stack remains same). 𝑂(𝑛log𝑛) 𝑂(𝑛) Clear visualization of fleets using a stack.
Greedy (Pointer) Similar to stack but only tracks the lastFleetTime. If currTime > lastFleetTime, it’s a new fleet. 𝑂(𝑛log𝑛) 𝑂(1)(after sort) Most Optimized. Space efficient as it avoids stack overhead.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative Cases:

  1. Optimal Code & Why (Golang)

Why this is optimal: Sorting by position ensures we process cars from the target backwards. If a car behind reaches the target slower than the fleet ahead (time > lastTime), it cannot join that fleet and must start a new one.

type car struct {
    pos  int
    time float64
}

func carFleet(target int, position []int, speed []int) int {
    n := len(position)
    cars := make([]car, n)
    for i := 0; i < n; i++ {
        // Calculate arrival time: (target - pos) / speed
        cars[i] = car{position[i], float64(target-position[i]) / float64(speed[i])}
    }

    // Sort by position descending (closest to target first)
    sort.Slice(cars, func(i, j int) bool {
        return cars[i].pos > cars[j].pos
    })

    fleets := 0
    var lastTime float64

    for _, c := range cars {
        // If this car takes LONGER than the fleet in front, it forms a NEW fleet
        if c.time > lastTime {
            fleets++
            lastTime = c.time
        }
        // Else: it arrives faster/same time but is blocked, joining the front fleet
    }

    return fleets
}
  1. Reflection / Mistake Log

LeetCode 84: Largest Rectangle in Histogram

  1. Title & Problem Goal
  1. Analysis & Constraints (2026 Data)
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Brute Force Check every pair (𝑖,𝑗) and find the minimum height between them. 𝑂(𝑛^3) or 𝑂(𝑛^2) 𝑂(1) Simple but unusable for 𝑛=10^5.
Divide & Conquer Max area is either in the left half, right half, or across the min bar. 𝑂(𝑛log𝑛) avg 𝑂(log𝑛) 𝑂(𝑛^2) worst case (sorted input).
Monotonic Stack Use a stack to track indices. When a shorter bar appears, pop and calculate areas for the popped bar. 𝑂(𝑛) 𝑂(𝑛) Most Optimized. Processes each bar exactly once.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative Cases:

  1. Optimal Code & Why (Golang)

Why this is optimal: We use a stack to store pairs of (start_index, height). We maintain a monotonic increasing stack. When we see a bar shorter than the top of the stack, we know the taller bar’s rectangle β€œends” there. We pop it, calculate its area using the width from its start_index to the current index, and update the global max.

type pair struct {
    index  int
    height int
}

func largestRectangleArea(heights []int) int {
    maxArea := 0
    stack := []pair{} // Monotonic increasing stack

    for i, h := range heights {
        start := i
        // If current height is shorter than stack top, pop and calculate area
        for len(stack) > 0 && stack[len(stack)-1].height > h {
            p := stack[len(stack)-1]
            stack = stack[:len(stack)-1]

            // Area = height of popped * (current_index - its_start_index)
            area := p.height * (i - p.index)
            if area > maxArea {
                maxArea = area
            }
            // The new bar can technically "start" from the index of the popped taller bar
            start = p.index
        }
        stack = append(stack, pair{start, h})
    }

    // Process remaining bars in stack (they extend to the end of the histogram)
    for _, p := range stack {
        area := p.height * (len(heights) - p.index)
        if area > maxArea {
            maxArea = area
        }
    }

    return maxArea
}
  1. Reflection / Mistake Log

This post is part of a series: (Re)Start Learning DSA

  1. (Re)Start Learning Data Structure and Algorithm - Part 0, Introduction
  2. (Re)Start Learning Data Structure and Algorithm - Part 1, Complexities
  3. (Re)Start Learning Data Structure and Algorithm - Part 2, Mathematics
  4. (Re)Start Learning Data Structure and Algorithm - Part 3, Array
  5. (Re)Start Learning Data Structure and Algorithm - Part 4, Two Pointers
  6. (Re)Start Learning Data Structure and Algorithm - Part 5, Stack (this post)