179. Largest Number - Explanation

Problem Link

Description

You are given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]

Output: "210"

Example 2:

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

Output: "9534330"

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1,000,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

To form the largest number, we need to decide the order of numbers such that when concatenated, they produce the maximum value. The key insight is that comparing two numbers a and b requires checking which concatenation is larger: a + b or b + a. For example, given 9 and 34, we compare "934" vs "349" and pick the order that gives the larger result.

The brute force approach repeatedly finds the "best" number to place next by comparing all remaining numbers using this concatenation rule, then appends it to the result.

Algorithm

1. Convert all integers to strings for easy concatenation comparison.
2. Initialize an empty result list.
3. While numbers remain:
   • Find the number that should come first by comparing arr[i] + arr[maxi] vs arr[maxi] + arr[i] for all candidates.
   • Append the best number to the result and remove it from the list.
4. Join all strings and handle the edge case where the result is all zeros (return "0").

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

        res = []
        while arr:
            maxi = 0
            for i in range(1, len(arr)):
                if arr[i] + arr[maxi] > arr[maxi] + arr[i]:
                    maxi = i
            res.append(arr[maxi])
            arr.pop(maxi)

        result = "".join(res)
        return result if result[0] != '0' else '0'

Time & Space Complexity

• Time complexity: $O(n * N)$
• Space complexity: $O(N)$

Where $n$ is the size of the array $nums$ and $N$ is the total number of digits in the array $nums$.

---

2. Sorting

Intuition

Instead of repeatedly scanning for the best number, we can use sorting with a custom comparator. The comparator determines the order by checking if a + b > b + a. By sorting the entire array once using this rule, numbers naturally arrange themselves so that their concatenation yields the largest possible value.

This approach is more efficient because sorting is faster than repeatedly finding and removing the maximum element.

Algorithm

1. Convert all integers to strings.
2. Sort the strings using a custom comparator: for strings a and b, place a before b if a + b > b + a.
3. Concatenate all sorted strings.
4. Handle the edge case where the result starts with "0" (all zeros) by returning "0".

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

        def compare(n1, n2):
            if n1 + n2 > n2 + n1:
                return -1
            else:
                return 1
        nums = sorted(nums, key=cmp_to_key(compare))
        return str(int("".join(nums)))

Time & Space Complexity

• Time complexity: $O(N \log N)$
• Space complexity: $O(N)$

Where $N$ is the total number of digits in the array $nums$.