Common Array Patterns

You're already familiar with two pointers, sliding windows, and prefix sums as individual techniques. This lesson dives deeper into why these patterns solve certain problems optimally and how to spot which pattern a problem uses.

All three patterns leverage a fundamental property of arrays: contiguous memory allocation and $O(1)$ index access. This is why they're so efficient here: you can move pointers freely, advance a window in constant time, and precompute running sums without performance penalties.

Two pointers

The two pointers pattern places one pointer at each end of the array and moves them toward each other based on some condition. It works on sorted arrays and trades the O(n) cost of a nested loop for a single $O(n)$ pass.

The problem we will use to anchor this is: given a sorted array, remove duplicates in place and return the new length. One pointer scans forward, and the other marks the boundary of unique elements. When the scanner finds a new unique value, the boundary pointer advances, and the value is written there.

Time and space complexity

• Time $O(n)$: Single pass through the array.

• Space $O(1)$ ...