1291. Sequential Digits

MediumEnumeration
Leetcode Link

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 to 9).
  • 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:

  1. 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.

  2. Outer Loop: This loop starts with the digit 1 and goes up to 9, representing the starting digit of our sequential numbers.

  3. Inner Loop: For each digit i started by the outer loop, we initialize an integer x with i. This inner loop adds the next digit (j) to i, so that x becomes a number with sequential digits. For example, if i is 1, then x will be transformed through the sequence: 1 -> 12 -> 123 -> ... and so on. The loop continues until j reaches 10, as 9 is the last digit we can add.

  4. Number Construction and Range Checking: In each iteration of the inner loop, x is updated as x = x * 10 + j; this adds the next digit at the end of x. The newly formed number is then checked to ascertain if it's within the [low, high] range. If x falls within the range, the number is added to the ans list.

  5. Loop Termination: The loop terminates in one of two cases. The first is when x exceeds high, 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 is 9) has been added to the sequence, and no further sequential digit can follow.

  6. 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 Evaluator

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

  1. Initialization: Start with an empty list ans, ready to store numbers with sequential digits within our range [100, 300].

  2. Outer Loop: We consider starting digits from 1 through 9.

  3. Inner Loop: Starting with the initial digit i. For example, when i is 1, we will construct numbers beginning with 1.

  4. Number Construction and Range Checking:

    • With i = 1, we construct x = 1.
    • Increment the next digit by one and add it to x, so now x = 12 (because 1 * 10 + 2 = 12).
    • Continue adding the next digit: x = 123. This number exceeds our low but is still less than high, so we add 123 to our ans list.
    • When we add 4, x = 1234, which is now greater than high. We stop here for this sequence and do not add 1234 to ans.
  5. Loop Termination: This inner loop stops for this particular starting digit since x has exceeded high, and we won't attempt to add more sequential digits.

  6. Proceed with Other Starting Digits: Loop with the next starting digit, i = 2.

    • Repeat the process with x = 2, then x = 23.
    • We find x = 234 exceeds our range, so we don't add 234 to ans and stop the inner loop for the starting digit 2.

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]`.

  1. 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 is 123, 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, then 2, then 3, and so forth.
  • We found 123 as a valid number and added it to ans.
  • 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following shows the order of node visit in a Breadth-first Search?


Recommended Readings

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.