Sequential Digits

• Initialize an empty list result.
• Loop for num from low to high.
• For each num, check if it has sequential digits using a helper function isSequential(num).
• The isSequential function works as follows:
  • Convert the number num to its string representation, s.
  • Iterate from the first character to the second-to-last character of s.
  • In each step, check if the character at the next position is exactly one greater than the character at the current position (e.g., s.charAt(i+1) - s.charAt(i) == 1).
  • If this condition ever fails, the number is not sequential, so return false.
  • If the loop completes without returning, it means all digits are sequential, so return true.
• If isSequential(num) returns true, add num to the result list.
• After checking all numbers up to high, return the result list. The list will be sorted because we iterate from low to high.

The most straightforward way to solve this problem is to check every single number in the given range. We can create a helper function, say isSequential(n), that takes an integer and returns true if its digits are sequential and false otherwise.

Inside isSequential(n), we can convert the number n to a string to easily access its digits. Then, we iterate through the digits from the first to the second-to-last. In each step, we check if the next digit is exactly one more than the current digit. If this condition ever fails, we immediately know the number is not sequential and can return false. If the loop completes without finding any non-sequential pairs, the number is sequential, and we return true.

The main function will loop from low to high. For each number i in the loop, it calls isSequential(i). If isSequential(i) returns true, i is added to the result list. Since we iterate in increasing order, the list will be naturally sorted.

1class Solution {2    public List<Integer> sequentialDigits(int low, int high) {3        List<Integer> result = new ArrayList<>();4        for (int i = low; i <= high; i++) {5            if (isSequential(i)) {6                result.add(i);7            }8        }9        return result;10    }11 12    private boolean isSequential(int n) {13        String s = String.valueOf(n);14        for (int i = 0; i < s.length() - 1; i++) {15            if (s.charAt(i + 1) - s.charAt(i) != 1) {16                return false;17            }18        }19        return true;20    }21}

• Initialize an empty list result.
• Initialize a queue (e.g., LinkedList) and add the single-digit numbers 1 through 9 to it. These are the seeds for all sequential numbers.
• Start a loop that continues as long as the queue is not empty.
  • Dequeue an element, let's call it current.
  • If current is within the range [low, high], add it to the result list.
  • If current is greater than high, we can stop processing because all subsequent numbers generated will also be larger. Break the loop.
  • Get the last digit of current: lastDigit = current % 10.
  • If lastDigit < 9, it's possible to form a longer sequential number.
    • Calculate the next sequential number: nextNum = current * 10 + (lastDigit + 1).
    • If nextNum is not greater than high, add it to the queue.
• Return the result list. It is already sorted because the BFS-like generation produces numbers in increasing order.

The key observation is that there are only a limited number of sequential digit numbers (e.g., 12, 234, 5678, etc.). The smallest is 12 and the largest is 123456789. Instead of checking every number in a potentially vast range, we can just generate this small set of valid numbers and see which ones fit our criteria.

A clean way to generate these numbers in sorted order is to use a Breadth-First Search (BFS) approach. We can think of the numbers as nodes in a tree where a number N has a child N*10 + (last_digit_of_N + 1).

We start by seeding a queue with the single-digit numbers (1 to 9). Then, we iteratively take a number from the queue, check if it's in our [low, high] range, and then generate the next sequential number to add back to the queue. We stop generating children for a number if its last digit is 9 or if the number itself exceeds high.

This method naturally generates the numbers in ascending order (1, 2, ..., 9, 12, 23, ..., 89, 123, ...), so the final result list will be sorted as required.

1class Solution {2    public List<Integer> sequentialDigits(int low, int high) {3        List<Integer> result = new ArrayList<>();4        Queue<Integer> queue = new LinkedList<>();5 6        // Initialize the queue with single-digit numbers (our starting points)7        for (int i = 1; i <= 9; i++) {8            queue.add(i);9        }10 11        while (!queue.isEmpty()) {12            int current = queue.poll();13 14            // If the current number is within the desired range, add it.15            if (current >= low && current <= high) {16                result.add(current);17            }18 19            // If current exceeds high, no need to check further from this path.20            if (current > high) {21                continue; // or break, since queue is ordered22            }23 24            int lastDigit = current % 10;25            // If the last digit is not 9, we can form a longer sequential number.26            if (lastDigit < 9) {27                int nextNum = current * 10 + (lastDigit + 1);28                if (nextNum <= high) {29                    queue.add(nextNum);30                }31            }32        }33        34        return result;35    }36}