Know this before you start: “Sorting costs O(n log n)”
Sorting costs O(n log n)
A good comparison sort takes . It's often worth paying: once the array is in order, the rest of the answer is frequently one pass, or a look at the ends.
The idea
Python's sorted() and list.sort(), Java's Arrays.sort and C++'s sort all run in O(n log n). For a million numbers that's about 20 million steps, fine; checking every pair would be half a trillion.
So when the compares all pairs (), ask whether sorted order would bring the answer to the front, the ends or next-door neighbours.
Sorting changes the order, so it can't be used when the answer needs the original positions, unless you sort (value, index) pairs.
Worked example
Largest product of three numbers in [−10, −10, 1, 3, 2]
- Sorted: [−10, −10, 1, 2, 3]. The answer can only use the ends.
- Three largest: 1 × 2 × 3 = 6. Two smallest (two negatives make a positive) × largest: −10 × −10 × 3 = 300.
- Answer 300, after one sort and two multiplications: O(n log n), not O(n³) over every triple.
Pseudocode
The steps in plain words. ← means “set to”; indentation shows what's inside what.
See it run
The worked example, step by step, beside the Python. The highlighted line is the one running.
Step-by-step
nums = [-10, -10, 1, 3, 2]
nums
sorted
Solution · Pythonline 2
def max_product_of_three(nums):a = sorted(nums) # O(n log n)return max(a[-1] * a[-2] * a[-3], # three largesta[0] * a[1] * a[-1]) # two most negative × largest print(max_product_of_three([-10, -10, 1, 3, 2])) # 300print(max_product_of_three([1, 2, 3, 4])) # 24 # Sort by a key, keeping where each item came fromnums = [30, 10, 20]print(sorted(range(len(nums)), key=lambda i: nums[i])) # [1, 2, 0]Step 1 of 4· line 2
Pay O(n log n) once to sort. Now the candidates can only be at the ends.
O(n log n) to sort. Python's sort uses ; the scan afterwards is usually O(n).
When you'll use it
- Closest pairs, duplicates, meeting rooms and , “largest / smallest k”, on a sorted array, grouping by sorted letters.
In the wild · Every “Sort by” button: Sorting a spreadsheet by price, then by name, needs a stable sort, which is why Python and JavaScript both use merge-sort-based TimSort.
Common mistakes
- Sorting inside a loop: n sorts is O(n² log n).
- Sorting when the answer needs original indexes, without keeping them alongside.