How hard is LeetCode 1215. Stepping Numbers?

LeetCode 1215. Stepping Numbers is rated Medium on LeetCode.

What is the time complexity of LeetCode 1215. Stepping Numbers?

The Python solution on this page runs in O(10 \times 2^{\log M}).

What is the space complexity of LeetCode 1215. Stepping Numbers?

The Python solution on this page uses O(2^{\log M}), where M is the number of digits in high auxiliary space.

What topics does LeetCode 1215. Stepping Numbers cover?

LeetCode 1215. Stepping Numbers is tagged Breadth-First Search, Math and Backtracking on LeetCode.

Is LeetCode 1215. Stepping Numbers a premium problem?

Yes. LeetCode 1215. Stepping Numbers is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Stepping Numbers — LeetCode 1215 Python Solution

MediumLeetCode PremiumBreadth-First SearchMathBacktracking

Problem: #1215
Pattern: Backtracking
Reading time: 3 min
Source: leetcode.com

The problem

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.

Example

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

Python solution

Python

class Solution:
    def countSteppingNumbers(self, low: int, high: int) -> List[int]:
        ans = []
        if low == 0:
            ans.append(0)
        q = deque(range(1, 10))
        while q:
            v = q.popleft()
            if v > high:
                break
            if v >= low:
                ans.append(v)
            x = v % 10
            if x:
                q.append(v * 10 + x - 1)
            if x < 9:
                q.append(v * 10 + x + 1)
        return ans

Complexity

Measure	Complexity
Time	O(10 \times 2^{\log M})
Space	O(2^{\log M}), where M is the number of digits in high auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1215. Stepping Numbers is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1215. Stepping Numbers?: LeetCode 1215. Stepping Numbers is rated Medium on LeetCode.
What is the time complexity of LeetCode 1215. Stepping Numbers?: The Python solution on this page runs in O(10 \times 2^{\log M}).
What is the space complexity of LeetCode 1215. Stepping Numbers?: The Python solution on this page uses O(2^{\log M}), where M is the number of digits in high auxiliary space.
What topics does LeetCode 1215. Stepping Numbers cover?: LeetCode 1215. Stepping Numbers is tagged Breadth-First Search, Math and Backtracking on LeetCode.
Is LeetCode 1215. Stepping Numbers a premium problem?: Yes. LeetCode 1215. Stepping Numbers is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.