⚡Flashcard Drill➔
NeetCode #147LC-1291MediumArrays & Hashing
← Back to All Problems

#147 · #1291 · Sequential Digits(顺次数)

📌 Problem Statement & Constraints

An integer has sequential digits if each digit is exactly one more than the previous. Given low and high, return a sorted list of all sequential digits in the range. Constraints: 10 <= low <= high <= 10^9.

💡 Core Algorithmic Approaches

  1. Sequential numbers are fully determined by their length and their starting digit, so there are only 8 + 7 + ... + 1 = 36 candidates in total.
  2. Enumerate the length from 2 to 9 and the starting digit from 1 to 10 - length.
  3. Build the number digit by digit and keep it if it falls within [low, high].
  4. Because the enumeration proceeds by increasing length and starting digit, the resulting list is already sorted.

💻 Benchmark Python3 Implementation

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        res = []
        for length in range(2, 10):
            for start in range(1, 10):
                if start + length - 1 > 9:   # would exceed digit 9
                    break
                num = 0
                for d in range(length):
                    num = num * 10 + (start + d)
                if low <= num <= high:
                    res.append(num)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1): at most 36 candidates are generated, independent of the input magnitudes.
💾 Space Complexity
O(1) beyond the output.

⚠️ Interview Pitfalls & Follow-ups

  • Iterating over the whole range [low, high]: it can span 10^9 values; the enumeration is constant time.
  • Forgetting the start + length - 1 > 9 bound: starting digits near 9 with long lengths would produce digits above 9.
  • Generating candidates and then sorting: the enumeration order already yields sorted output.
  • Starting the length loop at 1: single-digit numbers are sequential trivially, but the constraints start at low >= 10, so length 1 never contributes.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems