Abstract / Summary

Given a list of non-negative integers, arrange them as strings to form the largest possible concatenated number.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 43% (2+ million submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Sorting
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method largestNumber that receives a list of integers and returns a string representing the largest possible concatenated number formed by arranging the integers. The algorithm proceeds in several distinct phases: conversion of integers to strings, an initial descending lexical sort, a corrective bubble-style pass to resolve ordering anomalies, removal of leading zeros, and final concatenation.

Key Steps

The first phase creates a list of string representations of the input numbers. This conversion enables direct string concatenation for comparison.

all = []
for n in nums:
    all.append(str(n))

The second phase applies Python’s built-in sort in reverse order. For most inputs this ordering already yields the correct arrangement because larger numeric strings tend to precede smaller ones when sorted lexicographically in descending order.

all.sort(reverse = True)

The third phase introduces an iterative correction loop. It repeatedly scans adjacent pairs and swaps them whenever the concatenation of the left element followed by the right element is lexicographically smaller than the opposite order. The loop continues until a full pass makes no swaps, guaranteeing that no adjacent pair violates the desired ordering criterion.

again = True
while again:
    again = False
    for i in range(1, len(all)):
        if all[i - 1] + all[i] < all[i] + all[i - 1]:
            all[i - 1], all[i] = all[i], all[i - 1]
            again = True

The fourth phase eliminates superfluous leading zeros that can appear when the input consists solely of zeros or when zeros are positioned at the front after sorting. It repeatedly deletes the first element while the list contains more than one element and the leading element equals the string "0".

while len(all) > 1 and all[0] == "0":
    del all[0]

The final step concatenates the processed list of strings into a single result string, which is returned to the caller.

return "".join(all)

Edge Cases Handled

The algorithm explicitly addresses the situation where the input list contains only zeros or a mixture that would otherwise produce a leading zero in the final output. By iteratively removing the first element while it is "0" and more than one element remains, the method ensures that a solitary zero is returned instead of an empty string or a string with multiple leading zeros.

Another implicit edge case is the handling of numbers that, when converted to strings, have differing lengths but could affect ordering. The corrective loop examines every adjacent pair and swaps them if the concatenated order is unfavorable, thereby handling cases where the initial reverse sort does not produce the optimal arrangement-for example, inputs like [3, 30, 34, 5, 9] where "30" should follow "3".

Performance Optimizations

The use of Python’s native list.sort with the reverse=True flag leverages the highly optimized Timsort algorithm, providing a fast baseline ordering for the majority of inputs. By performing this initial sort, the subsequent corrective loop often requires few or no swaps, reducing the number of iterations needed to reach a stable ordering.

The corrective loop itself is designed to terminate early when no swaps occur in a full pass, avoiding unnecessary work. The condition again = False at the start of each outer iteration ensures that the loop exits as soon as the list is correctly ordered, preventing endless scanning.

The removal of leading zeros employs a simple while loop that deletes the first element only when necessary, avoiding the overhead of constructing a new list or performing more complex index calculations.

Overall, the combination of an efficient built-in sort, a targeted adjacent-pair correction mechanism, and minimal post-processing steps yields a solution that balances correctness with practical performance for typical input sizes.

Imagine you have a big pile of number cards and you want to arrange them into one long, giant row so that the number looks as large as possible. First, the computer takes every number and turns it into a little word made of digits.

Next, the computer puts the largest cards at the front of the line to get started. Sometimes, though, putting a number in one spot makes it look smaller than if it were in a different spot. For example, if you have a nine and a ninety-one, you want to see which order makes a bigger number when you stick them together. The computer looks at every pair of neighbors and swaps them if switching their places makes the total number bigger. It keeps checking these pairs over and over until every number is in the best spot to make the biggest string.

Finally, if the line starts with a zero, the computer takes that zero away so you do not have extra zeros at the front. When everything is in the right order, the computer glues all the digits together into one final result.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java							TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python	C#	Java		JS				Go	TS
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	aylei					Rust
	begeekmyfriend							C
	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai				Java
	chenyanzhe	C++
	everthis						JS
	fartem									Ruby
	FelixFan1122			C#
	gaosq0604		Python
	Garvit244		Python
	halfrost										Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx							C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	martianoff								Scala
	qiyuangong				Java
	ruoru					Rust
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
	XiaotaoGuo	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
martianoff	Scala
qiyuangong	Java
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
XiaotaoGuo	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality