Largest Number

Medium Arrays & Hashing Greedy Original on LeetCode

Largest Number is a medium arrays & hashing problem solved with the greedy pattern. The best approach, optimal (sort with a concatenation comparator), runs in O(n log n · L) time and O(n · L) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (repeated selection) up.

Problem

You are given a list of non-negative integers nums. Arrange them in some order and write them next to each other to form one big number. Return the largest number you can build this way.

The result can be far too large for any integer type, so return it as a string, with no leading zeros (unless the number itself is zero).

Examples

Example 1

Input
nums = [5, 52, 7]
Output
"7552"
Why
7 goes first. Between 5 and 52, "552" beats "525", so 5 comes before 52.

Example 2

Input
nums = [12, 121, 0]
Output
"121210"
Why
"12121" is larger than "12112", so 12 goes before 121; 0 goes last.

Example 3

Input
nums = [0, 0, 0]
Output
"0"
Why
The joined string would be "000", which is written as just "0".

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 10^9

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 17 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (repeated selection)O(n² · L)O(n · L)
Optimal (sort with a concatenation comparator)O(n log n · L)O(n · L)

1Brute force (repeated selection)

TimeO(n² · L)n rounds, each scanning up to n strings with an O(L) concatenation compare (L ≤ 10 digits).
SpaceO(n · L)The list of digit strings and the result.

Build the answer one piece at a time. Among the numbers not used yet, the one that should come next is the one that beats every other under the rule x + y >= y + x. Find it by a linear scan, append it, remove it, and repeat.

  1. Convert every number to a string.
  2. While strings remain: scan for the string best such that best + s >= s + best for every remaining s.
  3. Append best to the result and remove it.
  4. If the result starts with '0', return "0"; otherwise return it.
class Solution {
    public String largestNumber(int[] nums) {
        List<String> left = new ArrayList<>();
        for (int x : nums) left.add(String.valueOf(x));
        StringBuilder sb = new StringBuilder();
        while (!left.isEmpty()) {
            int bestIdx = 0;
            for (int i = 1; i < left.size(); i++) {
                String a = left.get(i), b = left.get(bestIdx);
                if ((a + b).compareTo(b + a) > 0) bestIdx = i;
            }
            sb.append(left.remove(bestIdx));
        }
        return sb.charAt(0) == '0' ? "0" : sb.toString();
    }
}

2Optimal (sort with a concatenation comparator)

TimeO(n log n · L)O(n log n) comparisons, each building and comparing two strings of up to 2L characters.
SpaceO(n · L)The array of digit strings and the joined result.

The rule "a goes before b when a + b > b + a" is transitive, so it defines a proper ordering. Sort the digit strings with it and join them. If the first string is "0", every string is "0" and the answer is "0".

  1. Convert every number to a string.
  2. Sort with comparator (a, b) -> (b + a).compareTo(a + b).
  3. If the first string is "0", return "0".
  4. Otherwise join all strings and return the result.
class Solution {
    public 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 s : strs) sb.append(s);
        return sb.toString();
    }
}

Edge cases to test

  • All zeros: return "0", not "000"
  • One number is a prefix of another, like 3 and 34 or 12 and 121
  • A single element
  • Numbers of very different lengths, like 9 and 1000000000

Hints

Hint 1

Sorting by numeric value fails ([3, 30] should give "330", not "303"), and plain string order also fails for prefixes.

Hint 2

To decide which of a and b goes first, compare the two possible joins: a + b versus b + a.

Hint 3

That rule is a valid ordering, so you can sort with it. Watch out for a result made only of zeros.

FAQ

What is the best time complexity for Largest Number?

Optimal (sort with a concatenation comparator) runs in O(n log n · L) time and O(n · L) extra space. O(n log n) comparisons, each building and comparing two strings of up to 2L characters.

Which pattern does Largest Number use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.

Is there a brute force solution for Largest Number?

Yes. Brute force (repeated selection) takes O(n² · L) time and O(n · L) space. Build the answer one piece at a time.

Which edge cases should I test for Largest Number?

All zeros: return "0", not "000"; One number is a prefix of another, like 3 and 34 or 12 and 121; A single element; Numbers of very different lengths, like 9 and 1000000000.