L20–L25 Trie, Greedy, DP, Backtracking, Bits

L20. Trie

Definition: a prefix tree. Each edge is one character. Words that share a prefix share the same path. A node’s end flag marks a complete word.

Real-world use:

1. Insert

Walk one node per character. Create a child if missing. Mark end on the last character.

Real-world use: add apple to a dictionary so later app can reuse the same path.

Insert "apple":

root
 └─ a
    └─ p
       └─ p
          └─ l
             └─ e   (end=true)

Then insert "app": reuse a-p-p and mark that p as end.

Complexity: time O(L) for a word of length L. Extra space O(L) new nodes in the worst case.

2. Implement Trie

Search needs end == true. StartsWith only needs the walk to succeed. "apple" is a word; "app" is only a prefix until you insert it.

Real-world use: search-as-you-type: StartsWith("app") is true while Search("app") is still false.

type Trie struct {
	children [26]*Trie
	end      bool
}

func (t *Trie) Insert(word string) {
	node := t
	for i := 0; i < len(word); i++ {
		idx := word[i] - 'a'
		if node.children[idx] == nil {
			node.children[idx] = &Trie{}
		}
		node = node.children[idx]
	}
	node.end = true
}

func (t *Trie) Search(word string) bool {
	node := t.walk(word)
	return node != nil && node.end
}

func (t *Trie) StartsWith(prefix string) bool {
	return t.walk(prefix) != nil
}

Complexity: Insert / Search / StartsWith time O(L). Extra space for the trie is O(total characters inserted) after prefix sharing. Each call uses O(1) extra besides the tree.

L21. Greedy

Definition: take the locally best choice and never undo it. It is correct only when that local choice is also globally optimal — farthest reach, earliest finish, unique start that can complete a cycle.

Real-world use:

1. Jump Game I

Can you reach the last index? Track the farthest index reachable so far. If i walks past that, you are stuck.

Real-world use: can a frog (or a delivery hop) reach the last stone if each stone says how far you may jump?

[2,3,1,1,4] → true. [3,2,1,0,4] → false (stuck at the 0).

func CanJump(nums []int) bool {
	reach := 0
	for i, jump := range nums {
		if i > reach {
			return false
		}
		if i+jump > reach {
			reach = i + jump
		}
	}
	return true
}

Complexity: time O(n), extra space O(1).

2. Jump Game II

Minimum jumps, assuming a path exists. The current jump covers [prevEnd+1, end]. When i hits end, take one more jump and extend end to farthest.

Real-world use: fewest refuels or fewest hops to cross a highway when each stop has a max reach.

[2,3,1,1,4] → 2 (0→1→4).

func Jump(nums []int) int {
	jumps, end, farthest := 0, 0, 0
	for i := 0; i < len(nums)-1; i++ {
		if i+nums[i] > farthest {
			farthest = i + nums[i]
		}
		if i == end {
			jumps++
			end = farthest
		}
	}
	return jumps
}

Complexity: time O(n), extra space O(1).

3. Gas station

Unique circular tour. If total gas < total cost, impossible. Otherwise the start is the station after the last time the tank went negative.

Real-world use: the unique depot a truck must start from to complete a circular route without running dry.

gas=[1,2,3,4,5], cost=[3,4,5,1,2] → start index 3.

func CanCompleteCircuit(gas, cost []int) int {
	total, tank, start := 0, 0, 0
	for i := range gas {
		diff := gas[i] - cost[i]
		total += diff
		tank += diff
		if tank < 0 {
			start = i + 1
			tank = 0
		}
	}
	if total < 0 {
		return -1
	}
	return start
}

Complexity: time O(n), extra space O(1).

L22. Dynamic Programming — House Robber

Definition: solve a big problem from overlapping smaller ones. Store each sub-answer (memo or table) so you never recompute it. House robber: you may not take two adjacent houses, so dp[i] = max(skip, take + dp[i-2]).

Real-world use:

You cannot rob two adjacent houses:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

[1,2,3,1] → 4 (1+3). [2,7,9,3,1] → 12 (2+9+1).

Type 1 — top-down (recursion + memo)

Real-world use: write the recurrence the way you think (“from house i, take or skip”), then cache answers so a planner does not re-ask the same house.

func RobTopDown(nums []int) int {
	memo := make([]int, len(nums))
	for i := range memo {
		memo[i] = -1
	}
	var robFrom func(int) int
	robFrom = func(i int) int {
		if i >= len(nums) {
			return 0
		}
		if memo[i] >= 0 {
			return memo[i]
		}
		take := nums[i] + robFrom(i+2)
		skip := robFrom(i + 1)
		if take < skip {
			take = skip
		}
		memo[i] = take
		return take
	}
	return robFrom(0)
}

Complexity: time O(n), extra space O(n) for the memo plus O(n) recursion.

Type 2 — bottom-up table

Real-world use: fill a spreadsheet of “best so far at house i” from left to right when you want no recursion on a long street.

func RobBottomUp(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	if n == 1 {
		return nums[0]
	}
	dp := make([]int, n)
	dp[0] = nums[0]
	dp[1] = nums[0]
	if nums[1] > dp[1] {
		dp[1] = nums[1]
	}
	for i := 2; i < n; i++ {
		dp[i] = dp[i-1]
		if dp[i-2]+nums[i] > dp[i] {
			dp[i] = dp[i-2] + nums[i]
		}
	}
	return dp[n-1]
}

Complexity: time O(n), extra space O(n).

Type 3 — space optimization

Only dp[i-1] and dp[i-2] are needed.

Real-world use: a streaming planner that only remembers yesterday and the day before — no full table in memory.

func Rob(nums []int) int {
	prev2, prev1 := 0, 0
	for _, money := range nums {
		cur := prev1
		if prev2+money > prev1 {
			cur = prev2 + money
		}
		prev2, prev1 = prev1, cur
	}
	return prev1
}

Complexity: time O(n), extra space O(1).

All three are O(n) time. Extra space is O(n), O(n), then O(1).

L23. Minimum Path Sum

Definition: a grid DP. From each cell you may move only right or down. The cheapest way to a cell is cell + min(from above, from left).

Real-world use:

dp[r][c] = grid[r][c] + min(from_above, from_left)

1 3 1
1 5 1   path 1→3→1→1→1 = 7
4 2 1

Approach 1 — recursion with memo

Real-world use: ask “cheapest from this cell to the exit?” and cache the answer, like a GPS that memos intersections.

func MinPathSumMemo(grid [][]int) int {
	rows, cols := len(grid), len(grid[0])
	memo := make([][]int, rows)
	for i := range memo {
		memo[i] = make([]int, cols)
		for j := range memo[i] {
			memo[i][j] = -1
		}
	}
	var dfs func(r, c int) int
	dfs = func(r, c int) int {
		if r == rows-1 && c == cols-1 {
			return grid[r][c]
		}
		if memo[r][c] >= 0 {
			return memo[r][c]
		}
		best := int(^uint(0) >> 1)
		if r+1 < rows {
			best = dfs(r+1, c)
		}
		if c+1 < cols {
			if right := dfs(r, c+1); right < best {
				best = right
			}
		}
		memo[r][c] = grid[r][c] + best
		return memo[r][c]
	}
	return dfs(0, 0)
}

Complexity: time O(rows × cols), extra space O(rows × cols) for the memo plus O(rows + cols) recursion.

Approach 2 — full table

Fill first row and first column as prefix sums, then the rest.

Real-world use: a warehouse cost grid: each cell stores the cheapest way to arrive there from the dock.

func MinPathSumTable(grid [][]int) int {
	rows, cols := len(grid), len(grid[0])
	dp := make([][]int, rows)
	for i := range dp {
		dp[i] = append([]int(nil), grid[i]...)
	}
	for c := 1; c < cols; c++ {
		dp[0][c] += dp[0][c-1]
	}
	for r := 1; r < rows; r++ {
		dp[r][0] += dp[r-1][0]
		for c := 1; c < cols; c++ {
			if dp[r-1][c] < dp[r][c-1] {
				dp[r][c] += dp[r-1][c]
			} else {
				dp[r][c] += dp[r][c-1]
			}
		}
	}
	return dp[rows-1][cols-1]
}

Complexity: time O(rows × cols), extra space O(rows × cols).

Approach 3 — one row

dp[c] is the previous row until you overwrite it. Compare dp[c] (above) with dp[c-1] (left).

Real-world use: same cheapest-path grid when you only keep the previous street of costs in memory.

func MinPathSum(grid [][]int) int { /* see solutions.go */ }

Complexity: time O(rows × cols), extra space O(cols).

L24. Backtracking

Definition: build a partial answer, try a choice, recurse, then undo the choice if it fails (path = path[:len-1], unmark visited). Use it when you must enumerate or search a decision tree.

Real-world use:

1. Subset generation

For each number: skip it, or take it. 2^n subsets.

Real-world use: every pizza topping combo, or every subset of optional features a customer can buy.

[1,2,3] → [], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3] (order depends on skip-first vs take-first).

func SubsetsBacktrack(nums []int) [][]int {
	var out [][]int
	var path []int
	var dfs func(int)
	dfs = func(i int) {
		if i == len(nums) {
			out = append(out, append([]int(nil), path...))
			return
		}
		dfs(i + 1)              // skip
		path = append(path, nums[i])
		dfs(i + 1)              // take
		path = path[:len(path)-1]
	}
	dfs(0)
	return out
}

The iterative version (Subsets in solutions.go) grows the answer list by cloning every existing subset and appending the new number.

Complexity: time O(n · 2ⁿ), extra space O(n) for the path plus O(n · 2ⁿ) for the output.

2. Rat in a Maze

n x n grid. 1 is open, 0 is blocked. Start (0,0), end (n-1,n-1). Moves in order D L R U. Mark visited, recurse, unmark.

Real-world use: a warehouse robot listing every open path from the dock to the packing bay.

1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1

Paths: DDRDRR, DRDDRR.

func RatInMaze(grid [][]int) []string {
	n := len(grid)
	visited := make([][]bool, n)
	for i := range visited {
		visited[i] = make([]bool, n)
	}
	var paths []string
	var path []byte
	dirs := []struct {
		dr, dc int
		ch     byte
	}{{1, 0, 'D'}, {0, -1, 'L'}, {0, 1, 'R'}, {-1, 0, 'U'}}
	var dfs func(r, c int)
	dfs = func(r, c int) {
		if r == n-1 && c == n-1 {
			paths = append(paths, string(path))
			return
		}
		for _, d := range dirs {
			nr, nc := r+d.dr, c+d.dc
			if nr < 0 || nc < 0 || nr >= n || nc >= n || visited[nr][nc] || grid[nr][nc] == 0 {
				continue
			}
			visited[nr][nc] = true
			path = append(path, d.ch)
			dfs(nr, nc)
			path = path[:len(path)-1]
			visited[nr][nc] = false
		}
	}
	if n == 0 || grid[0][0] == 0 {
		return nil
	}
	visited[0][0] = true
	dfs(0, 0)
	return paths
}

Complexity: time O(4^(n²)) in the worst open grid, extra space O(n²) for visited plus O(n²) path depth.

L25. Bitwise Operations

Definition: work on the binary digits of an integer. AND / OR / XOR / NOT and shifts replace loops over flags. Index i is 0-based from the least significant bit.

Real-world use:

OperatorGoMeaning
ANDa & bbits set in both
OR`a \b`bits set in either
XORa ^ bbits that differ
NOT^aflip all bits
left shifta << kmultiply by 2^k
right shifta >> kdivide by 2^k (sign-extends signed ints)

n & (n-1) clears the lowest set bit. n & 1 is the lowest bit.

1. Power of two

Positive and exactly one set bit. 16 yes, 18 no, 0 no.

Real-world use: check that a buffer size or memory page is a power of two before rounding.

func IsPowerOfTwo(n int) bool { return n > 0 && n&(n-1) == 0 }

Complexity: time O(1), extra space O(1).

2. Count set bits

Real-world use: how many permission flags or feature bits are on in one integer.

func HammingWeight(n int) int {
	count := 0
	for n != 0 {
		n &= n - 1
		count++
	}
	return count
}

11 is 1011 → 3 bits.

Complexity: time O(number of set bits), extra space O(1).

3. Only non-repeating element

XOR cancels pairs. [4,1,2,1,2] → 4.

Real-world use: the one package id that did not come in a pair, or the unique unpaired locker key.

func SingleNumber(nums []int) int {
	x := 0
	for _, n := range nums {
		x ^= n
	}
	return x
}

Complexity: time O(n), extra space O(1).

4. Get the i-th bit

10 is 1010. Bit 1 is 1.

Real-world use: read one feature flag: “is dark mode (bit 1) on?”

func GetIthBit(n, i int) int { return (n >> i) & 1 }

Complexity: time O(1), extra space O(1).

5. Set the i-th bit

10 | (1<<0) → 11.

Real-world use: turn on one permission without touching the others.

func SetIthBit(n, i int) int { return n | (1 << i) }

Complexity: time O(1), extra space O(1).

Clear is the natural pair: n &^ (1 << i). Same complexity.