Largest Number | Leetcode

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

---

Solution: Convert the numbers into a string array. This is because we need to operate them in strings for sorting, so we do not need to reconvert them to strings everytime we need it. Sort the string array using a special order. The comparison order is the key to this question. First, the numbers should be sorted in descending order (highest to lowest), so you have to use the opposite order of a JDK String.compareTo() method. Second, for any two number strings, you compare them by checking if putting one before the other is greater. For example, for "128" and "12", check if "12812" is greater than "12128". This will always work because since these two numbers have the same prefix, they will always be contiguous to other numbers with the same prefix in sorted order. Hence comparing them by putting them adjacent to each other will work.

public class Solution {
    public String largestNumber(int[] nums) {
        // Convert to array of strings.
        String[] s = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            s[i] = Integer.toString(nums[i]);
        }
        
        // Sort by desired order.
        Arrays.sort(s, (x, y) -> (y + x).compareTo(x + y));
        
        // Form one large string.
        StringBuilder sb = new StringBuilder();
        for (String t: s) {
            // Skip leading zeros.
            if (sb.length() == 0 && t.equals("0")) {
                continue;
            }
            sb.append(t);
        }
        
        // If empty, return 0.
        return (sb.length() != 0) ? sb.toString() : "0";
    }
}