Largest Number — Solution in Python, Java & C++
Largest Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and strings.
Largest Number is a medium coding problem on arrays, strings and sorting, asked in Amazon, Microsoft, Adobe and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Sorting, Greedy
- Asked at: Amazon, Microsoft, Adobe, Meta, Myntra, Hotstar
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a list of non-negative integers nums, arrange them so that they form the largest possible number, and return it as a string.
Example 1
Input: nums = [10,2]
Output: 210
Example 2
Input: nums = [3,30,34,5,9]
Output: 9534330
Example 3
Input: nums = [0,0]
Output: 0
Explanation: All zeros collapse to a single 0, not 00.
Constraints
1 <= nums.length <= 400 <= nums[i] <= 1000000000
Hints for Largest Number
Hint 1
Plain numeric or lexicographic sorting both fail: 3 must come before 30, but 30 before 34.
Hint 2
Compare two numbers
aandbby which concatenation is larger —a+borb+a— and sort by that.Hint 3
Watch the all-zeros case: joining gives
"000…", which must be reported as"0".
How to solve Largest Number
Sort the numbers as strings with the comparator "a before b iff a + b > b + a", then concatenate.
Approach
- Convert to strings.
- Sort with the concatenation comparator.
- If the first is
"0", return"0"; else join.
Why it works
The comparator is a valid total order (it is transitive, which follows from comparing a·10^|b| + b against b·10^|a| + a), and any adjacent pair out of that order could be swapped to increase the result — so the sorted order is maximal.
Complexity
- Time —
O(n log n · L) - Space —
O(n · L)
Pitfalls
- Neither numeric nor lexicographic order works (
3vs30vs34). [0, 0]must return"0", not"00".
Reference solution
Python
import functools
def largestNumber(nums) -> str:
strs = [str(x) for x in nums]
strs.sort(key=functools.cmp_to_key(lambda a, b: (b + a > a + b) - (b + a < a + b)))
if strs[0] == "0":
return "0"
return "".join(strs)Java
public static String largestNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]);
Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
if (strs[0].equals("0")) return "0";
StringBuilder sb = new StringBuilder();
for (String x : strs) sb.append(x);
return sb.toString();
}C++
string largestNumber(vector<int>& nums) {
vector<string> strs;
for (int x : nums) strs.push_back(to_string(x));
sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
return a + b > b + a;
});
if (strs[0] == "0") return "0";
string out;
for (const string& x : strs) out += x;
return out;
}JavaScript
var largestNumber = function(nums) {
const strs = nums.map(function(x) { return String(x); });
strs.sort(function(a, b) {
const ab = a + b;
const ba = b + a;
if (ba < ab) return -1;
if (ba > ab) return 1;
return 0;
});
if (strs[0] === "0") return "0";
return strs.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.