We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sequential Digits

Number: 1212

Difficulty: Medium

Paid? No

Companies: Amazon, Apple, Google, Adobe, F5

Problem Description

Find and return a sorted list of all integers within the range [low, high] that have sequential digits. A number has sequential digits if every digit is exactly 1 greater than the previous digit.

Key Insights

  • Sequential digits can only be constructed from the ordered digit string "123456789".
  • The length of the candidate numbers is constrained by the number of digits in the low and high bounds.
  • There are limited possibilities (at most 36 different sequential digit numbers), so pre-generation by sliding window over "123456789" is efficient.
  • Only include candidates that fall within the given range.

Space and Time Complexity

Time Complexity: O(1) – There is a constant upper bound on the number of candidates generated (at most 36). Space Complexity: O(1) – Only a fixed number of variables and candidate numbers are stored.

Solution

The solution involves generating all sequential digit numbers by sliding a window of length L over the pre-defined string "123456789". The window size L varies from the number of digits in low to the number of digits in high. For each candidate number generated, check if it lies within the range [low, high]. If it does, add it to the result list, which is then returned in sorted order. The algorithms use string slicing and integer conversion, and due to the small number of candidates, the approach is optimally efficient.

Code Solutions

# Python solution with detailed inline comments.
class Solution:
    def sequentialDigits(self, low: int, high: int) -> list:
        # Initialize a list to hold valid sequential digit numbers.
        result = []
        # Convert the bounds to strings to determine the range of lengths.
        low_len = len(str(low))
        high_len = len(str(high))
        # The reference string containing sequential digits.
        digits = "123456789"
        # Iterate over possible lengths of candidate numbers.
        for L in range(low_len, high_len + 1):
            # Slide a window of length L over the digits string.
            for i in range(0, 10 - L):
                # Generate a candidate number by slicing and converting to integer.
                num = int(digits[i:i+L])
                # Check if candidate is within the given range.
                if low <= num <= high:
                    result.append(num)
        # Return the list sorted in increasing order.
        return sorted(result)
← Back to All Questions