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

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

```java
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.

![With a = Integer.MIN_VALUE and b = 1, a - b overflows to 2,147,483,647 so the comparator says a > b, while Integer.compare(a, b) correctly returns -1.](https://cdn.hashnode.com/uploads/covers/658c3a46e339366b1a80b9f3/8f1a7998-baa6-4872-b992-068b957d2c00.png align="center")

## See it fail (complete program)

```java
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;
    }
}
```

```bash
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):

```text
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.