LeetCode Problem 179

Difficulty: 🟡 Medium
Topics: Array, String, Greedy, Sorting

Solution

LeetCode 179 - Largest Number

Problem Understanding

This problem asks us to rearrange a list of non-negative integers so that, when concatenated together, they form the largest possible number.

At first glance, this may look like a straightforward sorting problem where we simply sort the numbers in descending order. However, the challenge comes from the fact that the ordering depends on how numbers interact when placed next to each other.

For example, consider the input [3, 30].

If we sort numerically in descending order, we would place 30 before 3, producing "303". However, "330" is larger than "303", meaning 3 should come first. This shows that ordinary numerical sorting does not work.

Instead, we need to determine, for every pair of numbers a and b, whether placing a before b or b before a creates a larger result.

The input consists of an integer array nums, where:

• Each value is a non-negative integer.
• The length of the array is between 1 and 100.
• Each number can be as large as 10^9.

The expected output is a string, not an integer. This requirement exists because the resulting concatenated number may become extremely large and exceed standard integer limits.

The constraints tell us that the input size is relatively small, at most 100 numbers. This means sorting based solutions are practical. However, brute force permutation generation would still be infeasible because permutations grow factorially.

Several edge cases are important to recognize upfront.

The first tricky case is when all numbers are zero, such as [0,0]. A naive concatenation after sorting might return "00", but the correct answer is "0".

Another important case involves numbers with shared prefixes, such as 3 and 30, or 12 and 121. Numerical sorting or lexicographical sorting fails here because the best ordering depends on concatenation.

The problem guarantees that all numbers are non-negative, which simplifies implementation because we do not need to handle negative signs.

Approaches

Brute Force Approach

A brute force solution would generate every possible arrangement of the numbers and compute the resulting concatenated number for each permutation. After evaluating all permutations, we return the largest result.

For example, given [10,2], we would generate:

• "102"
• "210"

Then select "210" as the maximum.

This approach is guaranteed to be correct because it exhaustively checks every possible ordering. Since the optimal arrangement must exist among all permutations, brute force will always find it.

However, the problem is that the number of permutations grows factorially. For n numbers, there are n! possible arrangements. Even with only 100 elements, this becomes computationally impossible.

Optimal Approach

The key observation is that we do not need to test every permutation. Instead, we can define a custom sorting rule.

Suppose we have two numbers represented as strings, a and b.

To determine which should come first, we compare:

• a + b
• b + a

If a + b produces a larger value, then a should appear before b.

For example:

• a = "3"
• b = "30"

Compare:

• "330"
• "303"

Since "330" is larger, "3" should come before "30".

This comparison rule gives us a way to sort the entire array greedily. Once sorted, we concatenate all strings to form the answer.

The reason this works is that every local comparison ensures the globally optimal concatenation order.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n)	O(n! × n)	Generates every permutation and compares results
Optimal	O(n log n × k)	O(n)	Uses custom sorting based on concatenation comparison

Here, k represents the average string length of the numbers, which is small because numbers are at most 10^9.

Algorithm Walkthrough

Optimal Algorithm

1. Convert every integer into a string.

We perform comparisons using concatenation, so strings are easier to work with than integers. For example, 30 becomes "30". 2. Define a custom comparison rule.

For any two strings a and b, compare a + b with b + a.

If a + b > b + a, then a should come before b.

For example:

• a = "9"
• b = "34"

Compare:

• "934"
• "349"

Since "934" is larger, "9" comes first. 3. Sort the string array using this custom comparator.

The sorting process repeatedly compares pairs and arranges them so that the final ordering maximizes the concatenated result. 4. Handle the all-zero edge case.

After sorting, if the first element is "0", then every number must be zero.

For example:

• Sorted: ["0","0","0"]

Returning "000" would be incorrect.

Instead, return "0". 5. Concatenate all sorted strings.

Join the strings together to produce the final largest number.

Why it works

The correctness relies on the ordering rule.

For any two elements a and b, placing them in the order that maximizes a+b versus b+a ensures the best local arrangement. Since sorting enforces this relationship across all adjacent elements, the final sequence is globally optimal.

In other words, if every neighboring pair is arranged optimally, no swap can further improve the result.

Python Solution

from typing import List
from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        string_numbers = [str(num) for num in nums]

        def compare(a: str, b: str) -> int:
            if a + b > b + a:
                return -1
            if a + b < b + a:
                return 1
            return 0

        string_numbers.sort(key=cmp_to_key(compare))

        if string_numbers[0] == "0":
            return "0"

        return "".join(string_numbers)

The implementation begins by converting every integer into a string because concatenation comparisons are central to the solution.

The compare function defines the custom ordering rule. Instead of comparing numeric values directly, it compares the two possible concatenations:

• a + b
• b + a

If a + b is larger, we return -1 so that Python places a before b during sorting.

Python's built in sorting function expects a key function rather than a comparator. To bridge this gap, we use cmp_to_key, which converts the comparator into a sortable key.

After sorting, we check whether the first element is "0". Since the largest number would always appear first, this condition guarantees that every number is zero.

Finally, we join the sorted strings together into the final result.

Go Solution

package main

import (
	"sort"
	"strconv"
	"strings"
)

func largestNumber(nums []int) string {
	stringNums := make([]string, len(nums))

	for i, num := range nums {
		stringNums[i] = strconv.Itoa(num)
	}

	sort.Slice(stringNums, func(i, j int) bool {
		return stringNums[i]+stringNums[j] >
			stringNums[j]+stringNums[i]
	})

	if stringNums[0] == "0" {
		return "0"
	}

	return strings.Join(stringNums, "")
}

The Go implementation follows the same overall strategy as the Python version but uses sort.Slice with a custom comparison function.

Unlike Python, Go sorting directly accepts a comparator through a boolean function. If the concatenation a+b is larger than b+a, the comparator returns true, meaning a should come before b.

The implementation uses strconv.Itoa() to convert integers into strings and strings.Join() to concatenate the final result efficiently.

Go slices are dynamic views over arrays, so no special handling is needed for empty versus nil slices because the problem guarantees at least one element.

Integer overflow is also not a concern because we never convert the final result into an integer. Everything remains as strings.

Worked Examples

Example 1

Input: nums = [10,2]

Convert to strings:

Index	Value
0	"10"
1	"2"

Comparison:

Compare	Result
"102" vs "210"	"210" is larger

Therefore:

"2" comes before "10".

Sorted array:

Position	Value
0	"2"
1	"10"

Concatenation:

"2" + "10" = "210"

Final answer:

"210"

Example 2

Input: nums = [3,30,34,5,9]

Convert to strings:

Value
"3"
"30"
"34"
"5"
"9"

Important comparisons:

Comparison	Winner
"330" vs "303"	"3" before "30"
"343" vs "334"	"34" before "3"
"534" vs "345"	"5" before "34"
"95" vs "59"	"9" before "5"

Sorted order:

Position	Value
0	"9"
1	"5"
2	"34"
3	"3"
4	"30"

Concatenation:

"9" + "5" + "34" + "3" + "30"
= "9534330"

Final answer:

"9534330"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n × k)	Sorting requires O(n log n) comparisons, each comparison costs O(k) for concatenation
Space	O(n)	Extra storage is used for string conversion

The dominant cost comes from sorting. Each comparison creates temporary concatenated strings of length proportional to k, where k is the maximum number of digits. Since k is bounded by about 10, the solution performs efficiently in practice.

Test Cases

solution = Solution()

assert solution.largestNumber([10, 2]) == "210"  # Example 1
assert solution.largestNumber([3, 30, 34, 5, 9]) == "9534330"  # Example 2

assert solution.largestNumber([0]) == "0"  # Single zero
assert solution.largestNumber([0, 0]) == "0"  # Multiple zeros
assert solution.largestNumber([1]) == "1"  # Single element

assert solution.largestNumber([12, 121]) == "12121"  # Prefix overlap
assert solution.largestNumber([34323, 3432]) == "343234323"  # Tricky ordering

assert solution.largestNumber([999999998, 999999997]) == "999999998999999997"  # Large values

assert solution.largestNumber([20, 1]) == "201"  # Larger prefix first
assert solution.largestNumber([8308, 830]) == "8308830"  # Shared prefix edge case

Test	Why
[10,2]	Validates the first example
[3,30,34,5,9]	Validates the second example
[0]	Smallest valid input
[0,0]	Ensures all-zero handling works
[1]	Single element boundary case
[12,121]	Verifies prefix comparison correctness
[34323,3432]	Tests tricky comparator behavior
[999999998,999999997]	Ensures large values work correctly
[20,1]	Verifies concatenation ordering
[8308,830]	Tests shared prefix behavior

Edge Cases

All Values Are Zero

An input such as [0,0,0] is a common source of bugs. After sorting, naive implementations might return "000", which is technically the concatenation but not the expected representation of the number.

This implementation handles the issue by checking whether the first sorted value is "0". Since sorting places the largest element first, if the largest is zero, every element must also be zero. In that case, we return "0".

Numbers With Shared Prefixes

Inputs like [3,30] or [12,121] can break naive numerical or lexicographical sorting approaches.

For example, numerical descending order would incorrectly place 30 before 3, resulting in "303" instead of "330".

The custom comparison logic fixes this by comparing a+b and b+a, ensuring the ordering maximizes the concatenated result.

Single Element Arrays

An input such as [7] is a boundary case because sorting logic still executes even though there is only one number.

The implementation naturally handles this case. The string conversion produces ["7"], sorting changes nothing, and joining returns "7" correctly.