Challenge: trapping rain water
Calculate the total water trapped between bars in O(n) time and O(1) space using a two-pointer approach.
- Solve trapping rain water in O(n) time and O(1) space
Optional challenge. These puzzles have efficiency checks built into the test suite, so brute-force solutions are rejected deterministically — no timing involved.
Given an array of non-negative integers representing bar heights in a
histogram, return the total amount of water that can be trapped between the
bars after rain. trap([0,1,0,2,1,0,1,3,2,1,2,1]) → 6.
The naive approach — for each bar, find the tallest bar to its left and right, then compute how much water sits above it — is O(n²) or O(n) with precomputed prefix/suffix arrays using O(n) space. There is a way to do it in O(n) time and O(1) space.
Hint: use two pointers starting at both ends. Track the maximum height seen from the left so far and from the right so far. At each step, process the side with the smaller maximum — water above that bar is bounded by the smaller of the two maxima, and you already know the smaller one.
Write trap(height) returning the total water trapped. Aim for O(n) time and O(1) space using two pointers.
trap([0,1,0,2,1,0,1,3,2,1,2,1]) → 6trap([3,0,0,2,0,4]) → 10Lab: 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).
Challenge: longest substring without repeating characters
Find the length of the longest substring without repeating characters in O(n) time using a sliding window.