Two Pointers on Sorted Array
Use sorted order to decide whether to move left or right.
0 of 3 problems solved
Two Pointers on Sorted Array
Use sorted order to decide whether to move left or right.
- •Is the array sorted?
- •Can the current sum tell me which pointer to move?
- •Am I moving only one pointer per step?
This is Two Sum again, but now the array is sorted. That sorted order is the whole gift. Put one pointer on the smallest number and one on the biggest. If the sum is too small, you need a bigger number, so move the left pointer. If the sum is too big, you need a smaller number, so move the right pointer. The sorted array tells you exactly which direction makes sense.
Sorting removes the guesswork. The current sum tells you exactly which pointer to move.
- 1Set left to the first index and right to the last index.
- 2Compute the sum of numbers at left and right.
- 3If the sum is too small, move left to the right.
- 4If the sum is too large, move right to the left.
- 5If the sum matches the target, return the answer.
Moving both pointers at once throws away information. Only one side should move, based on whether the sum is too small or too large.
3Sum Closest
Sort first, fix one pointer, scan with left/right. Track the smallest absolute difference from target and update on each iteration.
Median of Two Sorted Arrays
Binary search on the smaller array to find the partition where combined left halves have exactly half the total count and cross-boundary values stay in order.