Java Sorting with Lambda Expression

Question

I am new to Java and this might be a dumb question to ask. I was looking at '905. Sort Array By Parity' on Leetcode. One of the solutions is

class Solution {
    public int[] sortArrayByParity(int[] A) {
        Integer[] B = new Integer[A.length];
        for (int t = 0; t < A.length; ++t)
            B[t] = A[t];

        Arrays.sort(B, (a, b) -> Integer.compare(a%2, b%2));

        for (int t = 0; t < A.length; ++t)
            A[t] = B[t];
        return A;

        /* Alternative:
        return Arrays.stream(A)
                     .boxed()
                     .sorted((a, b) -> Integer.compare(a%2, b%2))
                     .mapToInt(i -> i)
                     .toArray();
        */
    }
}

I am having trouble understanding the line with lambda expression in it.

Arrays.sort(B, (a, b) -> Integer.compare(a%2, b%2));

How does it sort the array exactly? Where do a and b come from?

Answer 1

You are calling Arrays.sort(T[] a, Comparator<? super T> c), where T is resolved by the compiler to Integer, which means that the lambda expression must implement method compare(Integer o1, Integer o2).

a and b are the two parameters to the method. That's how lambda expressions work, you must name (and optionally type) the formal parameters of the abstract method of the functional interface.

Answer 2

Sort

The Java Array.sort method takes an array B as input and sorts it according to the compare(a, b) method of the array's elements. So if the array stored Integer objects, it would sort them according to Integer.compare(a, b) by default. This just sorts the integers in increasing order.

Comparator

Java has a Comparator interface that defines a method called compare(a, b). This method returns zero if (a==b), a negative value if (a < b), and a positive value if (a > b). The Comparator interface is often used in sorting methods or ordered data structures, like TreeMap.

Lambda

Now since this question asks for a custom sort order, you need to provide a custom compare(a, b) method. Fortunately, there is an overloaded version of Array.sort that allows you to do exactly this by providing a lambda method. A lambda is simply an inline function. In this case, it provides the desired comparison logic for the sort. In your example, (a, b) -> are the inputs to the lambda function, which are provided by the sort method. This is standard lambda syntax. The sort will run a mergesort algorithm on the array B, using your lambda compare method to determine how each pair of numbers are ordered.

Sort by Parity

Integer.compare(a%2, b%2) sorts integers a and b according to their least significant bits. % is the modulus operator (remainder after division). If a is even, a%2 returns 0. If a is odd, a%2 returns 1. https://leetcode.com/articles/sort-array-by-parity/ does a decent job of breaking down the logic of why this operation sorts the numbers by parity, but it's not really obvious. The more problems you solve, the more shortcuts like this you will learn.

References

Here are some SO threads that provide more information:

• java: Arrays.sort() with lambda expression
• Java: sorting an array with lambda expression?

Answer 3

• For interviews, as much as you can, you should avoid using Java's specialized methods.

• You can use this Solution, which is much simple to understand and is interview friendly.

Accepted Solution:

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int left = 0;
        int right = A.length - 1;

        while (left < right) {
            if (A[left] % 2 == 0)
                left++;

            else {
                if (A[right] % 2 != 0)
                    right--;

                if (A[right] % 2 == 0) {
                    swap(A, left, right);
                    left++;
                    right--;
                }
            }
        }

        return A;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

---

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int left = 0;
        int right = A.length - 1;

        while (left < right) {
            if ((A[left] & 1) == 0)
                left++;

            else {
                if ((A[right] & 1) != 0)
                    right--;

                if ((A[right] & 1) == 0) {
                    swap(A, left, right);
                    left++;
                    right--;
                }
            }
        }

        return A;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

---

References

• For additional details, you can see the Discussion Board. In the Discussion Board, there are plenty of accepted solutions, explanations, efficient algorithms with a variety of languages, and time/space complexity analysis.