Given two positive integers low and high represented as strings, find the count of stepping numbers in the inclusive range [low, high].
A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly 1.
Return an integer denoting the count of stepping numbers in the inclusive range [low, high].
Since the answer may be very large, return it modulo 109 + 7.
Note: A stepping number should not have a leading zero.
Example 1:
Input: low = "1", high = "11" Output: 10 Explanation: 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 Explanation: 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) < 101001 <= low.length, high.length <= 100low and high consist of only digits.low and high don't have any leading zeros.Problem Overview: Given two numeric strings low and high, count how many integers in this inclusive range are stepping numbers. A stepping number is a number where the absolute difference between every pair of adjacent digits is exactly 1 (e.g., 123 or 321). The challenge is that the range can be extremely large, so iterating through every number is not always feasible.
Approach 1: Brute Force Method (Time: O(N * d), Space: O(1))
The straightforward strategy is to iterate through every number between low and high. Convert each number to a string and check whether every adjacent digit pair differs by exactly 1. This involves a simple scan of the digits using a loop and comparing abs(d[i] - d[i-1]). If the condition holds for all adjacent digits, increment the count. The algorithm is easy to implement and useful for understanding the definition of stepping numbers, but it becomes impractical when the numeric range is large because the iteration cost grows linearly with the size of the range.
Approach 2: Optimized Pair Calculation Using Single Loop (Digit DP) (Time: O(d * 10 * 2), Space: O(d * 10))
A scalable solution uses dynamic programming with digit constraints (digit DP). Instead of enumerating every number, compute how many valid stepping numbers exist up to a given bound. Process the number digit by digit, keeping track of the previous digit and whether the current prefix is already smaller than the bound. From each digit, the next allowed digits are only prev - 1 or prev + 1. Memoization stores intermediate states defined by position, previous digit, and tight-bound state. Run this counting function for high and subtract the count for low - 1. This reduces the search space dramatically and relies heavily on digit-level state transitions using strings and string processing.
Recommended for interviews: Interviewers expect the optimized digit DP approach. The brute force method demonstrates that you understand what defines a stepping number, but it fails on large ranges. The DP solution shows mastery of constrained digit generation, memoization, and range counting—skills commonly tested in hard problems involving numeric strings.
This approach involves examining all possible combinations to find the solution by iterating over each element. While simple, the method may not be efficient for large datasets due to its time complexity.
The function bruteForceSolution computes the sum of all possible pairs in an array using nested loops. This involves iterating through each element and pairing it with all the subsequent elements.
Time Complexity: O(n^2)
Space Complexity: O(1)
This approach improves efficiency by leveraging a mathematical observation or data structure to avoid redundant calculations, significantly reducing time complexity.
This C function computes the sum of all possible integer pairs by calculating the total sum and multiplying each element by the size - 1, effectively counting its contribution to all possible pairs.
Time Complexity: O(n)
Space Complexity: O(1)
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.
We design a function dfs(pos, pre, lead, limit), which represents the number of schemes when we are currently processing the pos-th digit, the previous digit is pre, whether the current number only contains leading zeros is lead, and whether the current number has reached the upper limit is limit. The range of pos is [0, len(num)).
The execution logic of the function dfs(pos, pre, lead, limit) is as follows:
If pos exceeds the length of num, it means that we have processed all the digits. If lead is true at this time, it means that the current number only contains leading zeros and is not a valid number. We can return 0 to indicate that the number of schemes is 0; otherwise, we return 1 to indicate that the number of schemes is 1.
Otherwise, we calculate the upper limit up of the current digit, and then enumerate the digit i in the range [0,..up]:
i=0 and lead is true, it means that the current number only contains leading zeros. We recursively calculate the value of dfs(pos+1,pre, true, limit\ and\ i=up) and add it to the answer.pre is -1, or the absolute difference between i and pre is 1, it means that the current number is a valid stepping number. We recursively calculate the value of dfs(pos+1,i, false, limit\ and\ i=up) and add it to the answer.Finally, we return the answer.
In the main function, we calculate the answers a and b for [1, high] and [1, low-1] respectively. The final answer is a-b. Note the modulo operation of the answer.
The time complexity is O(log M times |\Sigma|^2), and the space complexity is O(log M times |\Sigma|), where M represents the size of the number high, and |\Sigma| represents the digit set.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force Method | Time Complexity: O(n^2) |
| Approach 2: Optimized Pair Calculation Using Single Loop | Time Complexity: O(n) |
| Digit DP | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Method | O(N * d) | O(1) | Small numeric ranges where iterating every number is feasible |
| Optimized Pair Calculation Using Single Loop (Digit DP) | O(d * 10 * 2) | O(d * 10) | Large ranges with big integers where enumeration is impossible |
2801. Count Stepping Numbers in Range | Digit DP Explained (again :D) • codingMohan • 1,905 views views
Watch 8 more video solutions →Practice Count Stepping Numbers in Range with our built-in code editor and test cases.
Practice on FleetCode