Greedy and Two-pass Array Patterns

Draw the problem first. A surprising number of “hard” array problems collapse into a single greedy pass (assume the local choice works, then check it) or two passes (left-to-right then right-to-left, or prefix × suffix).

Habits that help

• Sketch the array as bars or a chart before writing code. The shape usually gives the trick away.
• For greedy ideas, assume the local choice works, then hunt for a counter-example.
• The usual path: brute force, then memoised recursion (dynamic programming), then greedy or two-pass in O(n).

The problems

Problem	Insight	Complexity
Best Time to Buy and Sell Stock II (LeetCode 122)	Sum every up-move: profit += max(0, p[i] - p[i-1]). The same as buying every valley and selling every peak.	O(n) time, O(1) space
Jump Game (55)	Brute force is a decision tree (memoise “can reach the end from i”). Greedy: move the goal post. Walk right to left; if i + nums[i] >= goal, set goal = i. Reachable if goal == 0.	O(n), O(1)
Product of Array Except Self (238)	No division: prefix products × suffix products. [1,2,3,4] gives prefix [1,1,2,6] and suffix [24,12,4,1], so [24,12,8,6]. The second pass can reuse the output array.	O(n), O(1) extra
Gas Station (134)	If total gas < total cost, return -1. Otherwise one pass: track the tank, and when it goes negative restart from i + 1. That start is the answer.	O(n), O(1)
Candy (135)	Everyone gets 1. Left pass: if r[i] > r[i-1], c[i] = c[i-1] + 1. Right pass: if r[i] > r[i+1], c[i] = max(c[i], c[i+1] + 1). Sum. Each pass enforces one neighbour constraint; max merges them.	O(n), O(n)
Trapping Rain Water (42)	Water at i = min(maxLeft, maxRight) - h[i], if positive. Two arrays of running maxima, or two pointers that move whichever side has the smaller max.	O(n), O(1) with pointers

Trapping rain water, worked

h = [0,1,0,2,1,0,1,3,2,1,2,1]:

h	0	1	0	2	1	0	1	3	2	1	2	1
max L	0	0	1	1	2	2	2	2	3	3	3	3
max R	3	3	3	3	3	3	3	2	2	2	1	0
water	0	0	1	0	1	2	1	0	0	1	0	0

Total: 6. Here max L and max R exclude i itself, hence the clamp at zero.

Jump Game in code

// Move the goal post backwards; reachable if it gets to index 0
function canJump(nums: number[]) {
  let goal = nums.length - 1;
  for (let i = nums.length - 2; i >= 0; i--) if (i + nums[i] >= goal) goal = i;
  return goal === 0;
}