1291. Sequential Digits
Problem Description
We are provided with two integers, low
and high
, which define a range. The task is to find all integers within this range that have sequential digits. An integer is said to have sequential digits if each digit in the number is exactly one more than the previous digit. For example, 123 has sequential digits, but 132 does not. The final list of found integers should be returned in increasing order.
Intuition
To tackle the problem of finding integers with sequential digits within a given range, we need to generate these numbers rather than checking every number in the range. Starting with the smallest digit '1', we can iteratively add the next sequential digit by multiplying the current number by 10 (to shift the digits to the left) and then adding the next digit. For instance, start with 1
, then 12
, 123
, and so on, till we reach a number greater than high
. We repeat this for starting digits 1 through 9.
The intuitive steps in the solution approach are:
- Loop through all possible starting digits (
1
to9
). - In a nested loop, add the next sequential digit to the current number and check if it falls within the range [low, high]. If it does, add it to our answers list.
- Repeat this process until the number exceeds
high
or we reach the digit '9'. - Since the process generates the sequential digit numbers in increasing order, but not necessary starting with the lowest in the range, a final sort of the answer list ensures that the output is correctly ordered.
The provided solution follows this methodology, using two nested loops, to generate the numbers with sequential digits and collect the ones that lie within the range.
Solution Approach
The algorithm takes a direct approach by constructing numbers with sequential digits and then checking if they lie within the provided range.
Here’s the implementation process:
-
Initialization: We start by creating an empty list
ans
, which will be used to store all the numbers that match our condition and are within the[low, high]
range. -
Outer Loop: This loop starts with the digit
1
and goes up to9
, representing the starting digit of our sequential numbers. -
Inner Loop: For each digit
i
started by the outer loop, we initialize an integerx
withi
. This inner loop adds the next digit (j
) toi
, so thatx
becomes a number with sequential digits. For example, ifi
is1
, thenx
will be transformed through the sequence:1 -> 12 -> 123 -> ...
and so on. The loop continues untilj
reaches10
, as9
is the last digit we can add. -
Number Construction and Range Checking: In each iteration of the inner loop,
x
is updated asx = x * 10 + j
; this adds the next digit at the end ofx
. The newly formed number is then checked to ascertain if it's within the[low, high]
range. Ifx
falls within the range, the number is added to theans
list. -
Loop Termination: The loop terminates in one of two cases. The first is when
x
exceedshigh
, since all subsequent numbers that could be formed by adding more sequential digits will also be out of the range. The second case is when the last digit (which is9
) has been added to the sequence, and no further sequential digit can follow. -
Returning the Sorted List: Although the algorithm itself generates these numbers in a sequential order, they are added to the list in an order based on the starting digit. Therefore, a final sort is applied before returning the list to ensure that numbers are sorted according to their value.
The utilized data structures are simple: an int
variable to keep track of the currently formed number with sequential digits, and a list to store and return the eligible numbers.
The patterns involved in this algorithm include:
- Constructive algorithms: Rather than checking all numbers within a range, we constructively build the eligible numbers.
- Brute force with a twist: Instead of brute force checking all numbers, we only consider plausible candidates.
- Range-based iteration: Both loops are based on clearly defined ranges (1 to 9 and the dynamically generated
x
within[low, high]
).
Here's a brief code snippet for reference:
1class Solution:
2 def sequentialDigits(self, low: int, high: int) -> List[int]:
3 ans = []
4 for i in range(1, 9):
5 x = i
6 for j in range(i + 1, 10):
7 x = x * 10 + j
8 if low <= x <= high:
9 ans.append(x)
10 return sorted(ans)
As you can see, the code closely follows the outlined algorithm, utilizing two nested for-loops to build and check the sequential digit numbers.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach based on the problem of finding integers with sequential digits within a given range. Say our range is defined by the integers low = 100
and high = 300
.
Following the steps of the solution approach:
-
Initialization: Start with an empty list
ans
, ready to store numbers with sequential digits within our range[100, 300]
. -
Outer Loop: We consider starting digits from
1
through9
. -
Inner Loop: Starting with the initial digit
i
. For example, wheni
is1
, we will construct numbers beginning with1
. -
Number Construction and Range Checking:
- With
i = 1
, we constructx = 1
. - Increment the next digit by one and add it to
x
, so nowx = 12
(because1 * 10 + 2 = 12
). - Continue adding the next digit:
x = 123
. This number exceeds ourlow
but is still less thanhigh
, so we add123
to ourans
list. - When we add
4
,x = 1234
, which is now greater thanhigh
. We stop here for this sequence and do not add1234
toans
.
- With
-
Loop Termination: This inner loop stops for this particular starting digit since
x
has exceededhigh
, and we won't attempt to add more sequential digits. -
Proceed with Other Starting Digits: Loop with the next starting digit,
i = 2
.- Repeat the process with
x = 2
, thenx = 23
. - We find
x = 234
exceeds our range, so we don't add234
toans
and stop the inner loop for the starting digit2
.
- Repeat the process with
This process continues for all starting digits from 1
through 9
. However, given our -
high, we won't find any valid numbers with sequential digits starting with
3or greater within the range
[100, 300]`.
- Returning Sorted List: Once the loops have terminated, we sort the list
ans
. In this case, the only number we would have added to the list is123
, which is already in sorted order, but if there were more numbers, sorting would ensure they are returned in increasing order.
Thus, our final list ans
is [123]
, and it would be returned as the solution.
Quick Recap:
- Initialized with
ans = []
. - Our loops constructed and checked sequential digits from numbers starting with
1
, then2
, then3
, and so forth. - We found
123
as a valid number and added it toans
. - The loops stopped when the constructed number exceeded
high
for each starting digit. - We would return a sorted
ans
, which in this case is simply[123]
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def sequentialDigits(self, low: int, high: int) -> List[int]:
5 # Initialize an empty list to store the sequential digits
6 sequential_numbers = []
7
8 # Iterate over digits from 1 to 8 (since 9 cannot start a sequence)
9 for start_digit in range(1, 9):
10 # Initialize the current number with the starting digit
11 current_number = start_digit
12
13 # Build the sequence by appending digits to the right
14 for next_digit in range(start_digit + 1, 10): # Only digits 1-9 are valid
15 # Create the next number in the sequence by shifting left and adding the next_digit
16 current_number = current_number * 10 + next_digit
17
18 # Check if the current number is within the given range [low, high]
19 if low <= current_number <= high:
20 # If it is, append it to the list of sequential numbers
21 sequential_numbers.append(current_number)
22
23 # Return the sorted list of sequential numbers
24 return sorted(sequential_numbers)
25
26# Example usage:
27# solution = Solution()
28# print(solution.sequentialDigits(100, 300)) # Output: [123, 234]
29
1import java.util.List;
2import java.util.ArrayList;
3import java.util.Collections;
4
5class Solution {
6 public List<Integer> sequentialDigits(int low, int high) {
7 // Initialize the answer list to hold sequential digit numbers
8 List<Integer> sequentialNumbers = new ArrayList<>();
9
10 // Start generating numbers from each digit 1 through 8
11 // A sequential digit number cannot start with 9 as it would not have a consecutive next digit
12 for (int startDigit = 1; startDigit < 9; ++startDigit) {
13 // Initialize the sequential number with the current starting digit
14 int sequentialNum = startDigit;
15
16 // Append the next digit to the sequential number, starting from startDigit + 1
17 for (int nextDigit = startDigit + 1; nextDigit < 10; ++nextDigit) {
18 // Append the next digit to the current sequential number
19 sequentialNum = sequentialNum * 10 + nextDigit;
20
21 // Check if the newly formed sequential number is within the range [low, high]
22 if (sequentialNum >= low && sequentialNum <= high) {
23 // If it is within the range, add it to the answer list
24 sequentialNumbers.add(sequentialNum);
25 }
26 }
27 }
28
29 // Sort the list of sequential numbers
30 Collections.sort(sequentialNumbers);
31
32 // Return the list containing all valid sequential digit numbers in the range
33 return sequentialNumbers;
34 }
35}
36
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Function to find all the unique numbers that consist of sequential digits
7 // and are within the range [low, high] inclusive.
8 vector<int> sequentialDigits(int low, int high) {
9 vector<int> sequential_numbers; // Stores the resulting sequential numbers
10 // Loop to start forming sequential digits from each number 1 through 8.
11 for (int start_digit = 1; start_digit < 9; ++start_digit) {
12 int num = start_digit; // Initialize the current number with the start digit.
13 // Add digits sequentially after the start digit to form a number.
14 for (int next_digit = start_digit + 1; next_digit < 10; ++next_digit) {
15 num = num * 10 + next_digit; // Append the next digit at the unit place.
16 // Check if the number formed is within the range.
17 if (num >= low && num <= high) {
18 sequential_numbers.push_back(num); // Add it to our answer if it's within the range.
19 }
20 }
21 }
22 // Sort the vector containing all the qualifying numbers in ascending order.
23 sort(sequential_numbers.begin(), sequential_numbers.end());
24 // Return the vector of sequential numbers within the given range.
25 return sequential_numbers;
26 }
27};
28
1// Function to find all the sequential digit numbers within the range [low, high].
2function sequentialDigits(low: number, high: number): number[] {
3 // Initialize an empty array to hold the result.
4 let result: number[] = [];
5
6 // Outer loop to start the sequence with numbers from 1 to 8.
7 for (let startDigit = 1; startDigit < 9; ++startDigit) {
8 // Initialize the first number of the sequence with the starting digit.
9 let num = startDigit;
10
11 // Inner loop to build the sequential digit numbers by appending digits.
12 for (let nextDigit = startDigit + 1; nextDigit < 10; ++nextDigit) {
13 // Create the new sequential number by shifting the current
14 // number by one place to the left and adding the next digit.
15 num = num * 10 + nextDigit;
16
17 // Check if the newly formed number is within the given range.
18 if (num >= low && num <= high) {
19 // If the number is within the range, add it to the result array.
20 result.push(num);
21 }
22 }
23 }
24
25 // Sort the result array in ascending order before returning.
26 result.sort((a, b) => a - b);
27 return result;
28}
29
Time and Space Complexity
The given Python code generates sequential digits between a low and high value by constructing such numbers starting from each digit between 1 and 9. Here is an analysis of its time and space complexity:
Time Complexity:
The time complexity of the code can be evaluated by considering the two nested loops. The outer loop runs for a constant number of times (8 times to be precise, as it starts from 1 and goes up to 8). The inner loop depends on the value of i
from the outer loop and can iteratively execute at most 9 times (when i=1
). However, not all iterations will be full, as it breaks off once it exceeds high
. But in the worst-case scenario, if low
is 1 and high
is the maximum possible value within the constraints, each loop can be considered to run O(1)
times as the number of iterations does not depend on the input values 'low' and 'high'.
With each iteration of the inner loop, we're performing O(1)
operations (arithmetic and a conditional check). Therefore, the time complexity is O(1)
.
Space Complexity:
The space complexity is dependent on the number of valid sequential digit numbers we can have in the predefined range. The ans
list contains these numbers and is returned as the output. In the worst case, this could be all 'sequential digit' numbers from one to nine digits long. However, since the count of such numbers is limited (there are only 45 such numbers in total: 9 one-digit, 8 two-digit, ..., 1 nine-digit), the space needed to store them does not depend on the value of low
or high
. Therefore, the space complexity is also O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.