Largest Number

Problem

Given a list of non negative integers, arrange them such that they form the largest number. For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330. Note: The result may be very large, so you need to return a string instead of an integer.

Solution

String[] Comparator Solution: O(nlgn) time, O(n) space

public class Solution {
    public String largestNumber(int[] nums) {
        String[] strs = Arrays.stream(nums).mapToObj(String::valueOf).toArray(String[]::new);
        Arrays.sort(strs, (s1, s2) -> (s2 + s1).compareTo(s1 + s2));
        if (strs[0].charAt(0) == '0') return "0";
        StringBuilder sb = new StringBuilder();
        for (String s : strs) sb.append(s);
        return sb.toString();
    }
}

Analysis

The key idea in this solution is to use compareTo() method to sort
We first convert the int[] to String[]
Then we sort them by (s1, s2) -> (s2 + s1).compareTo(s1 + s2)
After that we just need to collect the strings in order and return completed string at the end
Notice how we convert int[] to String[] by:
Arrays.stream(nums).mapToObj(String::valueOf).toArray(String[]::new);