LeetCode 179: Largest Number

Explanation

To solve this problem, we need to arrange the numbers in such a way that the resulting number formed by concatenating them is the largest possible. The key idea is to compare two numbers by concatenating them in two different orders and selecting the order that gives the larger result. We can achieve this by custom sorting the numbers.

1. Define a custom comparator that compares two numbers by concatenating them in different orders and selecting the larger result.
2. Sort the numbers using the custom comparator.
3. Concatenate the sorted numbers to form the largest number.

Time complexity: O(nlogn) where n is the number of integers in the input list. Space complexity: O(n)

class Solution {
    public String largestNumber(int[] nums) {
        String[] strNums = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strNums[i] = String.valueOf(nums[i]);
        }
        
        Arrays.sort(strNums, (a, b) -> (b + a).compareTo(a + b)); // Custom comparator
        
        if (strNums[0].equals("0")) {
            return "0"; // Edge case when the largest number is 0
        }
        
        StringBuilder result = new StringBuilder();
        for (String str : strNums) {
            result.append(str);
        }
        
        return result.toString();
    }
}