Taro Logo

Stepping Numbers

#5 Most AskedMedium
Topics:
RecursionGraphs

A Stepping Number is an integer such that all of its adjacent digits have an absolute difference of exactly 1. For example, 321 is a Stepping Number while 421 is not.

Given two integers low and high, find and return a sorted list of all the Stepping Numbers in the range [low, high] inclusive.

Example 1:

Input: low = 0, high = 21
Output: [0,1,2,3,4,5,6,7,8,9,10,12,21]

Example 2:

Input: low = 10, high = 15
Output: [10,12]

Constraints:

  • 0 <= low <= high <= 2 * 109

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Is a number included when it equals either endpoint of the range?
  2. Are single-digit numbers, including zero, always stepping numbers?
  3. Must the absolute difference between neighboring digits be exactly one?
  4. Should the result be sorted in increasing order without duplicates?
  5. Can the upper endpoint be as large as two billion, so every stepping number in that span must be returned?

Brute Force Solution

Approach

Every integer from the lower endpoint through the upper endpoint is tested. A one-digit number is accepted immediately, and a longer number is accepted only when every pair of neighboring digits differs by exactly one. The accepted numbers are sorted before they are returned.

Here's how the algorithm would work step-by-step:

  1. Walk from the lower endpoint through the upper endpoint, including both ends.
  2. Treat a number with one digit as a stepping number and record it.
  3. Otherwise compare each pair of neighboring digits.
  4. Reject the number as soon as any pair differs by something other than one.
  5. Record the number when every neighboring pair differs by one.
  6. Sort the recorded numbers and return them.

Code Implementation

def find_stepping_numbers_brute_force(start_number, end_number):
    stepping_numbers_result = []

    # Iterate through every single number in the given range to check if it's a stepping number.
    for current_number in range(start_number, end_number + 1):
        number_as_string = str(current_number)

        # Single-digit numbers are always stepping numbers by definition.
        if len(number_as_string) <= 1:
            stepping_numbers_result.append(current_number)
            continue

        is_stepping_number = True

        # Check each pair of adjacent digits to see if they differ by exactly 1.
        for digit_index in range(len(number_as_string) - 1):
            first_digit = int(number_as_string[digit_index])
            second_digit = int(number_as_string[digit_index + 1])

            # If any pair of adjacent digits violates the stepping number rule, the number is disqualified.
            if abs(first_digit - second_digit) != 1:
                is_stepping_number = False
                break

        if is_stepping_number:
            stepping_numbers_result.append(current_number)

    return sorted(stepping_numbers_result)

Big(O) Analysis

Time Complexity
O((high - low) * log(high)) – Let high and low be the endpoints of the range. Every integer from low through high is examined once. Turning a number into digits and comparing neighbors takes time proportional to the number of digits, which is O(log(high)). Multiplying that cost by the width of the range gives O((high - low) * log(high)). Sorting the matches is smaller than the scan whenever the range is wide, because stepping numbers are far rarer than ordinary integers, so the bound is dominated by the scan.
Space Complexity
O(k) – Let k be the number of stepping numbers inside the range. Those matches are stored in the result, so the result occupies O(k) memory. The digit text of the number being tested has length O(log(high)), which is smaller than the result whenever the range contains more than a few matches. No other structure grows with the input. The extra space is O(k).

Optimal Solution

Approach

Stepping numbers are grown one digit at a time, starting from the digits one through nine. From any number, the next digit is either one below or one above its last digit, and a number already past the upper bound is not extended. Zero is added only when the lower bound allows it, and the collected numbers are sorted at the end.

Here's how the algorithm would work step-by-step:

  1. If the lower bound is zero, record zero immediately.
  2. Place the digits one through nine into a list that is consumed from the front.
  3. Take the first number off that list, and record it when it lies inside the range.
  4. If that number is already above the upper bound, do not extend it.
  5. Otherwise append the digit one smaller than the last digit when that digit exists and the new number does not exceed the upper bound.
  6. Also append the digit one larger than the last digit under the same bound.
  7. Repeat until the list is empty, then sort and return the recorded numbers.

Code Implementation

def find_stepping_numbers(low_bound, high_bound):
    result_numbers = []
    if low_bound == 0:
        result_numbers.append(0)

    # A queue is used to build stepping numbers digit by digit in a breadth-first manner.
    queue_for_generation = [digit for digit in range(1, 10)]

    while queue_for_generation:
        current_number = queue_for_generation.pop(0)

        if low_bound <= current_number <= high_bound:
            result_numbers.append(current_number)

        # Stop generating longer numbers from the current one if it already exceeds the upper bound.
        if current_number > high_bound:
            continue

        last_digit = current_number % 10

        # Generate the next stepping number by appending a digit that is one less than the last digit.
        if last_digit > 0:
            next_number_option_one = current_number * 10 + (last_digit - 1)
            if next_number_option_one <= high_bound:
                queue_for_generation.append(next_number_option_one)

        # Generate the next stepping number by appending a digit that is one more than the last digit.
        if last_digit < 9:
            next_number_option_two = current_number * 10 + (last_digit + 1)
            if next_number_option_two <= high_bound:
                queue_for_generation.append(next_number_option_two)

    return sorted(result_numbers)

Big(O) Analysis

Time Complexity
O(k^2) – Let k be the number of stepping numbers generated, including the one-digit seeds that fall above the upper bound. Each generated number is removed from the front of a list. Removing the front shifts every later entry, so one removal costs time proportional to the current length of the list. Across k removals those shifts add up to O(k^2). Building a child number and sorting the matches are cheaper than the shifts, so the total time is O(k^2).
Space Complexity
O(k) – Let k be the number of generated stepping numbers. The working list holds the numbers still waiting, and the result holds the numbers inside the range. Both are bounded by k. No other structure grows with the endpoints. The extra space is O(k).

Edge Cases

The range contains one number that is not stepping
How to Handle:
The scan rejects it and the digit builder never records it, so the result is empty.
The lower endpoint is zero
How to Handle:
Zero is recorded immediately, and generation starts from the digits one through nine so zero is not used as a prefix.
Both endpoints are single digits
How to Handle:
Every value in the range is accepted because a single digit has no neighboring pair to violate the rule.
Ten is inside the range and eleven is also inside
How to Handle:
Ten is kept because its digits differ by one, and eleven is rejected because its digits are equal.
A longer candidate would pass the upper bound
How to Handle:
That candidate is not kept and is not used to grow still longer numbers.
0/14 completed