Overflow-Safe Java Comparators for Arrays, Collections, and Priority Queues

Welcome back. In the previous lesson, you learned not to judge a pointer algorithm by indentation alone: when pointers only move forward or toward each other, you bound the total movement over the full execution.

This lesson shifts to a Java implementation detail that can quietly invalidate an otherwise correct algorithm: the comparator. Sorting intervals, ordering custom states, and building heaps are recurring interview tasks. You will learn to define an ordering that remains correct even at int and long extremes, then apply it to arrays, collections, and PriorityQueue.

---

A comparator is an ordering rule, not arithmetic

A Java Comparator<T> answers one question:

In the ordering I want, should a appear before, after, or at the same rank as b?

Its compare(a, b) method returns an int, but only the sign matters:

Result	Meaning
Negative	a comes before b
Zero	a and b are tied by this ordering
Positive	a comes after b

The result does not need to be exactly -1, 0, or 1. Java sorting and heap implementations only use whether it is negative, zero, or positive.

A comparator must be internally coherent. The practical version of the comparator contract is:

• If a comes before b, then b must come after a.
• If a comes before b and b comes before c, then a must come before c.
• Repeating the comparison should not change its result while the objects stay unchanged.

Violating these rules can lead to incorrectly ordered output, or an exception such as “comparison method violates its general contract.”

Watch the first portion of “Write Efficient Bug-free and Simple Comparators in Java” from the Java channel. It establishes the sign-based meaning of compare, then demonstrates why seemingly natural subtraction-based comparators break.

The most important interview habit is this:

Never compare integral values by subtracting them.

The unsafe version is short:

Comparator<Integer> unsafeAscending = (a, b) -> a - b;

It works for many ordinary inputs, which makes it dangerous. But Java int arithmetic overflows silently.

Suppose:

int a = Integer.MIN_VALUE;
int b = 1;

Mathematically, a is smaller than b, so the comparator should return a negative result. But a - b is smaller than the minimum representable int; it wraps around to a positive value. The comparator falsely claims that a comes after b.

Use the library method instead:

Comparator<Integer> safeAscending = Integer::compare;

Or, when writing the body explicitly:

Comparator<Integer> safeAscending = (a, b) -> Integer.compare(a, b);

For long values, use Long.compare(a, b). The same rule applies to numeric fields inside your own classes.

---

Prefer comparison helpers and comparator factories

When your objects have an int key, Comparator.comparingInt is usually the clearest choice. It is overflow-safe and avoids boxing each primitive value into an Integer.

Consider a search state with a cost and a node ID:

static final class State {
    final int cost;
    final int node;

    State(int cost, int node) {
        this.cost = cost;
        this.node = node;
    }
}

To sort by lower cost first, then use node ID as a deterministic tie-breaker:

Comparator<State> byCostThenNode =
        Comparator.comparingInt((State s) -> s.cost)
                  .thenComparingInt(s -> s.node);

This expresses the policy directly:

1. Compare cost.
2. If costs tie, compare node.
3. If both fields tie, treat the two states as tied.

Contrast that with a fragile handwritten version:

Comparator<State> unsafe =
        (a, b) -> a.cost != b.cost
                ? a.cost - b.cost
                : a.node - b.node;

Both subtraction expressions can overflow. Replacing only the first one is not enough; every numeric comparison must be safe.

A fully safe handwritten equivalent is:

Comparator<State> safe = (a, b) -> {
    int byCost = Integer.compare(a.cost, b.cost);
    if (byCost != 0) {
        return byCost;
    }
    return Integer.compare(a.node, b.node);
};

This is correct, but the chained factory form is usually easier to read under interview pressure.

Descending order without risky subtraction

For a max-first ordering, avoid this:

Comparator<Integer> unsafeDescending = (a, b) -> b - a;

Reversing the subtraction does not solve overflow; it merely moves the bug.

For boxed numbers, use:

Comparator<Integer> maxFirst = Comparator.reverseOrder();

For a custom object, reverse a comparator:

Comparator<State> higherCostFirst =
        Comparator.comparingInt((State s) -> s.cost)
                  .reversed();

Be precise about where .reversed() appears. This comparator:

Comparator<State> higherCostThenLowerNode =
        Comparator.comparingInt((State s) -> s.cost)
                  .reversed()
                  .thenComparingInt(s -> s.node);

orders by:

• cost descending;
• node ascending when costs tie.

But this version reverses the entire chain, including the tie-breaker:

Comparator<State> reversedEverything =
        Comparator.comparingInt((State s) -> s.cost)
                  .thenComparingInt(s -> s.node)
                  .reversed();

Both may be valid, but they describe different policies. State the intended tie-breaking rule before coding.

---

Sorting arrays and collections safely

Interview problems often represent intervals, points, or edges as int[][]. Although each inner element is a primitive int[], the outer int[][] is an array of objects, so Java lets you pass a comparator to Arrays.sort.

For intervals represented as {start, end}, sort by start time and then by end time:

int[][] intervals = {
    {5, 8},
    {1, 4},
    {5, 6},
    {Integer.MIN_VALUE, 0}
};

Arrays.sort(
    intervals,
    Comparator.<int[]>comparingInt(interval -> interval[0])
              .thenComparingInt(interval -> interval[1])
);

The explicit <int[]> can help Java infer the element type cleanly. The comparator is safe because comparingInt internally performs a proper integer comparison rather than subtracting starts or ends.

This is especially relevant for interval questions. The tempting alternative is:

Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

That code can misorder intervals whose starts are near Integer.MIN_VALUE and Integer.MAX_VALUE.

A useful distinction:

Data structure	How to sort
int[]	Arrays.sort(nums); primitive values use natural ascending order
Integer[]	Arrays.sort(nums, comparator)
int[][]	Arrays.sort(intervals, comparator)
List<T>	list.sort(comparator)
Legacy collection style	Collections.sort(list, comparator)

A primitive int[] cannot accept a custom Comparator, because primitive values are not objects. In most interview problems, this is fine: use Arrays.sort(nums) for ascending order, then apply your algorithm. If you need a custom ordering of numeric values, you normally use Integer[] or store those values inside custom objects.

For a collection of custom jobs:

static final class Job {
    final int deadline;
    final int profit;
    final String id;

    Job(int deadline, int profit, String id) {
        this.deadline = deadline;
        this.profit = profit;
        this.id = id;
    }
}

Sort earliest deadline first, then higher profit first, then ID alphabetically:

Comparator<Job> byDeadlineThenProfitThenId =
        Comparator.comparingInt((Job job) -> job.deadline)
                  .thenComparing(
                      Comparator.comparingInt((Job job) -> job.profit)
                                .reversed()
                  )
                  .thenComparing(job -> job.id);

jobs.sort(byDeadlineThenProfitThenId);

The key is that the descending comparison is built by reversing a safe comparator—not by negating or subtracting profits.

Read the selected sections of “PriorityQueue in Java: Heap Internals & Comparators” from Java-HandsOn. The resource reinforces safe numeric comparison, then shows how a comparator gives custom objects a usable ordering and how to chain tie-breakers.

---

Priority queues: the comparator determines what poll() returns

Java’s PriorityQueue is a min-heap according to its comparator.

With no comparator, it uses natural ordering:

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

Calling poll() returns the smallest integer currently present.

To retrieve the largest integer first:

PriorityQueue<Integer> maxHeap =
        new PriorityQueue<>(Comparator.reverseOrder());

The heap implementation has not somehow become a fundamentally different data structure. You changed the definition of what ranks first.

For custom records, pass your comparator when constructing the queue:

Comparator<State> byCostThenNode =
        Comparator.comparingInt((State s) -> s.cost)
                  .thenComparingInt(s -> s.node);

PriorityQueue<State> minCostHeap =
        new PriorityQueue<>(byCostThenNode);

Now each poll() returns a state with the smallest cost; states with equal costs are ordered by node.

Priority queues also frequently store primitive-array records, especially in graph and interval problems. For example, if each entry stores {cost, node}:

PriorityQueue<int[]> minHeap = new PriorityQueue<>(
        Comparator.<int[]>comparingInt(entry -> entry[0])
                  .thenComparingInt(entry -> entry[1])
);

minHeap.offer(new int[] {10, 4});
minHeap.offer(new int[] {3, 9});
minHeap.offer(new int[] {3, 2});

The first poll() returns {3, 2}. The queue compares entry[0] safely, then resolves a cost tie with entry[1].

Two priority-queue details matter in interviews:

1. Only the head is guaranteed to be next by priority.
   Repeated calls to poll() produce priority order. Iterating directly through a PriorityQueue does not produce sorted order.

2. Do not mutate comparison fields after insertion.
   If a State already inside the heap has its cost changed, Java does not automatically reposition it. Prefer immutable fields, or remove and reinsert the object when its priority changes.

A comparator returning zero does not mean Java considers the two objects identical everywhere. In a priority queue, ties are allowed. But in a TreeSet or TreeMap, two values that compare as zero occupy the same sorted-set/map position. That is why a tie-breaker is often important when you need every distinct object retained.

---

A fast comparator audit before submission

Before using a comparator in Arrays.sort, List.sort, or PriorityQueue, run this short mental check:

• Numeric key? Use Integer.compare, Long.compare, comparingInt, or comparingLong; never subtraction.
• Descending key? Use .reversed() on the relevant comparator, not negation or reversed subtraction.
• Multiple keys? Use thenComparing, thenComparingInt, or another primitive helper.
• Extreme values tested? Include Integer.MIN_VALUE, Integer.MAX_VALUE, negative values, zero, and duplicate keys.
• Boxed values? Do not use == to test whether two Integer objects have the same value. Use Integer.compare, .equals, or primitive unboxing as appropriate.
• Priority queue? Confirm that your comparator makes the item you want to remove first rank as smallest.
• Mutable priority field? Avoid changing it while the object remains in the heap.

For most interview code, this compact style is both safe and communicative:

Comparator<int[]> byFirstThenSecond =
        Comparator.<int[]>comparingInt(pair -> pair[0])
                  .thenComparingInt(pair -> pair[1]);

It tells the interviewer the ordering policy at a glance, avoids overflow, and handles ties predictably.

---

Key takeaways

• A comparator returns a negative, zero, or positive result to describe ordering; only the sign matters.
• Never use subtraction such as a - b or b - a to compare numeric values, because overflow can reverse the ordering.
• Use Integer.compare, Long.compare, Comparator.comparingInt, and Comparator.comparingLong for safe numeric ordering.
• Sort int[][] and collections of objects with comparator chains and explicit tie-breakers.
• A PriorityQueue returns the element that ranks first under its comparator; use Comparator.reverseOrder() for a boxed-number max-heap.
• Do not mutate fields that determine heap priority after an object is inserted.

Next, you will focus on stating an algorithm’s invariant: the precise fact that remains true throughout an iterative or recursive process and explains why the final answer is correct.