Introduction

To form the largest number from a list of non-negative integers, numeric descending sort is not enough. The correct order depends on how two numbers compare after concatenation. This problem is solved with a custom comparator that decides whether a should come before b by comparing ab versus ba.

Why Numeric Sort Fails

Consider [3, 30, 34]. Numeric descending gives 34, 30, 3 and result 34303. But order 34, 3, 30 gives 34330, which is larger.

This demonstrates that direct numeric value is not the correct ordering criterion. Concatenation dominance is.

Comparator Rule That Produces Optimal Order

For two numbers converted to strings a and b:

• Put a before b if a + b is greater than b + a.

Python comparator implementation:

1from functools import cmp_to_key
2
3def compare(a, b):
4    if a + b > b + a:
5        return -1
6    if a + b < b + a:
7        return 1
8    return 0

Sorting strings with this comparator yields a globally optimal arrangement.

Complete Python Solution

1from functools import cmp_to_key
2
3def largest_number(nums):
4    strings = [str(n) for n in nums]
5    strings.sort(key=cmp_to_key(compare))
6    result = ''.join(strings)
7    return '0' if result[0] == '0' else result
8
9print(largest_number([3, 30, 34, 5, 9]))
10print(largest_number([10, 2]))
11print(largest_number([0, 0, 0]))

The final guard for zero-only input prevents returning values like 000.

Java Implementation Pattern

The same logic maps cleanly to Java comparator.

1import java.util.Arrays;
2
3public class LargestNumber {
4    public static String build(int[] nums) {
5        String[] arr = Arrays.stream(nums)
6                .mapToObj(String::valueOf)
7                .toArray(String[]::new);
8
9        Arrays.sort(arr, (a, b) -> (b + a).compareTo(a + b));
10
11        String joined = String.join("", arr);
12        return joined.charAt(0) == '0' ? "0" : joined;
13    }
14}

This is production-friendly for backend services in Java stacks.

Complexity and Performance Notes

Runtime is dominated by sort operations. Comparator cost depends on string concatenation length. For very large input sets, string operations can become significant.

Optimization ideas:

• Precompute string conversion once.
• Avoid repeated intermediate object creation where possible.
• Benchmark with realistic size and value length distribution.

For common interview and service workloads, standard comparator-based solution is sufficient.

Validate Correctness with Tests

Add deterministic edge-case tests and small brute-force checks.

1import itertools
2
3def brute_force(nums):
4    best = ''
5    for perm in itertools.permutations(map(str, nums)):
6        candidate = ''.join(perm)
7        if candidate > best:
8            best = candidate
9    return best
10
11assert largest_number([10, 2]) == brute_force([10, 2])
12assert largest_number([0, 0]) == "0"
13assert largest_number([121, 12]) == brute_force([121, 12])

Brute-force validation on small arrays helps confirm comparator behavior during refactors.

API Contract and Input Validation

In production APIs, validate that values are non-negative integers before sorting. Reject malformed entries early with clear messages.

Strong input contracts reduce algorithm branching and simplify correctness reasoning.

If negative numbers are allowed by mistake, concatenation semantics become ambiguous relative to numeric interpretation, so it is better to enforce non-negative input explicitly.

Intuition for Comparator Correctness

The comparator works because for any pair, choosing the larger concatenation locally also improves any full permutation containing that pair order. If a+b is larger than b+a, placing a before b cannot hurt the final joined value.

This pairwise dominance gives a consistent ordering rule that sorting algorithms can apply globally. That is why a custom comparator sort is both correct and efficient for this problem class.

Common Pitfalls

• Sorting by numeric value only and getting suboptimal concatenation.
• Forgetting all-zero normalization.
• Writing comparator with inconsistent return logic.
• Recomputing string conversions inside comparator repeatedly.
• Skipping tests for prefix-like values such as 12 and 121.

Summary

• Largest-number construction is a custom comparator sorting problem.
• Compare a+b and b+a to decide order.
• Convert numbers to strings once, then sort with comparator.
• Normalize zero-only results to a single zero.
• Protect correctness with edge-case and brute-force tests.