Why (a, b) -> a - b Is a Bug in Java Comparators

If you've solved enough LeetCode problems in Java, you've written this:

PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> a - b);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
Arrays.sort(intervals, (x, y) -> x[1] - y[1]);

It passes most test cases, and that's what makes it dangerous. a - b is not a correct comparator for int. When the subtraction overflows, the sign flips, and your sort or heap silently returns the wrong order. No exception and no warning, just wrong answers on edge-case inputs (and a likely follow-up question in an interview).

This post shows the failure with real output, two related traps (long and double casts), and the correct one-liners.

Why it breaks

A Comparator only needs to return the right sign: negative if a < b, zero if equal, positive if a > b. a - b gets the sign right only while the true difference fits in an int.

An int holds −2,147,483,648 to 2,147,483,647. The difference between two ints can be almost twice that range. When it doesn't fit, Java wraps it around silently (two's-complement overflow), and the sign can come out reversed.

See it fail (complete program)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;

public class ComparatorOverflow {

    // The "LeetCode classic" comparators
    static final Comparator<Integer> SUBTRACT_ASC  = (a, b) -> a - b;
    static final Comparator<Integer> SUBTRACT_DESC = (a, b) -> b - a;

    // Correct versions
    static final Comparator<Integer> COMPARE_ASC  = Integer::compare;
    static final Comparator<Integer> COMPARE_DESC = Comparator.reverseOrder();

    public static void main(String[] args) {
        System.out.println("Java " + Runtime.version());

        // 1. Why it breaks: the subtraction itself overflows
        int a = Integer.MIN_VALUE, b = 1;
        System.out.println("\n1) a = MIN_VALUE, b = 1");
        System.out.println("   a - b              = " + (a - b) + "   (positive => 'a is bigger', wrong)");
        System.out.println("   Integer.compare(a,b) = " + Integer.compare(a, b));

        // 2. Sorting with a - b
        List<Integer> data = List.of(3, Integer.MIN_VALUE, -7, Integer.MAX_VALUE, 0, 42);
        System.out.println("\n2) sort " + data);
        System.out.println("   (a, b) -> a - b    : " + sorted(data, SUBTRACT_ASC));
        System.out.println("   Integer::compare   : " + sorted(data, COMPARE_ASC));

        // 3. Max-heap with b - a
        System.out.println("\n3) max-heap, poll order");
        System.out.println("   (a, b) -> b - a       : " + drain(new PriorityQueue<>(SUBTRACT_DESC), data));
        System.out.println("   Comparator.reverseOrder(): " + drain(new PriorityQueue<>(COMPARE_DESC), data));

        // 4. The same bug on int[] pairs (intervals / Dijkstra / "sort by end")
        int[][] intervals = { {1, 2_000_000_000}, {5, -2_000_000_000}, {3, 10} };
        int[][] bad = intervals.clone(), good = intervals.clone();
        Arrays.sort(bad, (x, y) -> x[1] - y[1]);
        Arrays.sort(good, Comparator.comparingInt(x -> x[1]));
        System.out.println("\n4) sort intervals by end");
        System.out.println("   (x, y) -> x[1] - y[1]          : " + Arrays.deepToString(bad));
        System.out.println("   Comparator.comparingInt(x[1])  : " + Arrays.deepToString(good));

        // 5. long and double: casting the difference is a different bug
        long big1 = 3_000_000_000L, big2 = 0L;
        System.out.println("\n5) long/double casts");
        System.out.println("   (int) (3_000_000_000L - 0L) = " + (int) (big1 - big2) + "   (sign flipped by truncation)");
        System.out.println("   Long.compare               = " + Long.compare(big1, big2));
        double p = 0.3, q = 0.7;
        System.out.println("   (int) (0.3 - 0.7)          = " + (int) (p - q) + "   (0 => 'equal', wrong)");
        System.out.println("   Double.compare             = " + Double.compare(p, q));

        // 6. How often does a - b give the wrong sign for random ints?
        Random rnd = new Random(42);
        int trials = 1_000_000, wrong = 0;
        for (int i = 0; i < trials; i++) {
            int x = rnd.nextInt(), y = rnd.nextInt();
            if (Integer.signum(x - y) != Integer.signum(Integer.compare(x, y))) wrong++;
        }
        System.out.printf("%n6) random full-range ints: a - b had the wrong sign in %,d of %,d pairs (%.1f%%)%n",
                wrong, trials, 100.0 * wrong / trials);
    }

    static List<Integer> sorted(List<Integer> in, Comparator<Integer> c) {
        List<Integer> copy = new ArrayList<>(in);
        copy.sort(c);
        return copy;
    }

    static List<Integer> drain(PriorityQueue<Integer> pq, List<Integer> in) {
        pq.addAll(in);
        List<Integer> out = new ArrayList<>();
        while (!pq.isEmpty()) out.add(pq.poll());
        return out;
    }
}

javac -d out ComparatorOverflow.java
java -cp out ComparatorOverflow

Real output (OpenJDK 25.0.4; the behaviour is the same on any Java version, since int overflow semantics have never changed):

Java 25.0.4.1+1-1-deb13u1-Debian

1) a = MIN_VALUE, b = 1
   a - b              = 2147483647   (positive => 'a is bigger', wrong)
   Integer.compare(a,b) = -1

2) sort [3, -2147483648, -7, 2147483647, 0, 42]
   (a, b) -> a - b    : [0, 3, 42, 2147483647, -2147483648, -7]
   Integer::compare   : [-2147483648, -7, 0, 3, 42, 2147483647]

3) max-heap, poll order
   (a, b) -> b - a       : [-7, -2147483648, 2147483647, 42, 3, 0]
   Comparator.reverseOrder(): [2147483647, 42, 3, 0, -7, -2147483648]

4) sort intervals by end
   (x, y) -> x[1] - y[1]          : [[1, 2000000000], [5, -2000000000], [3, 10]]
   Comparator.comparingInt(x[1])  : [[5, -2000000000], [3, 10], [1, 2000000000]]

5) long/double casts
   (int) (3_000_000_000L - 0L) = -1294967296   (sign flipped by truncation)
   Long.compare               = 1
   (int) (0.3 - 0.7)          = 0   (0 => 'equal', wrong)
   Double.compare             = -1

6) random full-range ints: a - b had the wrong sign in 250,191 of 1,000,000 pairs (25.0%)

What the output shows

1. The root cause. MIN_VALUE - 1 comes out as 2147483647, so the comparator claims the smallest int is bigger than 1.
2. List.sort returns a wrong order. -2147483648 and -7 end up after 2147483647. The sort doesn't fail. It does exactly what the broken comparator tells it.
3. The max-heap pops in nonsense order. (a, b) -> b - a polls -7 first. In a "top K" or "kth largest" problem, that's a wrong answer.
4. int[] pairs have the same bug. Sorting intervals by end with x[1] - y[1] leaves them unsorted once the values are large. LeetCode constraints like -2^31 <= x <= 2^31 - 1 exist to catch exactly this.
5. The cast traps:
   • long: (int) (a - b) keeps only the low 32 bits. Here a positive difference of 3,000,000,000 became -1294967296, so the sign flipped.
   • double: (int) (0.3 - 0.7) truncates -0.4 to 0, so the comparator says two different prices are equal. A TreeMap or TreeSet using it will treat them as duplicates and drop one.
6. How common is it? For uniformly random full-range ints, a - b gave the wrong sign in 25.0% of a million pairs (seeded run, so it's reproducible). With small inputs it never shows up, which is why it survives code review.

The correct versions

You want	Write this	Avoid
ascending ints	Integer::compare or Comparator.naturalOrder()	(a, b) -> a - b
descending ints (max-heap)	Comparator.reverseOrder() or (a, b) -> Integer.compare(b, a)	(a, b) -> b - a
sort int[] by a column	Comparator.comparingInt(x -> x[1])	(x, y) -> x[1] - y[1]
then by another column	Comparator.comparingInt((int[] x) -> x[1]).thenComparingInt(x -> x[0])	chained subtraction
longs	Long.compare(a, b) or Comparator.comparingLong(...)	(int) (a - b)
doubles	Double.compare(a, b) or Comparator.comparingDouble(...)	(int) (a - b)
objects by field	Comparator.comparing(Employee::salary)	e1.salary() - e2.salary()

Integer.compare(a, b) is equivalent to (a < b) ? -1 : ((a == b) ? 0 : 1), with no arithmetic and so nothing to overflow. Double.compare also handles -0.0 and NaN consistently, which plain < doesn't.

"But my inputs are small"

Sometimes that's true. If the problem guarantees 0 <= x <= 10^4, a - b can't overflow. Still use Integer.compare:

• It costs nothing. It's just as short, and clearer about intent.
• The constraints change. Code written for small IDs gets reused for timestamps, prices in paise, or hash values.
• Interviewers notice. "What happens if the values are near Integer.MAX_VALUE?" is a standard follow-up, and the right answer is to not have the bug in the first place.

One more reason: a comparator that isn't consistent across all pairs breaks the Comparator contract. The List.sort documentation warns that the sort may throw IllegalArgumentException ("Comparison method violates its general contract!") when it detects a contract violation. You may get a wrong order or you may get a crash, and both depend on the input.

Interview cheat sheet

• (a, b) -> a - b overflows when the operands have opposite signs and large magnitudes.
• The fix is Integer.compare, Comparator.comparingInt, or Comparator.reverseOrder().
• (int) casts of long/double differences are a different bug: truncation, not just overflow.
• A comparator must be consistent (sign-correct) for all pairs, or sorts and heaps are allowed to misbehave.

Next in DSA: Dijkstra in Java with PriorityQueue, where this exact comparator shows up again.