Sequential Digits solution and explanation
Google
9 more videos on this problem
Sequential Digits - Leetcode 1291 - PythonNeetCodeIO · 15:02 · 16K views
Sequential Digits | 2 Approaches | Leetcode 1291 | codestorywithMIKcodestorywithMIK · 21:21 · 10K views
Sequential Digits | LeetCode 1291 | C++, Java, PythonKnowledge Center · 14:37 · 6K views
1291. Sequential Digits | Sliding Window | Not a Digit DP | Time & Space - O(1)Aryan Mittal · 9:23 · 3K views
1291. Sequential Digits Leetcode BFS Solution example and Code C++Code with Alisha · 8:35 · 1K views
Sequential Digits LeetCode Problem 1291 | leetcode solutionEasyLeetcode · 12:09 · 575 views
1291. Sequential Digits | Leetcode Daily - PythonLeetcode Daily · 4:24 · 496 views
Sequential Digits | LeetCode 1291 - Pythonimpoldev · 5:00 · 252 views
Sequential Digits - LeetCode 1291 September ChallengeSM TechWorld · 9:43 · 162 views
1291 - Sequential Digits - LeetCode (Medium) | Maths | BFS Level-Order | Optimal SolutionThe Lame Coder · 12:14 · 100 views
The problem
An integer has sequential digits if and only if each digit in the number is one more than the previous digit.
Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.
Example 1:
Input: low = 100, high = 300 Output: [123,234]
Example 2:
Input: low = 1000, high = 13000 Output: [1234,2345,3456,4567,5678,6789,12345]
Constraints:
10 <= low <= high <= 10^9
Approach overview
Problem Overview: You are given two integers low and high. The task is to return every number within this range whose digits are sequentially increasing, such as 123, 456, or 6789. Each digit must be exactly one greater than the previous digit.
Approach 1: Generate All Sequential Digits and Filter (O(1) time, O(1) space)
The simplest strategy is to pre-generate every possible sequential digit number and then filter the ones that fall inside the range [low, high]. Since digits can only go from 1 to 9, there are fewer than 40 valid sequential numbers in total (e.g., 12, 23, 123, 2345). Store them in a list and iterate through it, adding numbers that satisfy the range condition. The search space is constant because digit length is capped at 9. This approach relies on simple enumeration and works well when you want the most straightforward implementation.
Approach 2: Sliding Window Approach (O(1) time, O(1) space)
Construct sequential numbers using a sliding window over the string "123456789". For each possible window length, slide across the string and convert the substring into an integer. For example, window size 3 generates 123, 234, 345, and so on. Each candidate number is checked against the range [low, high]. This technique avoids hardcoding the numbers and systematically builds them using the sliding window pattern.
Approach 3: Generating Sequential Digits Using Sliding Window (O(1) time, O(1) space)
This variation dynamically builds numbers while iterating over starting digits. Begin with a digit d, then repeatedly append the next digit d+1, d+2, etc., forming numbers like 12, 123, 1234. Stop when the next digit would exceed 9. Each generated number is checked against the bounds. The method is efficient because generation stops early once values exceed high. It is still constant time overall since the number of generated values is bounded.
Approach 4: Iterative Generation with Breadth-First Traversal (O(1) time, O(1) space)
Treat sequential numbers as nodes in a conceptual tree and generate them using a queue. Start with digits 1 through 9. For each number removed from the queue, append the next digit (lastDigit + 1) to create a new sequential number. Push the new number back into the queue if the last digit is less than 9. If the number lies within [low, high], add it to the result. This technique mirrors breadth-first search and naturally generates numbers in increasing order.
Recommended for interviews: The sliding window or BFS generation approach is typically expected. Both show that you recognize the strict digit pattern and avoid brute force checking of every number in the range. Explaining the enumeration first demonstrates understanding, while generating numbers directly shows stronger algorithmic reasoning.
Approach 1: Approach 1: Generate All Sequential Digits and Filter
This approach involves generating all possible sequential digit numbers and then filtering them to find the ones within the given range [low, high].
Sequential digit numbers can be viewed as forming an arithmetic sequence where the difference between consecutive digits is one. Starting with single-digit numbers, we generate all possible sequential numbers by adding the next digit until the number exceeds the upper limit. By maintaining a list of such numbers, we can iterate over this list and select numbers that fall within the specified range.
def sequentialDigits(low, high):
result = []
for start in range(1, 9):
num = next_num = start
while next_num <= 9:
if low <= num <= high:
result.append(num)
next_num += 1
num = num * 10 + next_num
return sorted(result)This Python function initializes a list result to store potential sequential digit numbers. By iterating the start value from 1 through 9, we form an initial number num and apply a while loop to generate sequential numbers by appending the next digit. For each valid num, we check if it lies within the range [low, high] and add it to the result.
Time Complexity: O(1) - Determined by the fixed number of sequential digits.
Space Complexity: O(1) - Space used is constant due to the limited number of sequential digit numbers.
Approach 2: Approach 2: Sliding Window Approach
Another approach utilizes a sliding window to generate possible sequences. By sliding over a pre-defined string of digits from '1' to '9', we construct numbers by considering substrings of increasing length. If digits form a number larger than high, we stop further expansion of that sequence.
def sequentialDigits(low, high):
result = []
sequential_str = '123456789'
n = len(sequential_str)
for length in range(2, n+1):
for start in range(n-length+1):
num = int(sequential_str[start:start+length])
if low <= num <= high:
result.append(num)
return sorted(result)This solution uses a predefined string '123456789' to simulate a sliding window effect. By varying the window length from 2 to 9, it generates numbers by converting substrings to integers. Valid numbers are collected in the list result.
Time Complexity: O(1) - Since there are maximum 45 possible numbers derived from the digit string of length 9.
Space Complexity: O(1) - Limited and fixed space occupation.
Approach 3: Generating Sequential Digits Using Sliding Window
This approach involves generating all possible sequential digits by using a string representation of numbers and sliding over them with different lengths. By maintaining a starting digit, we can build numbers by appending increasing numbers to it.
def sequentialDigits(low, high):
results = []
nums = "123456789"
for length in range(len(str(low)), len(str(high)) + 1):
for start in range(0, 10 - length):
num = int(nums[start:start + length])
if low <= num <= high:
results.append(num)
return results#include <vector>
#include <string>
using namespace std;
vector<int> sequentialDigits(int low, int high) {
vector<int> results;
string nums = "123456789";
for (int length = to_string(low).length(); length <= to_string(high).length(); ++length) {
for (int start = 0; start <= 9 - length; ++start) {
int num = stoi(nums.substr(start, length));
if (num >= low && num <= high) {
results.push_back(num);
}
}
}
return results;
}The above function iterates over possible lengths of sequential numbers fitting in the range dictated by the number of digits in low and high. It slides over the sequential string "123456789" and creates numbers of a specific length. If a generated number is within the range, it's appended to a result list.
Time Complexity: O(1) relative to the constant set of sequential digits.
Space Complexity: O(1) for results storage, limited by specific constraints.
Approach 4: Iterative Generation with Breadth-First Traversal
This approach uses an iterative method to generate numbers by extending in a breadth-first manner. Starting from each single-digit as a potential number, extend by appending one higher digit until the maximum range limit is reached.
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;
public List<Integer> sequentialDigits(int low, int high) {
List<Integer> results = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i < 10; ++i) queue.add(i);
while (!queue.isEmpty()) {
int number = queue.poll();
if (number >= low && number <= high) results.add(number);
int lastDigit = number % 10;
if (lastDigit < 9) {
int next = number * 10 + lastDigit + 1;
if (next <= high) queue.add(next);
}
}
return results;
}function sequentialDigits(low, high) {
let results = [];
let queue = [];
for (let i = 1; i <= 9; ++i) queue.push(i);
while (queue.length) {
let number = queue.shift();
if (number >= low && number <= high) results.push(number);
let lastDigit = number % 10;
if (lastDigit < 9) {
let next = number * 10 + (lastDigit + 1);
if (next <= high) queue.push(next);
}
}
return results;
}This Java solution utilizes a queue to explore the current number by appending a higher digit, similar to how BFS explores levels of a graph. The digits are expanded sequentially until the high constraint is breached.
Time Complexity: O(1) for the bounded number of operations as digits are limited.
Space Complexity: O(1) with respect to storing valid outputs within range constraints.
Approach 5: Default Approach
function sequentialDigits(low: number, high: number): number[] {
const ans: number[] = [];
for (let i = 1; i < 9; ++i) {
let x = i;
for (let j = i + 1; j < 10; ++j) {
x = x * 10 + j;
if (x >= low && x <= high) {
ans.push(x);
}
}
}
ans.sort((a, b) => a - b);
return ans;
}func sequentialDigits(low int, high int) (ans []int) {
for i := 1; i < 9; i++ {
x := i
for j := i + 1; j < 10; j++ {
x = x*10 + j
if low <= x && x <= high {
ans = append(ans, x)
}
}
}
sort.Ints(ans)
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Generate All Sequential Digits and Filter | Time Complexity: O(1) - Determined by the fixed number of sequential digits. |
| Approach 2: Sliding Window Approach | Time Complexity: O(1) - Since there are maximum 45 possible numbers derived from the digit string of length 9. |
| Generating Sequential Digits Using Sliding Window | Time Complexity: O(1) relative to the constant set of sequential digits. |
| Iterative Generation with Breadth-First Traversal | Time Complexity: O(1) for the bounded number of operations as digits are limited. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Generate All Sequential Digits and Filter | O(1) | O(1) | Simplest implementation when you precompute all possible sequential numbers. |
| Sliding Window on "123456789" | O(1) | O(1) | Clean pattern-based generation without storing predefined values. |
| Dynamic Sequential Generation | O(1) | O(1) | When building numbers incrementally from each starting digit. |
| Breadth-First Traversal (Queue) | O(1) | O(1) | Useful when demonstrating BFS-style generation and producing numbers in sorted order. |
Frequently asked questions
Is Sequential Digits easy or hard?
Sequential Digits is rated Medium on LeetCode but is often considered an easier medium problem. The main challenge is recognizing the digit pattern and generating numbers efficiently instead of brute-forcing the entire range.
How to solve Sequential Digits in O(1)?
Generate candidate numbers using a sliding window over the string "123456789" or build them incrementally starting from digits 1–9. Each generated number is checked against the range [low, high]. Because the total candidates are bounded, the algorithm effectively runs in constant time.
What is the best approach for Sequential Digits?
The sliding window or BFS generation approach is usually considered the best. Instead of checking every number in the range, you directly generate valid sequential numbers such as 123 or 4567. Since there are fewer than 40 possible sequential numbers overall, the algorithm runs in constant time and is very efficient.
Is Sequential Digits asked at Google/Amazon/Meta?
Sequential Digits is a common enumeration-style problem that has appeared in interview prep lists and coding assessments. Variations of pattern-based number generation and digit manipulation are frequently asked by companies like Amazon and Google in coding interviews.
What data structure is used in Sequential Digits?
Most solutions rely on simple arrays or lists to store generated numbers. Some implementations use a queue to perform breadth-first generation of sequential numbers. The problem focuses more on enumeration logic than complex data structures.
What is the time complexity of Sequential Digits?
The time complexity is O(1). The number of possible sequential digit values is fixed because digits range only from 1 to 9. Even if you generate all possibilities, the total count is small and independent of the input size.
Sequential Digits Python or Java solution approach?
In Python or Java, the most common solution uses a sliding window over the string "123456789" to generate substrings and convert them to integers. Another approach uses a queue to build numbers like 1 → 12 → 123. Both implementations run in constant time with minimal memory.