Arrays — Index Thinking

Treat every array problem as: What do I know at index i? What must I remember from the past?

Suno.Arraymeinnumbershain.Continuoussubarraykamaxsumchahiye.Emptynahi—kamsekamekelement.

Listen. You get an array. Find the max sum of a contiguous subarray. At least one element.

0:00 / 1:02

Speed

Practice maximum-subarray

When to use this

Contiguous memory, random access O(1)
In-place swaps / two writes (Move Zeroes)
Prefix sums / running min-max (Best Time to Buy Stock, Kadane)

C++ template

// Running best pattern
int best = nums[0];
for (int i = 1; i < n; i++) {
    // update state using nums[i]
    best = max(best, candidate);
}
return best;

Dry run

Kadane on [-2,1,-3,4,-1,2,1,-5,4] ends with best=6.

Pitfalls

Off-by-one on rotate
int overflow on sums
Forgetting in-place mutation

Say this in the interview

One scan, O(n) time, O(1) extra unless I need a map.

Problems in this topic (14)

Each opens teach-first (animated when available), then the code panel.