179. Largest Number

Description

Given a list of non-negative integers nums, arrange them such that they form the largest number.

Note: The result may be very large, so you need to return a string instead of an integer.

Constraints

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 109

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: nums = [3,30,34,5,9]

Output: "9534330"

Example 2

Input: nums = [1]

Output: "1"

Example 3

Input: nums = [10]

Output: "10"

Example 4

Input: nums = [0, 0, 0]

Output: "0"

Solutions

Solution 1

/**
 * Time complexity : O(nlogn). Although we are doing extra work in our 
 *    comparator, it is only by a constant factor. Therefore, the overall 
 *    runtime is dominated by the complexity of sort, which is O(nlogn) 
 *    in Python and Java.
 * Space complexity : O(n). Here, we allocate O(n) additional space to store 
 *    the copy of nums. Although we could do that work in place (if we decide 
 *    that it is okay to modify nums), we must allocate O(n) space for the 
 *    final return string. Therefore, the overall memory footprint is linear 
 *    in the length of nums.
 */

class Solution {
    public String largestNumber(int[] nums) {
        if(nums == null || nums.length == 0) return "";
        
        String[] values = new String[nums.length];
        for(int i = 0; i < nums.length; i++) {
            values[i] = String.valueOf(nums[i]);
        }
        
        Arrays.sort(values, new Comparator<String>() {
            public int compare(String a, String b) {
                return (b+a).compareTo(a+b);
            }
        });
        
        StringBuilder result = new StringBuilder();
        for(String value: values) {
            result.append(value);
        }
        
        while(result.charAt(0) == '0' && result.length() > 1) {
            result.deleteCharAt(0);
        }
        
        return result.toString();
    }
}

Follow up