DSA & Algorithms
Part 2 of 21 · DSA Interview PatternsArrays & Two Pointers — Opposite Ends, Same Direction & Partition
Opposite-end and same-direction two pointers for sorted arrays, partitions, and O(n) pair scans.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The array is sorted, or you may sort it
Prefer
Two indexes that only move inward or forward
Each step throws away a region that cannot hold a better answer. The scan is linear after the sort.
- Opposite ends for pair sums, water, and palindromes.
- Same direction for dedup, move-zeroes, and Dutch-flag partitions.
- Extra memory stays constant once the array is ordered.
Alternative
Check every pair
Nested loops are correct and miss the O(n) structure the prompt is asking for.
- Time stays quadratic after you were handed a sorted array.
- You reach for a hash map and spend O(n) memory you did not need.
- The lo == hi case gets treated as a valid pair.
One pass, two indexes
Opposite ends for a target sum. Same direction when you compact the array.
- 1
Place the indexes
Ends of a sorted array, or read and write at the start. - 2
Move the side that is wrong
Sum too small: advance left. Too big: retreat right. - 3
Keep the write invariant
The write index is the next slot that already satisfies the rule.
Overview
Opposite-end and same-direction two pointers for sorted arrays, partitions, and O(n) pair scans.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use when the array is sorted (or can be sorted cheaply), or when you need a linear scan with two indices that only move one way.
Recognition cues
- pair with target sum on sorted array
- remove duplicates in-place / partition around a pivot
- container with most water / opposite-end pointers
- palindrome check from outside in
- Dutch national flag / three-way partition
Mental model
Decisions
- 1
Step 1 Sort or confirm sorted; lo = 0, hi = n - 1
- nextStep 2 lo still left of hi?
- ?
Step 2 lo still left of hi?
- noFailure path - no pair found, return a sentinel
- yesStep 3 Compare a[lo] + a[hi] with target
- 3
Failure path - no pair found, return a sentinel
- ?
Step 3 Compare a[lo] + a[hi] with target
- sum too smallStep 4a lo += 1
- sum too bigStep 4b hi -= 1
- equalStep 4c Record the pair; return, or skip duplicates and move both
- 5
Step 4a lo += 1
- nextStep 2 lo still left of hi?
- 6
Step 4b hi -= 1
- nextStep 2 lo still left of hi?
- 7
Step 4c Record the pair; return, or skip duplicates and move both
- nextStep 2 lo still left of hi?
Lesson map
Arrays & Two Pointers — Opposite Ends, Same Direction & Partition
Opposite-end and same-direction two pointers for sorted arrays, partitions, and O(n) pair scans.
Architecture. Step 1 Sort or confirm sorted; lo = 0, hi = n - 1 Ready. Step 2 lo still left of hi? Ready. Failure path - no pair found, return a sentinel Ready. Step 3 Compare a[lo] + a[hi] with target Ready. Step 4a lo += 1 Ready. Step 4b hi -= 1 Ready. Step 4c Record the pair; return, or skip duplicates and move both Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB S["Step 1 Sort or confirm sorted lo = 0, hi = n - 1 Ready"] C["Step 2 lo still left of hi? Ready"] N["Failure path - no pair found, return a sentinel Ready"] M["Step 3 Compare a[lo] + a[hi] with target Ready"] L["Step 4a lo += 1 Ready"] H["Step 4b hi -= 1 Ready"] D["Step 4c Record the pair return, or skip duplicates and move both Ready"] S -->|continues| C C -->|no| N C -->|yes| M M -->|sum too small| L M -->|sum too big| H M -->|equal| D L -->|continues| C H -->|continues| C D -->|continues| C
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Opposite-end scan: O(n) time, O(1) space after sort (O(n log n) if you must sort).
- Same-direction write pointer: O(n) time, O(1) extra space.
Common pitfalls & interview traps
LeetCode drill (real problems)
- Two Sum II - Input Array Is Sorted
- Container With Most Water
- 3Sum
- Remove Duplicates from Sorted Array
- Trapping Rain Water
- Sort Colors
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
When do opposite-end pointers work?
Answer
When the decision moves one pointer monotonically - usually sorted or unimodal structure.
Two Sum sorted vs hash?
Answer
Sorted uses two pointers O(1) space; unsorted uses hash O(n) space expected O(n) time.
How does 3Sum use this?
Answer
Sort, fix i, two-pointer the residual pair; skip duplicates.
Dutch national flag?
Answer
Three pointers low/mid/high partitioning 0/1/2 in one pass.
Common trap in Container With Most Water?
Answer
Always move the shorter side, never the taller.
In-place dedup invariant?
Answer
Write index is the next free slot for unique values; read scans ahead.