DSA Tracker

Visualize

Largest Number

Sort by which pair reads bigger, not by size

time O(n log n * L)space O(n * L)

Sorting the numbers by their own value is the trap: 3 is smaller than 30, yet 3 belongs first, because 330 beats 303. Size is the wrong question. The only question that matters between two values is which order reads larger when they are glued together, so that comparison IS the sort key: a comes before b when a+b > b+a as text. That rule is consistent across the whole list, which is why one sort settles every slot at once and no later rearrangement can improve the total. The single exception is an input of nothing but zeros, where the join reads 000 and has to be reported as 0.

Details

Animated on: nums = [3, 30, 34, 5, 9, 35]. Arrange every number end to end so the resulting number is as large as possible.

Problem:Largest NumberMedium

Sort by which pair reads bigger, not by size

step 1 / 15

3
[0]
30
[1]
34
[2]
5
[3]
9
[4]
35
[5]

Plain numeric order would put 35, 34, 30, 9, 5, 3 on the page, and that is wrong: it reads 353430953. What decides the answer is never a number's size but how a PAIR reads glued together — so the whole sort runs on "3" + "30" against "30" + "3".

Pseudocode
1FUNCTION largestNumber(nums)
2  s <- STRINGS(nums)
3  FOR i <- 0 TO LENGTH(s) - 2
4    best <- i
5    FOR j <- i + 1 TO LENGTH(s) - 1
6      IF CONCAT(s[j], s[best]) > CONCAT(s[best], s[j])
7        best <- j
8    SWAP s[i], s[best]
9  IF s[0] = "0"
10    RETURN "0"
11  RETURN JOIN(s)

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. Plain numeric order would put 35, 34, 30, 9, 5, 3 on the page, and that is wrong: it reads 353430953. What decides the answer is never a number's size but how a PAIR reads glued together — so the whole sort runs on "3" + "30" against "30" + "3".
  2. "34" + "3" = 343 beats "3" + "34" = 334, so putting 34 in front is worth more than putting 3 in front. 34 takes over as the best candidate for slot 0.
  3. "5" + "34" = 534 beats "34" + "5" = 345, so putting 5 in front is worth more than putting 34 in front. 5 takes over as the best candidate for slot 0.
  4. "9" + "5" = 95 beats "5" + "9" = 59, so putting 9 in front is worth more than putting 5 in front. 9 takes over as the best candidate for slot 0.
  5. 9 won every pairwise glue against 30, 34, 5, 3, 35, so nothing left can improve slot 0 — it is locked. The answer now starts 9, and the 5 unplaced values fight over what follows.
  6. "34" + "30" = 3430 beats "30" + "34" = 3034, so putting 34 in front is worth more than putting 30 in front. 34 takes over as the best candidate for slot 1.
  7. "5" + "34" = 534 beats "34" + "5" = 345, so putting 5 in front is worth more than putting 34 in front. 5 takes over as the best candidate for slot 1.
  8. 5 won every pairwise glue against 34, 30, 3, 35, so nothing left can improve slot 1 — it is locked. The answer now starts 95, and the 4 unplaced values fight over what follows.
  9. "35" + "34" = 3534 beats "34" + "35" = 3435, so putting 35 in front is worth more than putting 34 in front. 35 takes over as the best candidate for slot 2.
  10. 35 won every pairwise glue against 30, 3, 34, so nothing left can improve slot 2 — it is locked. The answer now starts 9535, and the 3 unplaced values fight over what follows.
  11. "3" + "30" = 330 beats "30" + "3" = 303, so putting 3 in front is worth more than putting 30 in front. 3 takes over as the best candidate for slot 3.
  12. "34" + "3" = 343 beats "3" + "34" = 334, so putting 34 in front is worth more than putting 3 in front. 34 takes over as the best candidate for slot 3.
  13. 34 won every pairwise glue against 3, 30, so nothing left can improve slot 3 — it is locked. The answer now starts 953534, and the 2 unplaced values fight over what follows.
  14. 3 won every pairwise glue against 30, so nothing left can improve slot 4 — it is locked. The answer now starts 9535343, and only 30 is left to follow it.
  15. Every slot is settled: 9 | 5 | 35 | 34 | 3 | 30 glues to 953534330. Sorting by "which of us reads bigger in front" is enough because that rule is consistent — if 9 beats 5 and 5 beats 35, then 9 beats 35, so no swap made later could ever raise the total. The only special case left is an all-zero input, where the join would read 000 and must collapse to a single 0.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Largest Number in the editorAll Greedy problemsBack to roadmap