Biggest Number From the Pieces

MediumGreedy

Problem

You have number tiles pieces, each showing a non-negative integer. Lay all tiles in a row to read one long number.

Return the largest number you can form, as a string without leading zeros (all-zero tiles give "0").

Example 1

Input:
pieces = [9, 40, 4]
Output:
"9440"

4 goes before 40 because 440 > 404.

Example 2

Input:
pieces = [12, 121]
Output:
"12121"

12|121 = 12121 beats 121|12 = 12112.

Example 3

Input:
pieces = [0, 0]
Output:
"0"

Constraints

  • 1 ≤ pieces.length ≤ 100
  • 0 ≤ pieces[i] ≤ 10^9

Hint

Show the first hint

Plain numeric or plain string sorting both fail on some pair. Try two tiles a and b: how do you decide which goes first?

Walkthrough

How to approach it

01Clarify before coding

  • Must every tile be used? Yes.
  • Can the result exceed 64-bit integers? Yes (up to 1000 digits), so build a string.
  • What about leading zeros? Only possible when every tile is 0; return "0" then.

02Brute force

Try all permutations of the tiles and keep the largest concatenation.

Cost: O(n! · L): impossible for 100 tiles.

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.

Solve it in the browserStart free

This problem is part of Pro.