Largest Number LeetCode 179 Guide

LeetCode 179 Largest Number asks you to arrange a given array of non-negative integers such that they form the largest possible number, returned as a string. The numbers can be rearranged in any order — your goal is to find the permutation that produces the numerically largest concatenation.

The naive approach of sorting by numeric value fails immediately. The integer 9 is smaller than 10, but placing 9 before 10 gives "910" which is larger than "109". Correct ordering requires comparing numbers in the context of their string concatenation with neighbors.

This problem is a classic example where the right comparison function transforms an otherwise hard combinatorial search into a simple O(n log n) sort. Once you see the comparator, the solution is one pass through a sort and a join.

The core insight is this: given two numbers a and b (as strings), a should come before b if the concatenation a+b is lexicographically greater than b+a. This single comparison defines a total ordering over all strings in the array.

For example, compare "9" and "34": "9"+"34" = "934" vs "34"+"9" = "349". Since "934" > "349", 9 comes before 34. Compare "3" and "30": "3"+"30" = "330" vs "30"+"3" = "303". Since "330" > "303", 3 comes before 30.

This comparator is complete — it handles numbers of different lengths, repeated digits, and all edge cases without any special logic. Once you define this comparator, the sort does all the work and the answer is simply the joined result.

The comparator defines a valid total order because it is transitive: if a+b > b+a and b+c > c+b, then a+c > c+a. This can be proven algebraically by expressing each string concatenation as a numeric sum (a * 10^|b| + b > b * 10^|a| + a) and applying transitivity through b.

Because the relation is transitive, antisymmetric, and total, it constitutes a strict total order. This means any sorting algorithm applied with this comparator will converge to the unique globally optimal arrangement — not just a locally greedy one.

The sorted order guarantees that no swap of any two adjacent elements can increase the result. This is the hallmark of an exchange argument proof, the same technique used to prove greedy algorithms in interval scheduling and task ordering.

The primary edge case is an input consisting entirely of zeros, such as [0, 0] or [0, 0, 0]. After sorting and joining, you get "000...0". The custom comparator correctly places all zeros together, but the concatenation is not a valid representation of zero.

The fix is simple: after joining, check if the first character of the result is "0". If it is, every element must be zero (since a non-zero number would sort before zero by the comparator), so return "0" instead of the multi-zero string.

No other edge cases exist. Single-element arrays work trivially. Arrays containing 0 mixed with non-zero numbers are handled correctly because any non-zero string a satisfies a+"0" > "0"+a for all a >= 1, placing non-zeros before zeros automatically.

Take the input [3, 30, 34, 5, 9]. Convert each integer to its string representation: ["3", "30", "34", "5", "9"]. Now apply the custom comparator pairwise to sort in descending order.

Comparing "9" vs "5": "95" > "59", so 9 first. Comparing "5" vs "34": "534" > "345", so 5 next. Comparing "34" vs "3": "343" > "334", so 34 before 3. Comparing "3" vs "30": "330" > "303", so 3 before 30.

The sorted order is ["9", "5", "34", "3", "30"]. Joining gives "9534330". This is the largest possible arrangement — verify by trying any swap: "9534330" beats "9534303", "9533430", and every other permutation.

In Python: convert all integers to strings with map(str, nums). Define a comparator using functools.cmp_to_key: return -1 if a+b > b+a (a comes first), +1 if a+b < b+a, else 0. Sort with sorted(strs, key=cmp_to_key(compare)). Join and handle the all-zeros edge case. Time complexity O(n log n * k) where k is the average digit length.

In Java: convert to String[] with Arrays.stream(nums).mapToObj(String::valueOf).toArray(String[]::new). Sort with Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b)). Join with String.join("", strs). Check if strs[0].equals("0") for the edge case and return "0" if true.

Both implementations are O(n log n * k) time where k is the average number of digits. The string comparison at each comparator call costs O(k) instead of O(1), so the true complexity is O(n log n * k). Space is O(n) for the string array. In practice k <= 10 for 32-bit integers so this is negligible.

Largest Number belongs to the custom comparator family of sorting problems. Hand of Straights requires grouping cards by custom consecutive rules. Sort Colors (the Dutch flag problem) partitions in-place using three-way partitioning. These all share the theme of defining a non-obvious ordering criterion.

Next Permutation is a close relative — both problems involve rearranging an array of numbers to achieve a specific numeric target (the next larger permutation vs the largest possible concatenation). The mental model of "what ordering rule makes this work" applies to both.

For interview preparation, group these together: Largest Number (179), Next Permutation (31), Sort Colors (75), Hand of Straights (846), and Custom Sort String (791). Each rewards the insight of finding the right comparison key rather than trying brute-force enumeration.