Sort, Then One Pass

This page is about a habit rather than an algorithm. A large class of problems has no obvious approach until you sort the input, at which point the answer is a single loop.

What makes them worth studying is not the loop, which is trivial, but the argument for why the sorted arrangement is optimal. That argument is nearly always an exchange argument. Assume an optimal solution that differs from the sorted one, find two elements that are "crossed", and show that uncrossing them does not make the answer worse. Repeat until you have the sorted arrangement, so it is optimal too.

Minimum difference pair

Find the two values in an array with the smallest difference, where checking all pairs is O(n²).

Sort, and the closest pair must be adjacent. If two values are closest but not adjacent after sorting, then something sits between them, and that something is closer to each of them than they are to each other, which contradicts the assumption. So only the n-1 adjacent pairs need checking, giving O(n log n) dominated by the sort.

Wave form

Rearrange so the array alternates up and down: a[0] ≥ a[1] ≤ a[2] ≥ a[3] and so on.

Sort ascending, then swap each adjacent pair. After sorting, a[i] is at most a[i+1] everywhere. Swapping positions 0 and 1, 2 and 3, and so on makes every even index hold the larger of its pair, which is enough to satisfy the pattern on both sides.

There is also an O(n) solution that skips the sort entirely: walk the array and swap any adjacent pair that violates the pattern. It works, and it produces a different valid answer. Worth knowing that "sort first" is the obvious approach here rather than the only one.

Maximum sum of i × arr[i]

Choose an arrangement maximizing the sum of each element multiplied by its index.

Sort ascending. The largest index carries the most weight, so it should hold the largest value. The exchange argument: if a larger value sits at a smaller index than some smaller value, swapping them increases the sum, because the larger value gains more weight than the smaller one loses. So no arrangement other than the sorted one can be optimal.

Tywin's war strategy

Two armies of units with strength values, paired one-to-one. A matchup is won when your unit is strictly stronger, and the goal is to maximize the number of matchups won.

Sort both. Then walk the enemy from weakest upward, and against each one spend the cheapest of your units that can still beat it. Units too weak to beat the current enemy can never beat any later one either, since the enemies only get stronger, so they are spent as sacrifices.

The greedy choice is safe because using a stronger unit than necessary can only reduce your options later, never improve them. This is the same shape of argument as the interval-scheduling greedy.

Switch the widget above to see it run, and note that the answer is a count of wins rather than an arrangement.

Minimum moves to seat everyone

Given passenger positions and chair positions on a line, assign each passenger a chair minimizing the total distance moved.

Sort both and pair them in order. The exchange argument again: suppose two assignments cross, so passenger at p1 < p2 goes to chair c2 > c1. Uncrossing them, so p1 takes c1 and p2 takes c2, never increases the total distance, and often reduces it. Since any assignment can be uncrossed pair by pair without getting worse, the fully uncrossed one, which is the sorted pairing, is optimal.

The pattern

In every row the code is a loop of two or three lines. If a problem feels like it needs to try every arrangement, it is worth asking whether sorting first makes one particular arrangement provably best.

In code

function minimumDifference(a) {
  const s = [...a].sort((x, y) => x - y);
  let best = Infinity;
  for (let i = 0; i + 1 < s.length; i++) best = Math.min(best, s[i + 1] - s[i]);
  return best;
}

function waveForm(a) {
  const s = [...a].sort((x, y) => x - y);
  for (let i = 0; i + 1 < s.length; i += 2) [s[i], s[i + 1]] = [s[i + 1], s[i]];
  return s;
}

function maxIndexSum(a) {
  const s = [...a].sort((x, y) => x - y);          // biggest value, biggest index
  return s.reduce((total, v, i) => total + i * v, 0);
}

function maxWins(mine, theirs) {
  const a = [...mine].sort((x, y) => x - y);
  const e = [...theirs].sort((x, y) => x - y);
  let wins = 0, i = 0;

  for (let j = 0; j < e.length && i < a.length; j++) {
    // Skip units too weak to beat this enemy: they cannot beat any later one.
    while (i < a.length && a[i] <= e[j]) i++;
    if (i < a.length) { wins++; i++; }
  }
  return wins;
}

function minimumMoves(people, chairs) {
  const p = [...people].sort((x, y) => x - y);
  const c = [...chairs].sort((x, y) => x - y);
  return p.reduce((total, v, i) => total + Math.abs(v - c[i]), 0);
}

Check yourself

Sources and practice

Sedgewick and Wayne's Algorithms sorting chapter covers the algorithms in this section with full analysis. For drilling the problem patterns under time pressure, the CSES Problem Set has a sorting and searching section built almost entirely from the techniques on these pages.