Show problems as
Classic problem #386MediumDepth-First SearchTrie

Lexicographical Numbers

Real-world version: Picking Bins in Terminal Order
Tracked in this browser only
Read Lexicographical Numbers on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A stationery warehouse tags its picking bins with the whole numbers 1 through n. A tag is printed with no padding of any kind, so bin seven carries the tag 7 and bin seventy carries the tag 70.

The stock terminal sorts tags the way it sorts words. It lines two tags up at their first character and walks rightwards, and the first character where they differ decides the order, the earlier character winning. If one tag runs out while matching the other character for character all the way, the shorter tag is placed first.

Return the bin numbers in the order the terminal lists their tags.

Produce the listing by stepping from one tag to the next rather than by sorting: spend time proportional to n and keep only a constant amount of working memory aside from the listing you return.

Examples

Example 1

Input
n = 9
Output
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Every tag is a single character here, so walking the characters puts them in the same order as counting.

Example 2

Input
n = 11
Output
[1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9]

The tags 10 and 11 both open with the character 1 and continue past where the tag 1 ends, so they follow it and precede the tag 2.

Example 3

Input
n = 15
Output
[1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9]

All six tags opening with the character 1 sit together in order of their second character, and the single-character tags 2 through 9 come afterwards.

Example 4

Input
n = 19
Output
[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 3, 4, 5, 6, 7, 8, 9]

The block opening with the character 1 now runs to the tag 19, and the remaining single-character tags follow it.

Constraints

  • 1 <= n <= 5 * 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def lexical_order(n: int) -> list[int]:
Java
public List<Integer> lexicalOrder(int n)

More on the same topics