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
ProgramCreek
YouTube
Examples
Input: nums = [3,30,34,5,9]
Output: "9534330"
Input: nums = [1]
Output: "1"
Input: nums = [10]
Output: "10"
Input: nums = [0, 0, 0]
Output: "0"
Solutions
/**
* 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();
}
}