0436MediumDepth-First SearchTrie

Picking Bins in Terminal Order

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def lexical_order(n: int) -> list[int]:

Java

public List<Integer> lexicalOrder(int n)

The intended approach

Time O(n * d) where d is the digit count of n, at most 5 under the stated ceiling, so linear in n: every step does constant work plus a shave bounded by the digit count.Space O(1) beyond the returned listing: one running tag.

Hold a single current tag, starting at one, and emit it `n` times over, each time moving to whichever tag the terminal would place immediately after it. Appending a zero to the current tag gives the smallest tag that starts with it, so take that whenever the result still names a bin. When it does not, the next tag is reached by shaving digits off the right until the remaining prefix can be raised by one while staying inside the range, then raising it. Nothing but the current tag is carried between steps.

Pythonentry point: lexical_order

def lexical_order(n):
    # Walk the tags in terminal order one step at a time. From a tag, the next tag
    # is that tag with a zero appended whenever that still names a bin; otherwise
    # it is the nearest ancestor tag that can be bumped by one without leaving the
    # range, found by shaving trailing digits that cannot be bumped. Each step is
    # constant work apart from the shaving, which is bounded by the digit count.
    # O(n * d) time with d <= 5 the digit count of n, so linear in n for the stated
    # ceiling; O(1) working memory beyond the returned listing.
    listing = []
    tag = 1
    for _ in range(n):
        listing.append(tag)
        if tag * 10 <= n:
            tag *= 10
        else:
            while tag % 10 == 9 or tag + 1 > n:
                tag //= 10
            tag += 1
    return listing

The obvious version

Materialise every bin number, render each as text, and hand the whole set to a comparison sort keyed on that text.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_lexical_order(n):
    return sorted(range(1, n + 1), key=str)

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in