Sequential Digits Interview Question for Amazon

def sequentialDigits(low: int, high: int) -> list[int]:
    """Finds all integers in the range [low, high] with sequential digits."""
    result = []
    for length in range(len(str(low)), len(str(high)) + 1):
        for start_digit in range(1, 10 - length + 1):
            num = 0
            for i in range(length):
                num = num * 10 + (start_digit + i)
            if low <= num <= high:
                result.append(num)
    return sorted(result)

# Example usage:
low = 100
high = 300
print(f"Sequential digits between {low} and {high}: {sequentialDigits(low, high)}")

low = 1000
high = 13000
print(f"Sequential digits between {low} and {high}: {sequentialDigits(low, high)}")

Explanation:

The sequentialDigits function identifies and returns a sorted list of integers within a specified range [low, high] that have sequential digits.

Initialization: The function begins by initializing an empty list called result, which will store the sequential digit numbers found within the given range.
Determine Lengths: It iterates through possible lengths of sequential digit numbers, starting from the length of the low number and ending at the length of the high number. This is done using a for loop: for length in range(len(str(low)), len(str(high)) + 1):.
Determine Starting Digits: For each length, the function iterates through possible starting digits. The starting digit can range from 1 to 10 - length. This ensures that when we generate a number of the current length starting from start_digit, we don't exceed the digit 9. This is implemented using the loop for start_digit in range(1, 10 - length + 1):.
Construct the Number: For each length and start_digit, it constructs a number with sequential digits. This is done by initializing num = 0 and then, for each digit position i from 0 to length - 1, appending the digit start_digit + i to the number. This is achieved using the inner loop for i in range(length): and the calculation num = num * 10 + (start_digit + i).
Check if in Range: After constructing the number num, the function checks if num falls within the specified range [low, high]. If low <= num <= high, the number is appended to the result list.
Sort and Return: Finally, after generating all possible sequential digit numbers and filtering those within the range, the result list is sorted in ascending order using sorted(result) and returned.

Example Walkthrough:

Consider low = 1000 and high = 13000.

The outer loop iterates for lengths 4 and 5.
For length 4, the inner loop iterates for start digits from 1 to 6.
- When start_digit is 1, num becomes 1234. Since 1000 <= 1234 <= 13000, 1234 is added to the result.
- When start_digit is 2, num becomes 2345. Since 1000 <= 2345 <= 13000, 2345 is added to the result.
- This continues until start_digit is 6, and num becomes 6789. Since 1000 <= 6789 <= 13000, 6789 is added.
For length 5, the inner loop iterates for start digits from 1 to 5.
- When start_digit is 1, num becomes 12345. Since 1000 <= 12345 <= 13000, is not true, we don't add it.
- We stop at 12345 and consider it within the output since it's valid
Finally, the result list is sorted and returned.

Naive Approach:

A naive approach would involve iterating through each number in the range [low, high] and checking whether the digits are sequential. This method would be less efficient, especially for larger ranges, because it involves checking every number individually.

Optimal Approach:

The approach used in the code is more optimal because it directly constructs sequential digit numbers and only checks numbers that are guaranteed to have sequential digits. This avoids checking every number in the range.

Big O Runtime Analysis:

The time complexity of this function can be analyzed as follows:

The outer loop runs for a maximum of log10(high) - log10(low) + 1 times, which simplifies to a constant number of iterations because the length of the numbers is bounded by the number of digits in high.
The inner loop runs for a maximum of 9 - length + 1 times, which is also a constant.
The construction of the number num takes length time, which is O(1) since the maximum length is bounded.
The sorted function takes O(n log n) time, where n is the number of elements in the result list. In the worst case, the number of elements in result can be proportional to the range of lengths, so it's still relatively small.

Overall, the dominant factor is generating the sequential numbers which is O(1), and sorting them is O(n log n) where n is the number of sequential numbers. Thus the time complexity is approximately O(n log n). However, because n is small (max number of sequential numbers is very low), we often consider it O(1).

Big O Space Usage Analysis:

The space complexity of this function is determined by the space required to store the result list. In the worst case, the list could contain all possible sequential digit numbers within the given range. Since the number of digits is bounded, the number of possible sequential digit numbers is also bounded. Thus, the space complexity is O(1) since the maximum number of sequential digits is very low.

Edge Cases:

Large Range: If high is significantly larger than low, the algorithm efficiently constructs only valid sequential numbers.
Small Range: If low and high are very close, the algorithm quickly finds the few valid sequential numbers.
No Sequential Numbers: If there are no sequential digit numbers in the range, the function returns an empty list, which is the correct behavior.
low and high have different number of digits: The code handles cases where low and high have a different number of digits effectively by considering different lengths of sequential digits.