Largest Number From Given Numbers

Problem

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.

Example

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

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

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

Solution

Method 1 - Using Sorting

This problem will be solved by greedy. We should put higher number before lower one. For eg. 9 before 5 OR 9 before 34, as that will give us 95 and 934 respectively. Also, when we have same digit numbers like 35 and 34, then 35 should come before 34.

This problem can be solve by simply sorting strings, not sorting integer. Sorting integers will make 34 before 9, which will break our case.

Define a comparator to compare strings by concat() right-to-left or left-to-right.

String s1 = "9";
String s2 = "31";

String case1 =  s1 + s2; // 931
String case2 = s2 + s1; // 319

Apparently, case1 is greater than case2 in terms of value.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java

public String largestNumber(int[] nums) {
	String[] arr = new String[nums.length];
	for (int i = 0; i<nums.length; i++) {
		arr[i] = String.valueOf(nums[i]);
	}

	Arrays.sort(arr, new Comparator<String> () {
		public int compare(String a, String b) {
			return (b + a).compareTo(a + b);
		}
	});

	StringBuilder sb = new StringBuilder();
	for (String s: arr) {
		sb.append(s);
	}

	while (sb.charAt(0) == '0' && sb.length() > 1)
		sb.deleteCharAt(0);

	return sb.toString();
}

Java 8 style code:

public String largestNumber(int[] num) {
	String[] array = Arrays.stream(num).mapToObj(String::valueOf).toArray(String[]::new);
	Arrays.sort(array, (String s1, String s2) -> (s2 + s1).compareTo(s1 + s2));
	return Arrays.stream(array).reduce((x, y) -> x.equals("0") ? y : x + y).get();
}