Arrays
Loading
Loading
Arrays
Carrying state through a single pass, and filtering with a write pointer.
By the end of this chapter
Many array questions look like they need a nested loop because each position depends on everything before it. Usually that dependency can be carried forward in a variable instead.
# Recomputes the prefix every time: O(n^2)def prefix_maxima_slow(nums): return [max(nums[:i + 1]) for i in range(len(nums))] # Carries the answer forward: O(n)def prefix_maxima(nums): result = [] best = float("-inf") for value in nums: best = max(best, value) result.append(best) return resultConcept
Filtering in place uses two indices over the same array: one reads every element, the other marks where the next kept element belongs. The reader always moves; the writer only moves when something is worth keeping.
Before and after
Input
After compacting
Concept
The write index advances only when something is kept, and the read index advances every iteration. So write ≤ read at all times, which means every position written to has already been read. You can never clobber a value you still need.
def keep_positive(nums): write = 0 for value in nums: # read every element if value > 0: nums[write] = value # place the kept ones from the front write += 1 return write # length of the filtered prefixApproaches
The input must not be mutated, or the caller still needs the original. Genuinely the right answer then — it is not a mistake, it is a different constraint.
The array may be mutated and the problem asks for O(1) extra space or a returned count.
Can you recognise the pattern?
An array must be filtered, deduplicated or partitioned, and the problem says to do it in place with no extra array.
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: try 2 practice problems.
The kept values stay in their original relative order, and nothing was allocated to do it.