How do you solve Largest Number on LeetCode?

Largest Number (LeetCode #179) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: The order of concatenation matters significantly in determining the largest number.

What is the brute force solution for Largest Number?

The brute force approach for Largest Number is Brute Force, with O(n!) time complexity and O(n) space complexity. The brute force approach involves generating all possible permutations of the numbers, converting each permutation to a string, and then comparing them to find the largest one. This method is straightforward but inefficient for larger inputs. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Largest Number?

Largest Number uses the following concepts: Array, String, Greedy, Sorting. The recommended patterns to study are: Sorting, Greedy.

What are the interview tips for Largest Number?

Explain your thought process clearly while coding. Discuss edge cases before diving into the solution. Practice writing custom comparators, as they are common in sorting problems.

What are common mistakes when solving Largest Number?

Not considering edge cases like leading zeros. Using default sorting without a custom comparator.

#179

Largest Number

Medium

ArrayStringGreedySortingSortingGreedy

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n!)	O(n log n)
Space	O(n)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

The optimal approach sorts the numbers based on a custom comparison that determines which concatenation of two numbers forms a larger number. This is efficient and avoids the overhead of generating permutations.

⚙️

Algorithm

3 steps

1Step 1: Convert all integers to strings for comparison.
2Step 2: Sort the strings based on a custom comparator that checks which concatenation is larger.
3Step 3: Concatenate the sorted strings to form the largest number.

solution.py9 lines

1from functools import cmp_to_key
2
3def compare(x, y):
4    return (y + x > x + y) - (y + x < x + y)
5
6def largestNumber(nums):
7    nums_str = list(map(str, nums))
8    nums_str.sort(key=cmp_to_key(compare))
9    return ''.join(nums_str) if nums_str[0] != '0' else '0'

ℹ

Complexity note: The time complexity is O(n log n) due to the sorting step, which is efficient for the input size. The space complexity is O(n) for storing the string representations of the numbers.

1The order of concatenation matters significantly in determining the largest number.
2Sorting with a custom comparator is key to solving this problem efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.