Algorithms & complexity

You don't need to memorise hundreds of algorithms. You need to read a piece of code and say what it costs, and to recognise the dozen or so techniques that most problems — at work and in interviews — reduce to. This lesson covers analysing time and space, then sorting, binary search, recursion, graph traversal and dynamic programming, each with working Go code.

#Analysing code

To find the time complexity of code, count how many times the innermost work runs as a function of the input size, then keep only the fastest-growing term.

func HasDuplicate(nums []int) bool {
	for i := range nums {          // n iterations
		for j := i + 1; j < len(nums); j++ { // up to n-1, n-2, ... iterations
			if nums[i] == nums[j] {
				return true
			}
		}
	}
	return false
}

The inner comparison runs n(n−1)/2 times in the worst case. Drop constants and lower terms and that's O(n²). A set brings it down to O(n) at the price of O(n) extra memory — the most common trade in algorithm design, time for space:

func HasDuplicate(nums []int) bool {
	seen := make(map[int]struct{}, len(nums))
	for _, n := range nums {
		if _, ok := seen[n]; ok {
			return true
		}
		seen[n] = struct{}{}
	}
	return false
}

Rules of thumb that cover most code:

• Sequential steps add: an O(n) loop followed by an O(n log n) sort is O(n log n).
• Nested loops over the same input multiply: O(n) × O(n) = O(n²).
• Halving the input each step gives O(log n).
• A recursive function that calls itself twice on inputs of size n−1 is O(2ⁿ) — a warning sign.
• Space counts extra memory you allocate, including the recursion stack.

Always ask what the worst case is, and whether it's realistic. Hash-map lookups are O(1) on average; quicksort is O(n log n) on average and O(n²) on adversarial input, which is why Go's sort uses pattern-defeating quicksort with a fallback that guarantees O(n log n).

#Sorting

You will almost never write a sort at work; you'll call one. In Go that's the slices package (Go 1.21+):

slices.Sort(nums) // ascending, O(n log n)

slices.SortStableFunc(users, func(a, b User) int {
	return cmp.Compare(a.Age, b.Age) // negative, zero or positive
})

What you do need to know is what sorting buys you and the properties that matter:

• Sorting costs O(n log n) — no comparison sort can do better in general — and after it, many problems become linear: duplicates sit next to each other, two pointers can walk in from both ends, and binary search works.
• A stable sort keeps equal elements in their original order. Sort orders by date, then stably by customer, and each customer's orders stay in date order.
• Merge sort splits the input in half, sorts each half recursively and merges them in O(n): log n levels of O(n) work gives O(n log n). Knowing this shape helps you analyse any divide-and-conquer algorithm.

#Binary search

Binary search finds a target in a sorted slice by comparing against the middle and discarding the half that can't contain it: O(log n), so 30 steps for a billion elements. It's easy to get subtly wrong, so write it with a clear invariant — a statement that stays true on every iteration:

// LowerBound returns the first index i with nums[i] >= target,
// or len(nums) if there is none. nums must be sorted ascending.
func LowerBound(nums []int, target int) int {
	lo, hi := 0, len(nums) // invariant: the answer is in [lo, hi]
	for lo < hi {
		mid := lo + (hi-lo)/2 // avoids overflow of lo+hi
		if nums[mid] < target {
			lo = mid + 1 // answer is right of mid
		} else {
			hi = mid // mid itself might be the answer
		}
	}
	return lo
}

The standard library has this as slices.BinarySearch and, for any predicate, sort.Search. The deeper idea is binary search on the answer: whenever a yes/no question flips from false to true exactly once as a number grows — "can we ship all packages in D days with capacity C?" — you can binary-search for the smallest C that works, even though there's no array in sight.

#Recursion and backtracking

A recursive function solves a problem by solving smaller instances of the same problem. Every recursive function needs a base case that stops, and each call must move towards it. Trees are naturally recursive:

func Height(n *Node) int {
	if n == nil {
		return 0 // base case
	}
	return 1 + max(Height(n.Left), Height(n.Right))
}

Backtracking is recursion that builds a candidate step by step and undoes the last step when it leads nowhere. It enumerates permutations, subsets and puzzle solutions:

// Subsets returns every subset of nums.
func Subsets(nums []int) [][]int {
	var out [][]int
	var cur []int
	var walk func(i int)
	walk = func(i int) {
		if i == len(nums) {
			out = append(out, slices.Clone(cur)) // copy: cur keeps changing
			return
		}
		walk(i + 1)                  // skip nums[i]
		cur = append(cur, nums[i])   // take nums[i]
		walk(i + 1)
		cur = cur[:len(cur)-1]       // undo
	}
	walk(0)
	return out
}

There are 2ⁿ subsets, so this is O(2ⁿ · n) no matter how you write it. Exponential output means exponential time; that's fine for n = 15 and hopeless for n = 60. Each recursion level also uses stack space, so deep recursion over very large inputs (a linked list of a million nodes) is better written as a loop.

#Graph traversal: BFS and DFS

Most graph problems reduce to visiting nodes in some order while remembering which ones you've seen. The graph traversal note compares the two orders side by side.

Breadth-first search uses a queue and visits nodes level by level, so the first time it reaches a node is along a shortest path (counting edges). Use it for "minimum number of steps" questions:

// ShortestPath returns the number of edges from start to goal, or -1.
func ShortestPath(graph map[string][]string, start, goal string) int {
	dist := map[string]int{start: 0}
	queue := []string{start}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if node == goal {
			return dist[node]
		}
		for _, next := range graph[node] {
			if _, seen := dist[next]; !seen {
				dist[next] = dist[node] + 1
				queue = append(queue, next)
			}
		}
	}
	return -1
}

Depth-first search uses recursion (or an explicit stack) and goes as deep as possible before backing up. Use it to explore everything reachable, count connected components, detect cycles, or compute a topological order — an ordering of tasks that respects dependencies, which is how build tools and migration runners decide what runs first.

Both visit every node and edge once: O(V + E). Forgetting the "seen" set is the classic bug — on a graph with a cycle, the traversal never ends.

#Dynamic programming

Some recursive problems solve the same subproblem many times. Counting the ways to climb n stairs taking 1 or 2 steps at a time: ways(n) = ways(n-1) + ways(n-2). Written naively, ways(40) makes over 300 million calls, because ways(38) is computed twice, ways(37) three times, and so on.

Dynamic programming stores each subproblem's answer so it's computed once. You can do it top-down (recursion plus a cache, called memoization) or bottom-up (fill a table from the smallest case):

func ClimbStairs(n int) int {
	if n <= 1 {
		return 1
	}
	prev, cur := 1, 1 // ways(0), ways(1)
	for range n - 1 {
		prev, cur = cur, prev+cur
	}
	return cur
}

That's O(n) time and O(1) space. The recipe for any DP problem is the same, and the dynamic programming note walks through it on a second example:

1. Define the state: what does dp[i] mean, in words?
2. Write the transition: how is dp[i] built from smaller states?
3. Set the base cases.
4. Pick the order to fill the table so dependencies come first.

If you can't say what dp[i] means in one sentence, you don't have a DP solution yet.

Greedy algorithms are DP's risky cousin: they take the locally best choice at every step and never reconsider. When greedy is correct (scheduling the most non-overlapping meetings by earliest end time) it's simpler and faster, but you must be able to argue why the local choice is safe. Making change with coins of 1, 3 and 4 for the amount 6 shows the trap: greedy takes 4+1+1, but 3+3 uses fewer coins.

#Practice

Implement NumIslands(grid [][]byte) int: given a grid of '1' (land) and '0' (water), count the islands — groups of land cells connected horizontally or vertically. State the time and space complexity, and test it on:

11000
11000
00100
00011

which has 3 islands.

func NumIslands(grid [][]byte) int {
	var sink func(r, c int)
	sink = func(r, c int) {
		if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[r]) || grid[r][c] != '1' {
			return
		}
		grid[r][c] = '0'
		sink(r+1, c)
		sink(r-1, c)
		sink(r, c+1)
		sink(r, c-1)
	}

	count := 0
	for r := range grid {
		for c := range grid[r] {
			if grid[r][c] == '1' {
				count++
				sink(r, c)
			}
		}
	}
	return count
}

func TestNumIslands(t *testing.T) {
	grid := [][]byte{
		[]byte("11000"),
		[]byte("11000"),
		[]byte("00100"),
		[]byte("00011"),
	}
	if got := NumIslands(grid); got != 3 {
		t.Errorf("NumIslands = %d; want 3", got)
	}
}

#Key takeaways

• Count how often the innermost work runs, keep the dominant term, and check the worst case.
• Trading memory for time — usually with a hash map or set — is the most common optimisation.
• Sorting costs O(n log n) and unlocks two-pointer and binary-search solutions; use slices.Sort and know when you need stability.
• Write binary search with an explicit invariant; you can also binary-search over an answer space.
• BFS finds shortest paths in unweighted graphs; DFS explores, finds components and orders dependencies. Both need a visited set.
• Dynamic programming caches overlapping subproblems: define the state, transition, base cases and fill order.