Set 01 - Arrays & Two Pointers

Use Practice Loop if you need a reset.

Problems

Deliverables

• Write a 1-line invariant for each problem.
• Note 1 edge case or pitfall per problem.
• Record time-to-first-correct solution.

Notes

53. Maximum Subarray (Kadane)

Pattern: DP compressed into 1 variable

Invariant: cur = best subarray sum that must end at i

Update: cur = max(nums[i], cur + nums[i]), best = max(best, cur)

Pitfall: initializing wrong when all numbers are negative → start with best = cur = nums[0]

238. Product of Array Except Self

Pattern: prefix * suffix (two passes)

Invariant 1 (left pass): res[i] = product(nums[0..i-1])

Invariant 2 (right pass): suffix = product(nums[i+1..n-1]), then res[i] *= suffix

Pitfall you hit earlier: don’t assign res[i] when res=[] → use res=[1]*n

217. Contains Duplicate

Pattern: set membership

Invariant: after processing first k numbers, seen contains exactly those k values

Rule: if x in seen → duplicate found

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

121. Best Time to Buy and Sell Stock

Pattern: “min prefix” + best profit so far

Invariant:

• min_price = minimum price seen so far

• best = maximum profit achievable up to today

  Update: best = max(best, price - min_price) then min_price = min(min_price, price)

  Key insight: you’re basically doing Kadane on price differences, but this invariant is simpler.

283. Move Zeroes

Pattern: slow/fast pointer (stable compaction)

Invariant: nums[0..slow-1] are all the non-zeros seen so far in original order

Update: scan with fast; when non-zero, swap/assign into slow then slow += 1

Pitfall: preserving order matters → use stable compaction, not random swaps.

167. Two Sum II (sorted)

Pattern: two pointers on sorted array

Invariant: answer (if exists) is always inside [l, r]

Move rule:

• sum too small → l++

• sum too big → r--

  Why it works: pointer moves are monotonic with sorted order.

125. Valid Palindrome

Pattern: two pointers + filtering

Invariant: all characters outside [l, r] have already been validated as matching

Step: skip non-alnum on both sides; compare lowercase; move inward

Pitfall: forgetting to skip both sides correctly.

1266. Minimum Time Visiting All Points

Pattern: geometry greedy (Chebyshev distance)

Invariant: minimal time from point A to B equals max(|dx|, |dy|) because you can move diagonally to reduce both each step

Total: sum that value for every consecutive pair

Common mistake: using |dx|+|dy| (Manhattan) instead of max.

The “template buckets” (how to recognize next time)

Bucket A — “Scan + maintain best so far”

• 53 (Kadane), 121 (min_price/best)

  Trigger words: maximum/minimum, “best subarray/profit,” continuous scan

  Invariant style: “best ending here” / “min prefix”

Bucket B — “Two pointers”

• 167 (sorted), 125 (palindrome), 283 (compaction)

  Trigger words: sorted array, palindrome, remove/move elements in-place

  Invariant style: “outside is solved; inside remains”

Bucket C — “Two-pass accumulation”

• 238 prefix/suffix

  Trigger words: “except self”, “for each i depends on left and right”

  Invariant style: “left product already correct” then “multiply right product”

Bucket D — “Set / uniqueness”

• 217

  Trigger words: duplicates / seen before

  Invariant style: “set equals processed items”

Bucket E — “Math shortcut”

• 1266

  Trigger words: grid moves, diagonal allowed, shortest time/steps

  Invariant style: distance formula is preserved

Review

• Time spent + where you got stuck?
• Biggest mistake or missed edge case?
• One concrete improvement for next time.