Largest Number
Asked at Adobe
Problem
Given a list of non-negative integers, arrange them such that they form the largest possible number and return it as a string. For example, [3, 30, 34, 5, 9] should return "9534330". The result may be extremely large and cannot fit in a 32-bit integer.
Asked At
| Company | Difficulty | |
|---|---|---|
| Adobe | MEDIUM | View all Adobe questions → |
How to Think About It
Brute force: Generate all permutations and compare concatenated results — O(n! * n) time.
Greedy insight: Define a custom comparator where a sorts before b if ab > ba.
Convert all integers to strings to avoid integer overflow during concatenation.
After sorting, concatenate and handle the edge case where the result is all zeros.
Optimal: Custom sort with string comparison comparator — O(n log n * k) time where k is avg digit length.
Optimal Approach
Convert all numbers to strings and sort them with a custom comparator: for two strings a and b, a should come before b if a+b > b+a lexicographically. Concatenate the sorted array. If the result starts with '0', return '0' (all elements were zero). This greedy approach guarantees the largest possible concatenation because the comparator is transitive and captures the exact ordering needed. Time is O(n log n * k) where k is the average string length.
What Trips People Up in Real Interviews
Clarify that the output is a string, not an integer, since it can exceed 64-bit range.
Explain the comparator: for strings a and b, compare a+b vs b+a lexicographically.
Handle the edge case [0, 0, 0] → return "0", not "000".
Mention that Python's sort is stable, but the comparator handles all cases anyway.
Walk through [10, 2] → "210" since "210" > "102" to verify your comparator logic.
Solution Code
from functools import cmp_to_key
class Solution:
def largestNumber(self, nums):
strs = [str(n) for n in nums]
strs.sort(key=cmp_to_key(lambda a, b: 1 if a + b < b + a else -1))
result = ''.join(strs)
return '0' if result[0] == '0' else resultFrequently Asked Questions
What is the Largest Number problem?
Given a list of non-negative integers, arrange them such that they form the largest possible number and return it as a string. For example, [3, 30, 34, 5, 9] should return "9534330". The result may be extremely large and cannot fit in a 32-bit integer.
How do you solve Largest Number?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Largest Number?
Largest Number is asked at Adobe. It is a medium difficulty problem.
What are common mistakes on Largest Number?
- Clarify that the output is a string, not an integer, since it can exceed 64-bit range.
- Explain the comparator: for strings a and b, compare a+b vs b+a lexicographically.
- Handle the edge case [0, 0, 0] → return "0", not "000".
- Mention that Python's sort is stable, but the comparator handles all cases anyway.
- Walk through [10, 2] → "210" since "210" > "102" to verify your comparator logic.