Jobs

Interviews

Discussions

Sequential Digits

Medium

Asked by:

More companies

36 views

Topics:

Arrays

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

Try coding it in LeetCode

Sequential Digits

Medium

Asked by:

36 views

Topics:

Arrays

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of `low` and `high`? Are they positive integers only?
What should I return if there are no sequential digit numbers within the given range?
Are the input `low` and `high` inclusive, meaning I should consider numbers equal to `low` and `high` as potential sequential digit numbers?
Can `low` be greater than `high`? If so, what should the output be?
Is the range between `low` and `high` expected to be small, or could it potentially be very large, affecting the memory usage of intermediate computations?

Brute Force Solution

Approach

The brute force approach to finding sequential digits involves generating every possible number within a given range and checking if it meets the required criteria. We'll start by checking single-digit numbers, then two-digit numbers, and so forth. This systematic approach ensures that we cover all potential solutions.

Here's how the algorithm would work step-by-step:

Start by making a list of all single-digit numbers (1 through 9).
Then, create all possible two-digit numbers where each digit is one greater than the digit before it (like 12, 23, 34, and so on).
Continue making numbers with more digits, always increasing each digit by one compared to the previous one.
For each number you create, check if it falls within the provided range (between the low and high numbers).
If the number is within the range, add it to a list of valid results.
Once you've created numbers up to nine digits, stop. We have created all possible sequential digits.
Finally, sort the list of valid numbers in ascending order.

Code Implementation

def sequential_digits_brute_force(low, high):
    results = []

    # Iterate through possible starting digits and lengths.
    for start_digit in range(1, 10):
        number = start_digit

        if number >= low and number <= high:
            results.append(number)

        for next_digit in range(start_digit + 1, 10):
            number = number * 10 + next_digit

            # This avoids numbers that are longer than 9 digits
            if number >= low and number <= high:
                results.append(number)

    # Sorting needed to return in increasing order
    results.sort()
    return results

Big(O) Analysis

Time Complexity

O(1) – The algorithm generates sequential digits from single-digit numbers up to nine-digit numbers. The number of sequential digits is fixed and independent of any input range (low and high). The algorithm iterates through a constant set of possible sequential digits and performs a constant number of operations for each. Therefore, the time complexity is O(1).

Space Complexity

O(1) – The brute force approach generates sequential digits and stores them in a list of valid results. The maximum number of sequential digits possible is fixed, as the digits must be increasing and distinct (12, 23, 34... 123456789). Therefore, the space required to store the valid results is constant. No other significant auxiliary space is used, so the overall space complexity is O(1).

Optimal Solution

Approach

The problem asks for numbers made of increasing sequential digits within a given range. The best approach is to directly generate these sequential digit numbers and then filter to only include the numbers within the range, avoiding unnecessary checks.

Here's how the algorithm would work step-by-step:

Start by generating all possible sequential digit numbers. Think of them as sequences like '123', '4567', or '89'.
The length of these sequences will range from 1 digit to 9 digits.
Create all these sequential numbers and then check if each one falls within the lower and upper bounds provided in the problem.
Finally, return the numbers that are within the required range in sorted order.

Code Implementation

def sequentialDigits(low, high):
    sequential_numbers_in_range = []
    # Generate sequential numbers of varying lengths.
    for start_digit in range(1, 10):
        sequential_number = start_digit
        for next_digit in range(start_digit + 1, 10):
            sequential_number = sequential_number * 10 + next_digit
            # Check if the generated number is within the range.
            if low <= sequential_number <= high:
                sequential_numbers_in_range.append(sequential_number)

            #If sequential number exceeds max, stop
            if sequential_number > high:
                break

    # Return the sorted list of sequential numbers.
    return sorted(sequential_numbers_in_range)

Big(O) Analysis

Time Complexity

O(1) – The algorithm generates all possible sequential digit numbers. There are a finite and small number of such numbers (less than 45). The generation takes constant time. Filtering these numbers to find those within the given range and sorting them also takes constant time because the number of sequential digit numbers is limited. Therefore, the overall time complexity is O(1).

Space Complexity

O(1) – The described algorithm primarily generates sequential digit numbers and checks if they fall within the given range. The number of sequential digit numbers that can be generated is constant (at most nine starting digits with lengths up to 9), and the algorithm stores these numbers in a temporary list. However, the maximum number of generated sequential numbers is independent of the input range (low, high), meaning it remains constant. Therefore, the auxiliary space used is constant, irrespective of the input size, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
low is greater than high	Return an empty list since the range is invalid.
low and high are equal and are a sequential digit number	Add the number to the result if it satisfies the sequential digit property.
low is a sequential digit number but high is not	The solution needs to identify all sequential digit numbers and check whether they fall within the range.
high is a sequential digit number but low is not	The solution should only add numbers within the inclusive range [low, high].
No sequential digit numbers exist between low and high	The solution should return an empty list if no numbers match the criteria within the range.
Integer overflow when constructing sequential digit numbers beyond 9 digits	Limit the construction of sequential digits to a maximum of 9 digits to avoid integer overflow.
low and high are very close, only needing small sequential number generation	Generate sequential numbers starting from length one and stopping once a number exceeds 'high'.
low and high are very far apart, generating almost all sequential numbers possible.	Generate sequential numbers starting from length one to nine, filtering within [low,high].

low is greater than high

How to Handle:

Return an empty list since the range is invalid.

low and high are equal and are a sequential digit number

How to Handle:

Add the number to the result if it satisfies the sequential digit property.

low is a sequential digit number but high is not

How to Handle:

The solution needs to identify all sequential digit numbers and check whether they fall within the range.

high is a sequential digit number but low is not

How to Handle:

The solution should only add numbers within the inclusive range [low, high].

No sequential digit numbers exist between low and high

How to Handle:

The solution should return an empty list if no numbers match the criteria within the range.

Integer overflow when constructing sequential digit numbers beyond 9 digits

How to Handle:

Limit the construction of sequential digits to a maximum of 9 digits to avoid integer overflow.

low and high are very close, only needing small sequential number generation

How to Handle:

Generate sequential numbers starting from length one and stopping once a number exceeds 'high'.

low and high are very far apart, generating almost all sequential numbers possible.

How to Handle:

Generate sequential numbers starting from length one to nine, filtering within [low,high].

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of `low` and `high`? Are they positive integers only?
What should I return if there are no sequential digit numbers within the given range?
Are the input `low` and `high` inclusive, meaning I should consider numbers equal to `low` and `high` as potential sequential digit numbers?
Can `low` be greater than `high`? If so, what should the output be?
Is the range between `low` and `high` expected to be small, or could it potentially be very large, affecting the memory usage of intermediate computations?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by making a list of all single-digit numbers (1 through 9).
Then, create all possible two-digit numbers where each digit is one greater than the digit before it (like 12, 23, 34, and so on).
Continue making numbers with more digits, always increasing each digit by one compared to the previous one.
For each number you create, check if it falls within the provided range (between the low and high numbers).
If the number is within the range, add it to a list of valid results.
Once you've created numbers up to nine digits, stop. We have created all possible sequential digits.
Finally, sort the list of valid numbers in ascending order.

Code Implementation

def sequential_digits_brute_force(low, high):
    results = []

    # Iterate through possible starting digits and lengths.
    for start_digit in range(1, 10):
        number = start_digit

        if number >= low and number <= high:
            results.append(number)

        for next_digit in range(start_digit + 1, 10):
            number = number * 10 + next_digit

            # This avoids numbers that are longer than 9 digits
            if number >= low and number <= high:
                results.append(number)

    # Sorting needed to return in increasing order
    results.sort()
    return results

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by generating all possible sequential digit numbers. Think of them as sequences like '123', '4567', or '89'.
The length of these sequences will range from 1 digit to 9 digits.
Create all these sequential numbers and then check if each one falls within the lower and upper bounds provided in the problem.
Finally, return the numbers that are within the required range in sorted order.

Code Implementation

def sequentialDigits(low, high):
    sequential_numbers_in_range = []
    # Generate sequential numbers of varying lengths.
    for start_digit in range(1, 10):
        sequential_number = start_digit
        for next_digit in range(start_digit + 1, 10):
            sequential_number = sequential_number * 10 + next_digit
            # Check if the generated number is within the range.
            if low <= sequential_number <= high:
                sequential_numbers_in_range.append(sequential_number)

            #If sequential number exceeds max, stop
            if sequential_number > high:
                break

    # Return the sorted list of sequential numbers.
    return sorted(sequential_numbers_in_range)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
low is greater than high	Return an empty list since the range is invalid.
low and high are equal and are a sequential digit number	Add the number to the result if it satisfies the sequential digit property.
low is a sequential digit number but high is not	The solution needs to identify all sequential digit numbers and check whether they fall within the range.
high is a sequential digit number but low is not	The solution should only add numbers within the inclusive range [low, high].
No sequential digit numbers exist between low and high	The solution should return an empty list if no numbers match the criteria within the range.
Integer overflow when constructing sequential digit numbers beyond 9 digits	Limit the construction of sequential digits to a maximum of 9 digits to avoid integer overflow.
low and high are very close, only needing small sequential number generation	Generate sequential numbers starting from length one and stopping once a number exceeds 'high'.
low and high are very far apart, generating almost all sequential numbers possible.	Generate sequential numbers starting from length one to nine, filtering within [low,high].

low is greater than high

How to Handle:

Return an empty list since the range is invalid.

low and high are equal and are a sequential digit number

How to Handle:

Add the number to the result if it satisfies the sequential digit property.

low is a sequential digit number but high is not

How to Handle:

The solution needs to identify all sequential digit numbers and check whether they fall within the range.

high is a sequential digit number but low is not

How to Handle:

The solution should only add numbers within the inclusive range [low, high].

No sequential digit numbers exist between low and high

How to Handle:

The solution should return an empty list if no numbers match the criteria within the range.

Integer overflow when constructing sequential digit numbers beyond 9 digits

How to Handle:

Limit the construction of sequential digits to a maximum of 9 digits to avoid integer overflow.

low and high are very close, only needing small sequential number generation

How to Handle:

Generate sequential numbers starting from length one and stopping once a number exceeds 'high'.

low and high are very far apart, generating almost all sequential numbers possible.

How to Handle:

Generate sequential numbers starting from length one to nine, filtering within [low,high].