Interview Gym PRO

Stack

A stack is a pile of plates: you only touch the top one (last in, first out). It is the natural tool when the most recent unfinished thing must be dealt with first — nested brackets, undo, or "what is the next bigger value?".

After this topic: You can recognise "match the most recent thing" and "next greater element" problems and solve them in one pass.

Do these first: Arrays & Hashing

0 of 7 solved0%

Step 1 · Read the lesson

Last in, first out: matching pairs, evaluating expressions, undo and a running minimum.

Step 2 · Solve the problems in order

Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.

1.Valid Parentheses Easy

Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.

func isValid(s string) bool

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Stack Basics lesson page.

// IsValid (LeetCode 20): are all brackets closed by the right type, in the right order?
func IsValid(s string) bool {
	pairs := map[byte]byte{')': '(', ']': '[', '}': '{'}
	stack := []byte{}
	for i := 0; i < len(s); i++ {
		c := s[i]
		if open, isClose := pairs[c]; isClose {
			if len(stack) == 0 || stack[len(stack)-1] != open {
				return false
			}
			stack = stack[:len(stack)-1]
		} else {
			stack = append(stack, c)
		}
	}
	return len(stack) == 0 // leftovers are unclosed brackets
}

2.Min Stack Medium

Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.

type MinStack struct{}
func Constructor() MinStack
func (m *MinStack) Push(val int)
func (m *MinStack) Pop()
func (m *MinStack) Top() int
func (m *MinStack) GetMin() int

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Stack Basics lesson page.

// MinStack (LeetCode 155): every element remembers the minimum at the time it was pushed,
// so after a pop the previous minimum is simply the new top.
type MinStack struct{ items []struct{ val, min int } }

func (m *MinStack) Push(v int) {
	lo := v
	if n := len(m.items); n > 0 && m.items[n-1].min < lo {
		lo = m.items[n-1].min
	}
	m.items = append(m.items, struct{ val, min int }{v, lo})
}
func (m *MinStack) Pop()        { m.items = m.items[:len(m.items)-1] }
func (m *MinStack) Top() int    { return m.items[len(m.items)-1].val }
func (m *MinStack) GetMin() int { return m.items[len(m.items)-1].min }

3.Evaluate Reverse Polish Notation Medium

Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.

func evalRPN(tokens []string) int

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Stack Basics lesson page.

// EvalRPN (LeetCode 150): "3 4 +" puts the operator AFTER its operands, so operands wait on a stack.
func EvalRPN(tokens []string) int {
	var st Stack[int]
	for _, t := range tokens {
		switch t {
		case "+", "-", "*", "/":
			b, a := st.Pop(), st.Pop() // the FIRST pop is the right-hand operand
			switch t {
			case "+":
				st.Push(a + b)
			case "-":
				st.Push(a - b)
			case "*":
				st.Push(a * b)
			default:
				st.Push(a / b) // Go truncates toward zero, as the problem requires
			}
		default:
			n, _ := strconv.Atoi(t)
			st.Push(n)
		}
	}
	return st.Pop()
}

4.Generate Parentheses Medium

Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.

func generateParenthesis(n int) []string

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Stack Basics lesson page.

// GeneratePar (LeetCode 22): build the string one character at a time.
// Rule 1: you may add "(" while some are left. Rule 2: you may add ")" only if it closes an open one.
func GeneratePar(n int) []string {
	var out []string
	var build func(cur []byte, open, close int)
	build = func(cur []byte, open, close int) {
		if len(cur) == 2*n {
			out = append(out, string(cur))
			return
		}
		if open < n {
			build(append(cur, '('), open+1, close)
		}
		if close < open {
			build(append(cur, ')'), open, close+1)
		}
	}
	build(nil, 0, 0)
	return out
}

5.Daily Temperatures Medium
Days are waiting for a warmer day. Which waiting days can you resolve the moment a hot day arrives?
Keep a stack of indices with decreasing temperatures. For each new day pop every colder day and set its answer to the index gap, then push today.
Target: O(n) time, O(n) space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func dailyTemperatures(temperatures []int) []int
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Stack Basics lesson page.
// DailyTemperatures (LeetCode 739): days to wait until a warmer day (0 if never). func DailyTemperatures(temps []int) []int { res := make([]int, len(temps)) stack := []int{} for i, t := range temps { for len(stack) > 0 && temps[stack[len(stack)-1]] < t { j := stack[len(stack)-1] stack = stack[:len(stack)-1] res[j] = i - j } stack = append(stack, i) } return res }

6.Car Fleet Medium

Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.

func carFleet(target int, position []int, speed []int) int

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Stack Basics lesson page.

// CarFleet (LeetCode 853): sort by position, nearest the target first, and compute each car's arrival time.
// A car behind can never pass, so if it would arrive sooner than the fleet ahead it catches up and joins it.
// Only a car that arrives LATER than every fleet ahead leads a new fleet.
func CarFleet(target int, position, speed []int) int {
	idx := make([]int, len(position))
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(a, b int) bool { return position[idx[a]] > position[idx[b]] })
	fleets := 0
	slowest := 0.0
	for _, i := range idx {
		t := float64(target-position[i]) / float64(speed[i])
		if t > slowest { // arrives after everything ahead: cannot catch up, starts a new fleet
			fleets++
			slowest = t
		}
	}
	return fleets
}

7.Largest Rectangle in Histogram Hard

Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.

func largestRectangleArea(heights []int) int

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Stack Basics lesson page.

// LargestRectangleArea (LeetCode 84): largest rectangle inside a histogram.
// Stack of increasing heights. A shorter bar pops taller ones; each popped bar's
// rectangle extends left to the new stack top and right to the current index.
func LargestRectangleArea(heights []int) int {
	best := 0
	stack := []int{} // indices with increasing heights
	for i := 0; i <= len(heights); i++ {
		h := 0 // sentinel bar of height 0 flushes the stack at the end
		if i < len(heights) {
			h = heights[i]
		}
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= h {
			height := heights[stack[len(stack)-1]]
			stack = stack[:len(stack)-1]
			left := -1
			if len(stack) > 0 {
				left = stack[len(stack)-1]
			}
			best = max(best, height*(i-left-1))
		}
		stack = append(stack, i)
	}
	return best
}