#2801

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Stepping Numbers in Range

Count the stepping numbers in a range using dynamic programming with state transitions between digits.

Problem Statement

Given two positive integers low and high as strings, find how many stepping numbers lie within the inclusive range [low, high].

A stepping number is defined as an integer where the absolute difference between each adjacent digit is exactly 1. For example, 123 and 989 are stepping numbers, but 100 and 431 are not. Your task is to compute the count of these numbers in the specified range, including both bounds.

Examples

Example 1

Input: low = "1", high = "11"

Output: 10

The stepping numbers in the range [1,11] are 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10. There are a total of 10 stepping numbers in the range. Hence, the output is 10.

Example 2

Input: low = "90", high = "101"

Output: 2

The stepping numbers in the range [90,101] are 98 and 101. There are a total of 2 stepping numbers in the range. Hence, the output is 2.

Constraints

1 <= int(low) <= int(high) < 10100
1 <= low.length, high.length <= 100
low and high consist of only digits.
low and high don't have any leading zeros.

Solution Approach

State Transition Dynamic Programming

This approach builds the solution by iterating through digits of a number while maintaining a state for the current digit and previous state, ensuring the next digit has a difference of 1. For each valid transition, the algorithm constructs a stepping number and counts it if it lies within the range.

Counting from 1 to high, then subtracting from 1 to low - 1

By calculating the number of stepping numbers in the range [1, high] and subtracting those found in the range [1, low - 1], we efficiently compute the desired count in [low, high]. This approach leverages the fact that stepping numbers are sequential, making the subtraction method ideal for optimization.

Memoization

Memoization helps optimize the dynamic programming approach by storing intermediate results. This prevents redundant calculations, especially when exploring large ranges, and speeds up the solution by reducing the number of recursive calls.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used for state transitions and the number of digits in the given range. Memoization optimizes the complexity, but it is still affected by the size of the number strings and the range between low and high.

What Interviewers Usually Probe

Look for an understanding of dynamic programming with state transitions.
Evaluate the candidate’s approach to handling large ranges with minimal space complexity.
Ask about optimizations to handle edge cases such as long number strings.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the problem's definition of stepping numbers, leading to incorrect digit transitions.
Failing to account for the exact difference of 1 between adjacent digits in the dynamic programming solution.
Overlooking the time complexity of processing very large numbers as strings without efficient state management.

Follow-up variants

Allow negative stepping numbers.
Explore solutions using iterative methods rather than recursion with memoization.
Test performance with larger ranges and verify optimization strategies.

FAQ

What are stepping numbers?

Stepping numbers are integers where the absolute difference between adjacent digits is exactly 1, such as 101 or 454.

How do I calculate the number of stepping numbers in a range?

To calculate stepping numbers in the range [low, high], count the numbers in the range [1, high] and subtract the count in [1, low - 1].

What is the primary algorithm for this problem?

The primary algorithm uses dynamic programming with state transitions, where each digit is considered in relation to the previous one to determine if a valid stepping number exists.

How does memoization help with the solution?

Memoization stores previously calculated results for digit transitions, reducing redundant computations and improving performance, especially for large input sizes.

What makes this problem hard?

The difficulty arises from managing large input sizes, using dynamic programming efficiently with state transitions, and ensuring that the solution scales well for very large numbers, as the range can go up to 100 digits.

terminal

Solution

Solution 1: Digit DP

We notice that the problem is asking for the number of stepping numbers in the interval $[low, high]$. For such an interval $[l,..r]$ problem, we can usually consider transforming it into finding the answers for $[1, r]$ and $[1, l-1]$, and then subtracting the latter from the former. Moreover, the problem only involves the relationship between different digits, not the specific values, so we can consider using Digit DP to solve it.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def countSteppingNumbers(self, low: str, high: str) -> int:
        @cache
        def dfs(pos: int, pre: int, lead: bool, limit: bool) -> int:
            if pos >= len(num):
                return int(not lead)
            up = int(num[pos]) if limit else 9
            ans = 0
            for i in range(up + 1):
                if i == 0 and lead:
                    ans += dfs(pos + 1, pre, True, limit and i == up)
                elif pre == -1 or abs(i - pre) == 1:
                    ans += dfs(pos + 1, i, False, limit and i == up)
            return ans % mod

        mod = 10**9 + 7
        num = high
        a = dfs(0, -1, True, True)
        dfs.cache_clear()
        num = str(int(low) - 1)
        b = dfs(0, -1, True, True)
        return (a - b) % mod

Continue Practicing

#2767 partition string into minimum beautiful substrings #2851 string transformation #2746 decremental string concatenation