Problem 14.4 · Sorting and Divide & ConquerMedium

Largest Number

What it teaches: A custom comparator: put a before b when a + b (as strings) is bigger than b + a.

Practise it on judges as “Largest Number”.

The problem

Arrange non-negative integers so 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"

Constraints

1 ≤ n ≤ 100
0 ≤ nums[i] ≤ 10⁹

Pattern clues in the wording

→ Choose an order that maximises a combined result
→ Pairwise comparison decides the order

These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public String largestNumber(int[] nums) {
        return "";
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [10,2]	"210"
2	nums = [3,30,34,5,9]	"9534330"
3	nums = [0,0]	"0"

From slow to fast

Approaches

1. Optimal: sort by concatenation · O(n log n · L) for numbers of up to L digits

Optimal: sort by concatenation

Time O(n log n · L) for numbers of up to L digits Space O(n · L)

Convert to strings and sort with (a, b) -> (b + a).compareTo(a + b). Join. If the first character is '0', return "0".

Approach 1

import java.util.Arrays;

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, (a, b) -> (b + a).compareTo(a + b));
        if (s[0].equals("0")) return "0";
        return String.join("", s);
    }
}

Verdict: The comparator is transitive, so sorting by it is valid.

Before you submit

Edge cases and common mistakes

Test these inputs

All zeros → "0"
Numbers sharing a prefix (3 and 30)

Mistakes people make

Sorting numerically or lexicographically.
Returning "000" for all zeros.

Interview

Follow-up questions

Why is it safe to sort with this comparator?

Command Palette

The problem

Approaches

Optimal: sort by concatenation

Edge cases and common mistakes

Follow-up questions