LeetCode 1215 - Stepping Numbers

The problem is asking us to find all integers within a given range [low, high] that are stepping numbers. A stepping number is defined as a number in which the absolute difference between every pair of adjacent digits is exactly 1.

leetcodemediummathbacktrackingbreadth-first-search

LeetCode Problem 1215

Difficulty: 🟡 Medium
Topics: Math, Backtracking, Breadth-First Search

Solution

Problem Understanding

The problem is asking us to find all integers within a given range [low, high] that are stepping numbers. A stepping number is defined as a number in which the absolute difference between every pair of adjacent digits is exactly 1. For instance, 321 is a stepping number because |3-2| = 1 and |2-1| = 1, while 421 is not since |4-2| = 2.

The input consists of two integers, low and high, which define the inclusive range to search. The output should be a sorted list of all stepping numbers within this range.

The constraints specify that 0 <= low <= high <= 2 * 10^9. This upper bound is quite large, so a naive approach that checks every integer individually would be computationally expensive. It is crucial to consider an algorithm that generates only valid candidates rather than iterating through all numbers.

Important edge cases include ranges that start or end at 0, single-digit ranges, ranges that include very large numbers near 2 * 10^9, and numbers that could overflow intermediate calculations if we are not careful.

Approaches

The brute-force approach would iterate through every number from low to high and check whether it is a stepping number. For each number, we would convert it to its digits and verify that the difference between adjacent digits is 1. While this method is correct, its time complexity is O(high - low), which is infeasible for the upper bound 2 * 10^9.

A better approach leverages the observation that a stepping number can be constructed digit by digit. Starting from a single-digit number, we can append the next digit by either adding or subtracting 1 from the last digit. This process is naturally suited to Breadth-First Search (BFS) or Depth-First Search (DFS). Using BFS ensures numbers are generated in increasing order, simplifying the final sorting step.

Approach Time Complexity Space Complexity Notes
Brute Force O(high - low) O(1) Iterates through all numbers, checking each for the stepping property. Too slow for large ranges.
BFS / Constructive O(N) O(N) Generates only valid stepping numbers using BFS from digits 0-9. Efficient and naturally ordered.

Algorithm Walkthrough

  1. Initialize a queue with digits 1 through 9 (and optionally 0 if low is 0). Each digit represents the start of a potential stepping number.
  2. While the queue is not empty, pop a number from the front.
  3. If the number is within the range [low, high], add it to the result list.
  4. If the number is 0 or exceeds high, skip further processing for this number.
  5. Extract the last digit of the current number.
  6. Generate new stepping numbers by appending last_digit + 1 and last_digit - 1, ensuring that these digits are within 0 to 9.
  7. Push the newly generated numbers into the queue.
  8. Continue this process until all possible stepping numbers within the range are explored.
  9. Return the list of collected stepping numbers, which is naturally sorted due to BFS traversal.

Why it works: Each number in the queue is guaranteed to be a stepping number because it is constructed by following the rule that each new digit differs by exactly 1 from the previous digit. BFS ensures that numbers are generated in increasing order, so no post-processing sort is needed.

Python Solution

from typing import List
from collections import deque

class Solution:
    def countSteppingNumbers(self, low: int, high: int) -> List[int]:
        if low > high:
            return []

        result = []
        queue = deque(range(10))  # Start with digits 0-9

        while queue:
            num = queue.popleft()
            if low <= num <= high:
                result.append(num)
            if num == 0 or num > high:
                continue

            last_digit = num % 10
            if last_digit > 0:
                next_num = num * 10 + (last_digit - 1)
                if next_num <= high:
                    queue.append(next_num)
            if last_digit < 9:
                next_num = num * 10 + (last_digit + 1)
                if next_num <= high:
                    queue.append(next_num)

        return sorted(result)

Explanation: We initialize a queue with digits 0-9. For each number, we check if it is in range and add it to the result. Then we generate valid next stepping numbers by appending digits differing by 1 from the last digit. BFS guarantees the numbers are generated in ascending order, and sorted(result) ensures the final list is ordered.

Go Solution

package main

func countSteppingNumbers(low int, high int) []int {
    if low > high {
        return []int{}
    }

    result := []int{}
    queue := []int{0,1,2,3,4,5,6,7,8,9}

    for len(queue) > 0 {
        num := queue[0]
        queue = queue[1:]

        if num >= low && num <= high {
            result = append(result, num)
        }
        if num == 0 || num > high {
            continue
        }

        lastDigit := num % 10
        if lastDigit > 0 {
            nextNum := num*10 + (lastDigit - 1)
            if nextNum <= high {
                queue = append(queue, nextNum)
            }
        }
        if lastDigit < 9 {
            nextNum := num*10 + (lastDigit + 1)
            if nextNum <= high {
                queue = append(queue, nextNum)
            }
        }
    }

    // Sorting the result since BFS may not preserve strict order due to multiple branches
    sort.Ints(result)
    return result
}

Go Notes: We use a slice to implement the queue and append new numbers to it. Because Go does not provide a built-in deque, we manually remove elements from the front. The final result is sorted using sort.Ints to ensure ascending order.

Worked Examples

Example 1: low = 0, high = 21

Initial queue: [0,1,2,3,4,5,6,7,8,9]

Stepwise BFS:

Step Queue Popped num Result Notes
1 0-9 0 [0] last_digit=0, next 1 appended (but 01 > 21 ignored)
2 1-9 1 [0,1] last_digit=1, append 0,2 → queue
3 ... ... ... Continue BFS until all ≤21 added

Final result: [0,1,2,3,4,5,6,7,8,9,10,12,21]

Example 2: low = 10, high = 15

Queue starts [0,1,2,...,9]

Popping 1 generates 10 and 12, both in range. Others are skipped.

Result: [10,12]

Complexity Analysis

Measure Complexity Explanation
Time O(N) BFS generates only valid stepping numbers within range, each processed once.
Space O(N) Queue and result list store all stepping numbers up to high.

The complexity is acceptable because we avoid iterating through all numbers up to high, instead constructing only valid stepping numbers.

Test Cases

# test cases
sol = Solution()
assert sol.countSteppingNumbers(0, 21) == [0,1,2,3,4,5,6,7,8,9,10,12,21]  # example 1
assert sol.countSteppingNumbers(10, 15) == [10,12]  # example 2
assert sol.countSteppingNumbers(0, 0) == [0]  # boundary single number
assert sol.countSteppingNumbers(1, 1) == [1]  # single-digit range
assert sol.countSteppingNumbers(100, 1000)  # range with three-digit numbers
assert sol.countSteppingNumbers(2000000000, 2000000000) == []  # large number outside stepping numbers
assert sol.countSteppingNumbers(0, 9) == [0,1,2,3,4,5,6,7,8,9]  # only single-digit numbers
Test Why
0,21 validates basic multi-digit BFS generation
10,15 small range with skipped numbers
0,0 minimal edge case including 0
1,1 single-digit range
100,1000 tests three-digit stepping numbers
2000000000,2000000000 tests large number edge case
0,9 single-digit range including zero

Edge Cases

The first important edge case is when low = 0. Zero is a stepping number but cannot have any preceding digits,