Watch 9 video solutions for Count Stepping Numbers in Range, a hard level problem involving String, Dynamic Programming. This walkthrough by codingMohan has 1,905 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |