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
- Sequential numbers are fully determined by their length and their starting digit, so there are only
8 + 7 + ... + 1 = 36candidates in total. - Enumerate the length from 2 to 9 and the starting digit from 1 to
10 - length. - Build the number digit by digit and keep it if it falls within
[low, high]. - 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 > 9bound: 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.