Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

All patterns

Sorting

Pay O(n log n) once to make later steps linear or logarithmic.

time O(n log n)space O(1) to O(n)

What it is

Sorting exposes structure: equal items become adjacent, pairs can be found with two pointers, intervals can be merged in a single pass. It is often the cheapest way to remove an O(n²) search.

When to reach for it

  • Intervals, meeting rooms, merging
  • Duplicates or closest pairs
  • Greedy choices by order

Clues in the problem

  • Order of the original input does not matter
  • Comparisons between neighbours are enough

Template

def merge_intervals(iv):
iv.sort(key=lambda p: p[0])
out = [iv[0]]
for s, e in iv[1:]:
if s <= out[-1][1]:
out[-1][1] = max(out[-1][1], e)
else:
out.append([s, e])
return out

Practice problems

  • Merge Intervals
  • Meeting Rooms II
  • 3Sum
  • Non-overlapping Intervals

Common mistakes

  • Losing original indices
  • Sorting inside a loop
  • Assuming sort is stable when the language does not guarantee it