Skip to main content
Talentd

Count Stepping Numbers in Range - Solution & Explanation

HardStringDynamic Programming23 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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) < 10100
  • 1 <= low.length, high.length <= 100
  • low and high consist of only digits.
  • low and high don't have any leading zeros.

Approach Overview

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 1: Approach 1: Brute Force Method

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Approach 2: Optimized Pair Calculation Using Single Loop

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: 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.

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]:

  • If 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.
  • Otherwise, if 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:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Brute Force Method

Time Complexity: O(n^2)
Space Complexity: O(1)

Approach 2: Optimized Pair Calculation Using Single Loop

Time Complexity: O(n)
Space Complexity: O(1)

Digit DP—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force MethodO(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

Video Solution

2801. Count Stepping Numbers in Range | Digit DP Explained (again :D) • codingMohan • 1,934 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Count Stepping Numbers in Range easy or hard?
Count Stepping Numbers in Range is classified as a Hard problem on LeetCode. The difficulty comes from handling extremely large ranges and applying digit dynamic programming correctly. Understanding tight constraints, memoization states, and digit transitions is essential to solving it efficiently.
Count Stepping Numbers in Range Python/Java solution
Python and Java solutions typically implement a recursive or iterative digit DP with memoization. The function processes digits of the bound string, tracks the previous digit, and enforces the stepping constraint. The final answer is computed by evaluating the DP for high and subtracting the result for low minus one.
How to solve Count Stepping Numbers in Range in O(n)?
Use a digit DP strategy that builds numbers digit by digit while enforcing the stepping condition. Track the previous digit and only transition to prev−1 or prev+1. Memoize states based on index, previous digit, and tight flag to avoid recomputation. This converts an exponential search into a linear scan over digit states.
What is the best approach for Count Stepping Numbers in Range?
Digit Dynamic Programming (Digit DP) is the most efficient approach. Instead of checking every number in the range, the algorithm counts valid stepping numbers up to a bound using digit-by-digit transitions. The final answer is computed as count(high) minus count(low − 1). This reduces the complexity to roughly O(d * 10) where d is the number of digits.
Is Count Stepping Numbers in Range asked at Google/Amazon/Meta?
Problems based on digit DP and constrained number generation appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of stepping numbers, counting valid integers in ranges, and digit constraint problems are common in hard-level interview rounds.
What data structure is used in Count Stepping Numbers in Range?
The core technique uses dynamic programming with memoization. States are typically stored in a DP table or hash map keyed by digit index, previous digit, and tight constraint. Strings are also used to process the numeric bounds safely when the values exceed normal integer limits.
What is the time complexity of Count Stepping Numbers in Range?
The optimized digit DP solution runs in O(d * 10 * 2) time where d is the number of digits in the bound. Each state represents a digit position, previous digit, and tight constraint. The brute force approach is much slower at O(N * d) because it checks every number in the range.

Ready to solve this problem?

Practice Count Stepping Numbers in Range with our built-in code editor and test cases.

Practice on FleetCode
Previous

Stepping Numbers