0337MediumEnumeration

Staircase Serial Numbers In A Window

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 parts catalogue reserves a special shape of serial number for its display models. A staircase serial is a positive integer of two or more digits in which each digit is exactly one more than the digit to its left. 45, 678 and 23456 are staircase serials; 55, 321 and 1357 are not, and neither is anything containing a 0, since no digit is one more than 9.

Given an inclusive window [low, high], return every staircase serial that falls inside it, listed from smallest to largest. Return an empty list when the window holds none.

Examples

Example 1

Input: low = 1000, high = 13000
Output: [1234, 2345, 3456, 4567, 5678, 6789, 12345]

Six four-digit staircase serials sit inside the window, and 12345 is the only five-digit one below 13000.

Example 2

Input: low = 5678, high = 9012
Output: [5678, 6789]

The lower end of the window is itself a staircase serial and so counts; 6789 is the only other one before the window closes.

Example 3

Input: low = 100, high = 110
Output: []

The three-digit serials of this shape are 123 and up, so nothing in the window qualifies and the list comes back empty.

Example 4

Input: low = 45, high = 45
Output: [45]

The window is a single value and 5 is one more than 4, so that value is the whole answer.

Constraints

10 <= low <= high <= 10^9

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 staircase_serials(low: int, high: int) -> list[int]:

Java

public List<Integer> staircaseSerials(int low, int high)

The intended approach

Time O(1), at most 36 candidatesSpace O(1) beyond the returned list, which holds at most 36 values

A staircase serial is fixed by its length and its first digit, and both are tiny: lengths run from two to nine and the digits must come from 1 through 9 without wrapping. Reading each block of consecutive digits out of the string 123456789 produces every candidate, and doing the lengths in increasing order emits them in increasing numeric order, so the survivors of the window test are already sorted.

Pythonentry point: staircase_serials

def staircase_serials(low, high):
    # Every staircase serial is a block of consecutive digits taken from
    # 123456789, so there are only 36 of them in total. Walk them by length so
    # they come out already ascending.
    # Time O(1): at most 36 candidates are examined whatever the window is.
    # Space O(1) beyond the returned list, which holds at most 36 values.
    digits = "123456789"
    found = []
    for size in range(2, 10):
        for start in range(0, 10 - size):
            value = int(digits[start:start + size])
            if low <= value <= high:
                found.append(value)
    return found

The obvious version

Walk every integer in the window and test its digits pairwise.

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_staircase_serials(low, high):
    out = []
    for v in range(low, high + 1):
        s = str(v)
        ok = len(s) >= 2
        for i in range(1, len(s)):
            if ord(s[i]) - ord(s[i - 1]) != 1:
                ok = False
                break
        if ok:
            out.append(v)
    return out

How this problem was checked

Reference solution executed against 8 test cases — 8 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