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]

  1. Sorted: [−10, −10, 1, 2, 3]. The answer can only use the ends.
  2. Three largest: 1 × 2 × 3 = 6. Two smallest (two negatives make a positive) × largest: −10 × −10 × 3 = 300.
  3. 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.

sort nums O(n log n)
the answer now sits at the ends:
three largest vs two smallest × largest
return the larger O(1)

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

0-10
1-10
21
33
42

sorted

0-10
1-10
21
32
43

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 largest
a[0] * a[1] * a[-1]) # two most negative × largest
print(max_product_of_three([-10, -10, 1, 3, 2])) # 300
print(max_product_of_three([1, 2, 3, 4])) # 24
# Sort by a key, keeping where each item came from
nums = [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.

Practise it · before the Sorting problems

Largest product of three

Return the largest product of any three numbers in nums (it has at least three).

Input nums = [1, 2, 3, 4]

Output 24

Input nums = [-10, -10, 1, 3, 2]

Output 300

−10 × −10 × 3: two negatives make a positive.

Pass every test and this concept is marked as known on the roadmap and on every problem that needs it.

Your code

Tab / Shift+Tab indent · ⌘/Ctrl+/ comments · ⌘/Ctrl+Enter runs · Esc leaves the editor

Stuck?