Learn

Your comparator subtracts, and two large numbers sort the wrong way round

19 October 2026 · One mistake, one counterexample

Half the interval problems you practise start the same way: sort by start, then walk. You write the comparator in one line, the sample passes, and you move on to the interesting part. Then the interviewer says the coordinates can be any 32-bit signed integer, and the first line is the one that is wrong.

The situation

You are given intervals as int[][], each pair a start and an end, and the first step of your solution is to sort them by start. Most people type this without thinking:

static void sortByStart(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
}

On {{5, 9}, {1, 4}, {7, 8}} it returns {{1, 4}, {5, 9}, {7, 8}}. Green.

The input that breaks it

Two intervals: {{1_000_000_000, 5}, {-2_000_000_000, 3}}. Both starts fit comfortably in an int. The sorted result keeps the billion first, in either input order.

Do the arithmetic the comparator does. -2_000_000_000 - 1_000_000_000 is minus three billion, which does not fit in an int, so it wraps to 1_294_967_296. A positive result means "the first argument is larger", so the comparator says minus two billion is greater than one billion. Ask it the other way round and the difference wraps to a negative number, so it agrees with itself and is consistently wrong. Nothing throws. The array is simply out of order, and every step after the sort is built on that.

The hidden assumption is the sign of the difference is the sign of the comparison. It holds only while the difference fits in an int. Two values from opposite ends of the range produce a difference about twice as wide as the type.

It gets worse with more data. With values near the limits, the comparator can contradict itself: for -1 and Integer.MAX_VALUE both orders of the call return a negative number, so each value claims to come first. Sort 200 random arrays of 100 int values drawn from the whole range with a - b, on a recent JDK, and 197 come out unsorted, while the other 3 throw IllegalArgumentException because the sort noticed the contract was broken. None comes out right.

The fix and the invariant

Compare, do not subtract:

static void sortByStart(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
}

Integer.compare(a[0], b[0]) works too. Both return the sign without computing a difference, so there is nothing to overflow. The invariant to say is short: a comparator must give the opposite answer when you swap its arguments, and its answer must come from comparing the values, not from arithmetic on them.

In Python the trap does not exist, because integers do not overflow, and the idiomatic version uses a key rather than a comparator:

intervals.sort(key=lambda pair: pair[0])

That difference is worth saying aloud too. It shows the interviewer you know which of your habits come from which language.

What to say out loud

When you write the sort: "I'm sorting by start with Integer.compare rather than subtracting, because the starts can be anywhere in the int range and the difference of two of them can overflow." That is one sentence, said once, and it answers a follow-up question before it is asked. If you have already written a - b, say so and fix it: "That subtraction can overflow for values far apart; let me compare instead." Catching it yourself counts for more than never mentioning it.

The same sentence works for any comparator you write in Java: sorting by end, by length, by a score. Length is end - start, which can overflow on its own before you even compare it, so check the inputs of the comparison as well as the comparison.

The exercise

1. Open the last three Java solutions you wrote that sort anything, and find every comparator.
2. For each one that subtracts, write down the two smallest inputs that make the difference overflow. Use one value near Integer.MAX_VALUE and one near Integer.MIN_VALUE, then try smaller values until it stops breaking.
3. Run the comparator on both orders of those two inputs and check that the signs are opposite. If they are not, you have found the bug without a single test case passing or failing.
4. Replace it with Integer.compare or Comparator.comparingInt, and say the one sentence from the section above while you type.
5. Repeat for a comparator on a derived value, such as interval length, and decide whether the value itself needs to be a long.

Where this fits in Gadfly

Gadfly has four rooms, and in the algorithms room you code in Java or Python. In tutor mode it asks the next question rather than revealing the solution, so a question like "what range can the starts take, and what does your comparator do at the ends of it?" is the kind it would put to you. Saying "I'm stuck" gives one more step, up to pseudocode, never finished code.