DDSA Solutions

1291. Sequential Digits

MediumView on LeetCode
MathenumerationRecursion

Problem Overview

A sequential-digit number has digits that increase by exactly 1 left to right (12, 123, 6789, …).

Intuition

A sequential-digit number has digits that increase by exactly 1 left to right (12, 123, 6789, …). There are only 36 such numbers in total, so generate them instead of scanning [low, high]. DFS from each start digit 1–9, always appending the next consecutive digit, and keep values that land in range.

Algorithm

  1. 1For start digit i = 1 … 9, call DFS with current digit pointer i and num = 0.
  2. 2In DFS: if num is inside [low, high], add it to the answer.
  3. 3Stop if num > high or the next digit would exceed 9.
  4. 4Otherwise recurse with the next digit i+1 and num = num*10 + i (append digit i).
  5. 5Sort the collected list (branches are not globally ordered) and return it.

Example Walkthrough

Input: low = 100, high = 300

  1. 1.From start 1: build 1 → 12 → 123 (123 is in range) → 1234 (too big, stop).
  2. 2.From start 2: build 2 → 23 → 234 (in range) → …
  3. 3.From start 3: 3 → 34 → 345 (345 > 300, stop after checking).
  4. 4.Collect and sort → [123, 234].

Output: [123, 234]

Common Pitfalls

  • •Do not iterate every integer from low to high — generate the tiny candidate set.
  • •Must sort at the end if generation order is not ascending across all starts.
  • •Single-digit numbers are sequential; they appear only when low ≤ that digit.
  • •A number like 7890 is invalid — digits must stay within 1–9 with no wrap.
1291.cs
C#
// Approach: DFS from each start digit 1–9, always appending the next consecutive digit.
// Collect numbers that fall in [low, high]; sort the small result list at the end.
// Time: O(1) — at most 36 sequential numbers Space: O(1)
public class Solution
{
    public IList<int> SequentialDigits(int low, int high)
    {
        var ans = new List<int>();
        for (int i = 1; i <= 9; i++)
            dfs(low, high, i, 0, ans);

        ans.Sort();
        return ans;
    }

    private void dfs(int low, int high, int i, int num, IList<int> ans)
    {
        if (num >= low && num <= high)
            ans.Add(num);

        if (num > high || i > 9)
            return;

        dfs(low, high, i + 1, num * 10 + i, ans);
    }
}
Was this solution helpful?

Related Problems