Sequential Digits
MedPrompt
An integer has sequential digits if and only if each digit in the number is one more than the previous digit.
Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.
Example 1:
Input: low = 100, high = 300
Output: [123,234]Example 2:
Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]
Constraints:
10 <= low <= high <= 10^9
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through every integer from low to high. For each integer, we perform a check to see if its digits are sequential. If they are, the integer is added to our result list.
Algorithm
- Initialize an empty list
result. - Loop for
numfromlowtohigh. - For each
num, check if it has sequential digits using a helper functionisSequential(num). - The
isSequentialfunction works as follows:- Convert the number
numto 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.
- Convert the number
- If
isSequential(num)returnstrue, addnumto theresultlist. - After checking all numbers up to
high, return theresultlist. The list will be sorted because we iterate fromlowtohigh.
Walkthrough
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.
class Solution { public List<Integer> sequentialDigits(int low, int high) { List<Integer> result = new ArrayList<>(); for (int i = low; i <= high; i++) { if (isSequential(i)) { result.add(i); } } return result; } private boolean isSequential(int n) { String s = String.valueOf(n); for (int i = 0; i < s.length() - 1; i++) { if (s.charAt(i + 1) - s.charAt(i) != 1) { return false; } } return true; }}Complexity
Time
O(N * L), where N is the number of integers in the range `[low, high]` (i.e., `high - low + 1`) and L is the number of digits in the integer. Since `high` can be up to `10^9`, L is at most 10. The complexity can be written as O((high - low) * log10(high)). This is very slow for large ranges.
Space
O(log10(high)). The space is dominated by the storage required for the string representation of the number being checked. The result list stores at most 36 numbers, which is constant space.
Trade-offs
Pros
Simple to understand and implement.
Requires minimal logic beyond the problem definition.
Cons
Highly inefficient for large ranges between
lowandhigh.Will likely result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms due to its high time complexity.
Solutions
Solution
class Solution { public List < Integer > sequentialDigits ( int low , int high ) { List < Integer > ans = new ArrayList <>(); for ( int i = 1 ; i < 9 ; ++ i ) { int x = i ; for ( int j = i + 1 ; j < 10 ; ++ j ) { x = x * 10 + j ; if ( x >= low && x <= high ) { ans . add ( x ); } } } Collections . sort ( ans ); return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.