Arrange Numbers to Form the Largest Possible Value
Solve this ProblemGiven a list of non-negative integers, arrange them so that when written one after another they form the largest possible number, and return that number as a string. If every integer is 0, return "0".
Trying every ordering is factorial. Sorting the numbers by size is wrong (9 should come before 91, and 91 before 90). The right greedy rule compares two numbers by the strings they form when joined in each order: a should come before b when "a" followed by "b" is larger than "b" followed by "a".
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums.length ≤ 6 and 0 ≤ nums[i] ≤ 999 - ◆
Arrange all the numbers in some order and write them one after another (no separators) to form a single non-negative number - ◆
Return the largest number that can be formed, as a string — the result can be far too large for an ordinary integer - ◆
If every number is 0 the result is the single character "0", never something like "000"
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Ordering and Keep the Largest String
BruteTurn each number into text and try every possible ordering (every permutation). For each ordering, join the pieces into one string. All orderings use exactly the same digits, so the resulting strings all have the same length, which means the lexicographically largest string is also the numerically largest. Keep the largest one; if it starts with '0' then every number was 0 and the answer is "0". It is guaranteed correct because it checks every ordering, but the number of orderings grows factorially.
O(n! · n)O(n)1class Solution {
2 public String largestArrangement(int[] nums) {
3 String[] parts = new String[nums.length];
4 for (int i = 0; i < nums.length; i++) parts[i] = String.valueOf(nums[i]);
5 String[] best = {""};
6 permute(parts, new boolean[parts.length], "", 0, best);
7 return best[0].charAt(0) == '0' ? "0" : best[0];
8 }
9
10 private void permute(String[] parts, boolean[] used, String current, int placed, String[] best) {
11 if (placed == parts.length) {
12 if (current.compareTo(best[0]) > 0) best[0] = current;
13 return;
14 }
15 for (int i = 0; i < parts.length; i++) {
16 if (used[i]) continue;
17 used[i] = true;
18 permute(parts, used, current + parts[i], placed + 1, best);
19 used[i] = false;
20 }
21 }
22}Optimal — Sort With the "a + b vs b + a" Comparator
OptimalSorting the numbers from biggest to smallest is wrong (9 vs 91 vs 90 shows why), and so is sorting them as plain text. The right question for any two numbers a and b is: which order makes the bigger joined string — "a" followed by "b", or "b" followed by "a"? Sort with exactly that comparator: a goes before b when a + b > b + a as strings. This comparison is consistent (it is transitive), so a normal sort works, and joining the sorted pieces gives the largest number. If the first piece is "0", all pieces are 0 and the answer is "0".
O(n log n)O(n)1class Solution {
2 public String largestArrangement(int[] nums) {
3 String[] parts = new String[nums.length];
4 for (int i = 0; i < nums.length; i++) parts[i] = String.valueOf(nums[i]);
5 Arrays.sort(parts, (a, b) -> (b + a).compareTo(a + b));
6 if (parts[0].equals("0")) return "0";
7 StringBuilder result = new StringBuilder();
8 for (String part : parts) result.append(part);
9 return result.toString();
10 }
11}