LeetCode 179: Largest Number Solution in Python Explained

Problem Statement

In LeetCode 179, you’re given an array of non-negative integers nums. Your task is to arrange them into the largest possible number by concatenating them as strings and return the result as a string (due to potential size exceeding integer limits). This differs from SQL ranking like LeetCode 178: Rank Scores, focusing on string manipulation and ordering rather than database queries.

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9

Example

Let’s see some cases:

Copy codeInput: nums = [10,2]
Output: "210"
Explanation: "210" > "102", so concatenate as 2 then 10.

Copy codeInput: nums = [3,30,34,5,9]
Output: "9534330"
Explanation: Arranging as [9,5,34,3,30] gives "9534330", the largest possible.

Copy codeInput: nums = [0,0]
Output: "0"
Explanation: "00" simplifies to "0".

These examples show we’re forming the largest number via concatenation.

Understanding the Problem

How do you solve LeetCode 179: Largest Number in Python? Take nums = [10,2]. Concatenating as "102" (10 then 2) or "210" (2 then 10), "210" is larger. For [3,30,34,5,9], we need "9534330", not "3303459" or others—ordering matters. Brute-forcing all permutations is inefficient (O(n!)), so we need a sorting strategy comparing concatenated pairs (e.g., "3" + "30" vs "30" + "3"). This isn’t a BST iteration task like LeetCode 173: Binary Search Tree Iterator; it’s about string ordering. We’ll use: 1. Custom Sorting with String Comparison: O(n log n) time, O(1) space—our best solution. 2. Brute Force Permutations: O(n!) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Custom Sorting with String Comparison Approach

Explanation

Custom Sorting with String Comparison sorts the numbers as strings with a custom comparator:

• Convert each number to a string.
• Sort using a key where x > y if x + y > y + x (e.g., "3" + "30" = "330" < "303" = "30" + "3").
• Concatenate the sorted strings.
• Handle edge case: if result starts with "0", return "0".

This achieves O(n log n) time (sorting), O(1) extra space (excluding output), and efficiency by leveraging string comparison to find the optimal order.

For [3,30,34,5,9]:

• Sort: [9,5,34,3,30] (e.g., "9" + "5" > "5" + "9").
• Concatenate: "9534330".

Step-by-Step Example

Example 1: nums = [10,2]

Goal: Return "210".

• Step 1: Convert to strings.
• ["10", "2"].
• Step 2: Custom sort.
• Compare "10" + "2" = "102" vs "2" + "10" = "210".
• "210" > "102", order: ["2", "10"].
• Step 3: Concatenate.
• "2" + "10" = "210".
• Step 4: Check leading zero.
• Not "0", return "210".
• Finish: Return "210".

Example 2: nums = [3,30,34,5,9]

Goal: Return "9534330".

• Step 1: ["3", "30", "34", "5", "9"].
• Step 2: Sort with custom key.
• "9" > "5" ("95" > "59"), "5" > "34" ("534" > "345"), etc.
• Result: ["9", "5", "34", "3", "30"].
• Step 3: Concatenate.
• "9" + "5" + "34" + "3" + "30" = "9534330".
• Step 4: Not "0", return "9534330".
• Finish: Return "9534330".

Example 3: nums = [0,0]

Goal: Return "0".

• Step 1: ["0", "0"].
• Step 2: Sort (order doesn’t matter, all same).
• ["0", "0"].
• Step 3: "00".
• Step 4: Starts with "0", return "0".
• Finish: Return "0".

How the Code Works (Custom Sorting with String Comparison) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef largestNumber(nums: list[int]) -> str:
    # Line 1: Convert numbers to strings
    nums = [str(num) for num in nums]
    # e.g., [10,2] → ["10", "2"]

    # Line 2: Custom comparison function
    from functools import cmp_to_key
    def compare(x: str, y: str) -> int:
        # Compare x+y vs y+x (e.g., "10"+"2" vs "2"+"10")
        if x + y > y + x:
            return -1  # x before y (e.g., "210" > "102")
        elif x + y < y + x:
            return 1   # y before x
        return 0       # equal

    # Line 3: Sort with custom key
    nums.sort(key=cmp_to_key(compare))
    # Sort descending based on concatenation (e.g., ["2", "10"])

    # Line 4: Concatenate result
    result = ''.join(nums)
    # Join strings (e.g., "210")

    # Line 5: Handle leading zero case
    return result if result[0] != '0' else '0'
    # Return "0" if all zeros (e.g., "00" → "0"), else result

This detailed breakdown clarifies how custom sorting efficiently forms the largest number.

Alternative: Brute Force Permutations Approach

Explanation

Brute Force Permutations generates all possible arrangements:

• Use Python’s itertools.permutations to get all permutations.
• Concatenate each permutation into a string.
• Find the maximum string value.
• Handle leading zero case.

It’s a practical alternative, O(n!) time (n permutations), O(n) space per permutation, but impractical for large n due to exponential complexity.

For [10,2]:

• Permutations: "102", "210".
• Max: "210".

Step-by-Step Example (Alternative)

For [3,30,34]:

• Step 1: Permutations.
• [3,30,34], [3,34,30], [30,3,34], [30,34,3], [34,3,30], [34,30,3].
• Step 2: Concatenate.
• "33034", "33430", "30334", "30343", "34330", "34303".
• Step 3: Max.
• "34330".
• Finish: Return "34330".

How the Code Works (Brute Force)

Copy codefrom itertools import permutations

def largestNumberBrute(nums: list[int]) -> str:
    nums = [str(num) for num in nums]
    max_num = "0"
    for perm in permutations(nums):
        curr = ''.join(perm)
        if curr[0] != '0' or curr == "0":
            max_num = max(max_num, curr)
    return max_num

Complexity

• Custom Sorting with String Comparison:
• Time: O(n log n) – sorting with string comparisons.
• Space: O(1) – minimal extra space (excluding output).
• Brute Force Permutations:
• Time: O(n!) – all permutations.
• Space: O(n) – per permutation storage.

Efficiency Notes

Custom Sorting with String Comparison is the best solution with O(n log n) time and O(1) space, offering efficiency and scalability—Brute Force Permutations uses O(n!) time, making it impractical for large n, though conceptually simple, with O(n) space per permutation.

Key Insights

• Custom Sort: Compares concatenations.
• Permutations: Exhaustive search.
• Leading Zero: Edge case handling.

Additional Example

For nums = [1,2,3]:

• Goal: "321".
• Sort: ["3","2","1"], return "321".

Edge Cases

• All Zeros: [0,0] → "0".
• Single Number: [5] → "5".
• Large Numbers: [10,20] → "2010".

Both solutions handle these well, but brute force is slower.

Final Thoughts

LeetCode 179: Largest Number in Python is a clever sorting challenge. The Custom Sorting with String Comparison solution excels with its efficiency and elegance, while Brute Force Permutations offers a basic approach. Want more? Try LeetCode 56: Merge Intervals for sorting practice or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 179 on LeetCode with [3,30,34,5,9], aiming for "9534330"—test your skills now!