Know this before you start: “When sorting first unlocks the pattern”
When sorting first unlocks the pattern
Sorting costs O(n log n) once, but afterwards neighbours are related and two pointers, binary search or a single greedy pass become possible.
The idea
Unsorted data gives you no direction. Once sorted, small values are on the left and big ones on the right, so you know which way to move to make a sum bigger or smaller.
Sorting also puts equal values next to each other, which makes skipping duplicates trivial (3Sum), and puts overlapping intervals next to each other (merge intervals).
If the answer must report original positions, sort pairs of (value, index) or sort a copy.
See it step by step
3Sum: triples adding to 0 in [-1, 0, 1, 2, -1, -4]
- Sort → [-4, -1, -1, 0, 1, 2]
- Fix -4: two pointers on the rest look for +4: none.
- Fix -1: look for +1 → (-1, 0, 1) and (-1, -1, 2).
- The next -1 equals the previous fixed value: skip it, so no duplicate triples.
In code (Python)
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # same value fixed already
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
left += 1
while left < right and nums[left] == nums[left - 1]:
left += 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4])) # [[-1, -1, 2], [-1, 0, 1]]Sorting: O(n log n). 3Sum overall: O(n²).
When you'll use it
- Pairs or triples with a sum, skipping duplicate answers, intervals, greedy “pick the smallest first” problems.
Common mistakes
- Sorting when the problem needs original indexes (Two Sum): use a hash map instead.
- Forgetting sorting is O(n log n): it can't be part of an O(n) answer.
