Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
Since the result may be very large, so you need to return a string instead of an integer.
Input: nums = [10,2]
Output: "210"
Input: nums = [3,30,34,5,9]
Output: "9534330"
Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 109
Contents
- Solution 1 - Sort input numbers using a custom comparator
In this approach, we are going to sort the numbers using a custom comparator, that is convert the input numbers into strings and compare them such that
it sorts based on the digits and not as a whole number, for example if these two numbers were given as input 34 and 9, custom comparator
should return 9 is it is the greatest comparing the digit.
So, in the custom comparator, say num1 and num2 are inputs to the comparator, then
we will create two strings by concatenating these two numbers as num1+""+num2 and num2+""+num1 and compare between these two.
For example, in the input numbers given to comparator are num1 = 34 and num2 = 9, then two strings that we will create after concatenating are
349 and 934, since 934 is greater, it returns 9 as greater element.
import java.util.stream.IntStream;
public class LargestNumber {
static String largestNumber(int[] nums) {
StringBuilder sb = new StringBuilder();
IntStream.of(nums).boxed().sorted((num1, num2)->{
String compare1 = num1+""+num2;
String compare2 = num2+""+num1;
return compare2.compareTo(compare1);
}).forEach(sb::append);
if(sb.charAt(0) == '0') {
return "0";
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(largestNumber(new int[]{3,30,34,5,9}));
System.out.println(largestNumber(new int[]{0, 0}));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n log n) time where n is the length of nums array.
This is because, we are sorting input array.
Space complexity: O(1), assuming sort() function is using sorting algorithm like QuickSort.
Above implementations source code can be found at
GitHub link for Java code