Biggest Number From Price Tags
MediumSorting & Searching
Problem
A street vendor has a box of price tags, each printed with a non-negative integer tags[i]. For a promotion she lines up all the tags side by side to read one long number.
Return, as a string, the largest number she can form. The answer must not have leading zeros: if every tag is 0, return "0".
Example 1
- Input:
- tags = [7, 70, 75, 4]
- Output:
- "775704"
7 goes before 75 because 775 > 757, 75 before 70 because 7570 > 7075, and 70 before 4 because 704 > 470.
Example 2
- Input:
- tags = [10, 2]
- Output:
- "210"
Example 3
- Input:
- tags = [0, 0]
- Output:
- "0"
Constraints
- 1 ≤ tags.length ≤ 10^4
- 0 ≤ tags[i] ≤ 10^9
Hint
Show the first hint
Sorting the numbers by value fails (10 before 2 gives 102). Sorting as strings fails too (30 vs 3). What should decide which of two tags goes first?
Walkthrough
How to approach it
01Clarify before coding
- Must every tag be used? Yes, all of them.
- Why a string result? The concatenation of 10^4 numbers is far beyond any integer type.
- What about only zeros? Return "0", not "000".
02Brute force
Try every permutation of the tags, concatenate each, and keep the largest string of that length.
Cost: O(n! · L): hopeless past about 10 tags.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.