#179 Largest Number
the problem
In plain words
Arrange non-negative integers so that, written one after another, they form the largest possible number. Return it as a string.
in nums = [10,2]
out "210"
in nums = [3,30,34,5,9]
out "9534330"
- 1 ≤ n ≤ 100
- 0 ≤ nums[i] ≤ 10⁹
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSort with a custom comparator
Decide the order of any two pieces a, b by asking which concatenation is bigger: a+b or b+a. That rule is transitive, so a normal sort with it gives the best global order.
solutions
From brute force to optimal
Generate all n! orders, keep the biggest string.
- Backtrack over all permutations.
- Compare equal-length strings lexicographically.
- Return "0" if the best starts with 0.
n! orders, each built and compared in O(n·L), L = digits per number.
Recursion plus the current string.
class Solution { private String best; public String largestNumber(int[] nums) { best = null; permute(nums, 0); return best.charAt(0) == '0' ? "0" : best; } private void permute(int[] a, int k) { if (k == a.length) { StringBuilder sb = new StringBuilder(); for (int x : a) sb.append(x); String s = sb.toString(); // all candidates have equal length, so string order = numeric order if (best == null || s.compareTo(best) > 0) best = s; return; } for (int i = k; i < a.length; i++) { swap(a, k, i); permute(a, k + 1); swap(a, k, i); } } private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }}Sort strings so that a comes before b when a+b > b+a.
- Convert to strings.
- Sort with
(a, b) -> (b + a).compareTo(a + b). - If the first is "0", return "0".
- Join.
n log n comparisons, each builds two strings of length ≤ 2L (L ≤ 10).
The string array and the result.
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]); // a goes first if "a+b" beats "b+a" — e.g. "9"+"34" > "34"+"9" Arrays.sort(s, (a, b) -> (b + a).compareTo(a + b)); if (s[0].equals("0")) return "0"; // the biggest piece is 0 → everything is 0 StringBuilder sb = new StringBuilder(); for (String x : s) sb.append(x); return sb.toString(); }}Dry run: which glue is bigger?
in the room
How to say it in the interview
talk track
- Show why plain descending order fails: [3, 30] → "330" beats "303".
- State the comparator and the all-zeros edge case before coding.
traps
- Returning "00" for [0, 0].
- Comparing numerically instead of by concatenation.
what they ask next
Follow-ups
Why is the comparator transitive?
a+b > b+a ⇔ a·10^|b| + b > b·10^|a| + a ⇔ a/(10^|a|−1) > b/(10^|b|−1): it's comparing one real number per string, so it's a valid total order.
before you submit
Edge cases to test
- [0, 0] → "0", not "00".
- One piece is a prefix of another: [3, 30] → "330", [121, 12] → "12121".
- Up to 100 numbers of 10 digits: the answer can be 1,000 digits long — keep it a string, never parse it.
practise next
Similar problems
- #1636Sort Array by Increasing FrequencyEasyin Sorting
- #347Top K Frequent ElementsMediumin Heaps