Arrays & Strings

Converging pointers and read/write pointer patterns

Arrays: Two Pointers

Active InputTarget = 10
Array
1
0
2
1
3
2
4
3
6
4
8
5
11
6
Choose a two-pointer pattern to animate one step at a time.

Three Two-Pointer Patterns

1. Two Sum II works because the input is sorted. If the sum is too small, move the left pointer. If the sum is too large, move the right pointer.

2. Container With Most Water compares the current area and then discards the shorter side, because keeping it cannot improve the next area with a smaller width.

3. Remove Duplicates uses a read pointer to scan values and a write pointer to compact the unique prefix in place.

Complexity

Two Sum II
Time:O(n)
Space:O(1)
Container
Time:O(n)
Space:O(1)
Remove Duplicates
Time:O(n)
Space:O(1)