Common Array Patterns
Explore how to recognize and apply key array patterns—two pointers, sliding window, and prefix sums—to solve common interview problems efficiently using C++. Understand when to use each pattern based on problem signals like sorted arrays, contiguous subarrays, or range-sum queries.
We'll cover the following...
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, including C++ arrays and std::vector: contiguous storage and
Interview lens: The most valuable skill in an array interview is recognizing which pattern to reach for within the first minute of reading the problem.
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) cost of a nested loop for a single
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
: Single pass through the array. Space
: Modified in place, with no extra allocation. ...