Lab: paradigm problems
Four problems — identify the correct paradigm, then implement. Activity selection (greedy), kth largest (divide and conquer), combination sum (backtracking), and maximum subarray (DP).
- Identify and apply greedy, divide-and-conquer, backtracking, and DP to unfamiliar problems
- Implement activity selection, kth largest (quickselect), combination sum, and maximum subarray
For each problem below, the most important step is identifying the paradigm before writing any code. Read the "think first" prompt, decide which paradigm fits, then check your implementation.
Problem 1: activity selection
Problem. Given a list of intervals [start, end], return the maximum
number of non-overlapping intervals you can select.
activity_selection([[1,3],[2,4],[3,5],[0,6]]) → 2.
Think first. Does the locally optimal choice (earliest finish time) lead to a globally optimal solution? Yes — this is the classic greedy interval scheduling problem. Sort by end time, greedily select.
Why this paradigm? Greedy — the exchange argument proves that always taking the earliest-finishing interval never closes off a better solution.
Implement activity_selection(intervals) returning the maximum number of non-overlapping intervals. Sort by end time, greedily select.
activity_selection([[1,3],[2,4],[3,5],[0,6]]) → 2Problem 2: kth largest element
Problem. Given an unsorted list and an integer k, return the kth largest
element. kth_largest([3, 2, 1, 5, 6, 4], 2) → 5.
Think first. Sorting works in O(n log n) but you only need the kth element. Quickselect partitions around a pivot: elements larger than the pivot go left, smaller go right. Recurse into only the relevant partition. Average O(n).
Why this paradigm? Divide and conquer — partition discards half the search space, just like binary search, but without a sorted array.
Implement kth_largest(nums, k) using quickselect. Partition around the last element as pivot: elements >= pivot go to the left portion.
kth_largest([3,2,1,5,6,4], 2) → 5Problem 3: combination sum
Problem. Given a list of distinct positive integers candidates and a
target integer, return all unique combinations that sum to the target. The
same number may be used multiple times.
combination_sum([2, 3, 6, 7], 7) → [[2, 2, 3], [7]].
Think first. There is no greedy shortcut (taking the largest item first can miss valid combinations). DP could enumerate totals but not the actual combinations. Backtracking fits naturally: build a combination incrementally, recurse allowing repeats of the same element, backtrack when you overshoot.
Why this paradigm? Backtracking — enumerate all valid combinations with pruning (skip candidates that would exceed the remaining target).
Implement combination_sum(candidates, target) returning all unique combinations summing to target. Each candidate may be reused. Sort candidates first to enable pruning.
combination_sum([2,3,6,7], 7) → [[2, 2, 3], [7]]Problem 4: maximum subarray
Problem. Given a list of integers (may include negatives), return the
maximum sum of any contiguous subarray.
maximum_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) → 6.
Think first. Checking every subarray is O(n²). Greedy makes a locally
attractive choice — extend the running sum unless it has gone negative — but
the optimal sub-problem structure is cleaner as DP. dp[i] = max subarray sum
ending at index i. This is Kadane's algorithm: O(n), O(1) space with a
rolling variable.
Why this paradigm? DP — the running sum at each position depends on the running sum at the previous position. The "start fresh here" vs "extend" decision is a recurrence, not a pure greedy exchange.
Implement maximum_subarray(nums) using Kadane's algorithm: at each position, the best subarray ending here is either 'extend the previous' or 'start fresh here'.
maximum_subarray([-2,1,-3,4,-1,2,1,-5,4]) → 6maximum_subarray([-1,-2,-3]) → -1Where to go next
The Challenges module contains four standalone algorithmic problems that draw on everything from this tier. Work through them to consolidate the paradigm recognition skills practised here.