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 Java arrays: $O(1)$ index access. This is why they're so efficient here: you can move integer indices freely, advance a window in constant time, and precompute running sums without performance penalties.

Two pointers

The two pointers pattern places one index 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 )^ 2$ 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 index scans forward, and the other marks the boundary of unique elements. When the scanner finds a new unique value, the boundary index advances, and the value is written there.

Time and space complexity

• Time $O(n)$ ...