Sort + Two Pointers
Sort first, fix one number, then search for the other two efficiently.
0 of 3 problems solved
Sort + Two Pointers
Sort first, fix one number, then search for the other two efficiently.
- •Can I sort first to make pointer moves meaningful?
- •Can I reduce 3Sum into a fixed value plus Two Sum?
- •Did I remember to skip duplicates?
3Sum is easier when you stop thinking about three numbers at once. Sort the array first. Then freeze one number and turn the rest of the problem into a Two Sum search with left and right pointers. So really, 3Sum is just Two Sum with one extra setup step. The annoying part is duplicates, so you skip repeated values to avoid returning the same triplet again and again.
Sort once, fix one number, then let two pointers find the other two.
- 1Sort the array so pointer moves become meaningful.
- 2Pick one number as the fixed value.
- 3Set left and right pointers on the remaining portion of the array.
- 4If the total is too small, move left. If the total is too large, move right. If it is zero, record the triplet.
- 5Skip duplicate values for the fixed number and for the two pointers.
Not skipping duplicates creates repeated answers and makes the output look wrong even when the pointer logic is fine.
Sort Colors
Dutch National Flag: three pointers partition 0s, 1s, and 2s in one pass. Swap based on the value at mid while mid <= high.
First Missing Positive
Use the array as its own hash table: put value k at index k-1 for all 1 <= k <= n. Then scan for the first index where value != index + 1.