#179
Largest Number
Medium Comparator on concatenation
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Arrange non-negative integers so that, written side by side, they form the largest possible number. Return it as a string.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: arrange numbers to form the biggest possible number.
Why this works: compare two numbers by gluing them both ways: put a first if a + b > b + a as strings.
Example: [3, 30, 34, 5, 9]
"9" first, then "5", then "34" ("343" > "334")"3" before "30" ("330" > "303")"9534330"
✦Hints open one at a time
Normal numeric sorting fails: 9 should come before 34, and 3 before 30.
Put a before b if a + b (as strings) is bigger than b + a.
If the biggest piece is "0", the answer is "0".
↗Approach
Convert to strings, sort with comparator (x, y) -> (y + x).compareTo(x + y), join, and handle the all-zeros case.
</>Solution (Java)
import java.util.*;
class Solution {
public String largestNumber(int[] nums) {
String[] s = new String[nums.length];
for (int i = 0; i < nums.length; i++) s[i] = String.valueOf(nums[i]);
Arrays.sort(s, (x, y) -> (y + x).compareTo(x + y)); // larger concatenation first
if (s[0].equals("0")) return "0";
StringBuilder sb = new StringBuilder();
for (String x : s) sb.append(x);
return sb.toString();
}
}!Common mistake
Returning "000" for all-zero input instead of "0".
Complexity
- Time: O(n log n · k), k = digits per number.
- Space: O(n · k).
Topic: Sorting
🎬 Episodes 24–28: video coming soon