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.

As the last question of a successful interview, your boss gives you a few pieces of paper with numbers on it and asks you to compose a largest number from these numbers. The resulting number is going to be your salary, so you are very much interested in maximizing this number. How can you do this?

Examples

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

If the nums were single-digit number, then it would have been easy to just follow the algorithm:

LargestNumber(Digits):
	answer ← empty string
	while Digits is not empty:
		maxDigit ← -∞
		for digit in Digits:
			if digit >= maxDigit:
				maxDigit ← digit
		append maxDigit to answer
		remove maxDigit from Digits
	return answer

But nums will have multi-digit number.

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

C++

class Solution {
public:
	std::string largestNumber(std::vector<int>& nums) {
		std::vector<std::string> arr;
		arr.reserve(nums.size());
		for (int x : nums) arr.push_back(std::to_string(x));
		std::sort(arr.begin(), arr.end(), [](const std::string& a, const std::string& b) {
			// Put a before b if a+b > b+a
			return a + b > b + a;
		});
		if (arr.size() && arr[0] == "0") return "0"; // all zeros
		std::string result;
		result.reserve(arr.size() * 10); // rough pre-allocation
		for (auto& s : arr) result += s;
		return result;
	}
};

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();
}

Python

class Solution:
	def largestNumber(self, nums: List[int]) -> str:
		arr = [str(x) for x in nums]
		# Python's sort can't take a comparator directly (since 3.x), so we use functools.cmp_to_key
		from functools import cmp_to_key

		def cmp(a: str, b: str) -> int:
			if a + b > b + a:
				return -1  # a should come first
			if a + b < b + a:
				return 1
			return 0

		arr.sort(key=cmp_to_key(cmp))
		if arr[0] == '0':  # all zeros
			return '0'
		return ''.join(arr)

Complexity

⏰ Time complexity: O(n log n * k) – sorting n strings with custom comparator; each comparison concatenates two strings of average length k.
🧺 Space complexity: O(n * k) – storing string representations plus output (auxiliary beyond input integers is linear).