1
Arrays.sort(nx2Matrix, (a, b) -> {
    if (a[0] == b[0]) return a[1] - b[1];
    else return a[0] - b[0];
});

This sorts n x 2 matrixes to be in ascending order primarily by the first index, then the second, as it should:

[[2, 0], [4, 1], [1, 2], [2, 3], [5, 4]]

turns into

[[1, 2], [2, 0], [2, 3], [4, 1], [5, 4]]

But how is it doing this exactly? More specifically, what is the Comparator doing? (This is from Approach 1 for https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/editorial/)

I tried reading the docs for Comparator, but it didn't make sense to me. I also tried using print statements to see exactly what's going on, but I still don't understand how it sorts the matrix.

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Brendan B
  • 7
  • 2
  • Does this answer your question? [Java Integer compareTo() - why use comparison vs. subtraction?](https://stackoverflow.com/questions/2728793/java-integer-compareto-why-use-comparison-vs-subtraction) – Tim Moore Apr 29 '23 at 00:37
  • 2
    In brief, this implementation is _not_ actually correct for all input values, and should be avoided. – Tim Moore Apr 29 '23 at 00:38

1 Answers1

4

That simply says:

  • If the first numbers are equal return the difference between the second.
  • Otherwise, return the diff between the first.

Which then boils down your question to:

"Why does a-b form a valid comparator"?

The answer is: It does not, actually.

A comparator must return a negative number if 'a' comes before 'b', a positive number if 'a' comes after 'b', and 0 if 'a' and 'b' are, in terms of comparison, equal.

a-b actually sort of does that. For example, 3-5 is -2. -2 is negative, which means '3' comes before '5'. Indeed it does.

It's not a good idea because there's such a thing as overflow. -2_000_000_000 surely comes before 1_000_000_000. Nevertheless, -2_000_000_000 - 1_000_000_000 is nevertheless positive (try it!) because of overflow.

The proper way to write that code as above would instead be:

Arrays.sort(nx2Matrix, (a, b) -> {
    if (a[0] == b[0]) return Integer.comparing(a[1], b[1]);
    return Integer.comparing(a[0], b[0]);
});

or perhaps even:

Arrays.sort(nx2Matrix, Comparator
  .comparingInt(a -> a[0])
  .thenComparingInt(a -> a[1]));

Which is a lot more readable, and doesn't suffer from the overflow issue.

The above means:

  • For any element, 'unpack it' by taking that element and running the function a[0] on it; this gives you an int, then just compare these ints to know which element is first.
  • If that results in 2 elements being considered equal, instead compare the ints you get when running a[1] on each element.
rzwitserloot
  • 85,357
  • 5
  • 51
  • 72