In this guide, you will get 1291. Sequential Digits LeetCode Solution with the best time and space complexity. The solution to Sequential Digits problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Complexity Analysis
Time Complexity: O(9\log\texttt{high}) = O(\log\texttt{high})
Space Complexity: O(\log\texttt{high})
1291. Sequential Digits LeetCode Solution in C++
class Solution {
public:
vector<int> sequentialDigits(int low, int high) {
vector<int> ans;
queue<int> q{{1, 2, 3, 4, 5, 6, 7, 8, 9}};
while (!q.empty()) {
const int num = q.front();
q.pop();
if (num > high)
return ans;
if (low <= num && num <= high)
ans.push_back(num);
const int lastDigit = num % 10;
if (lastDigit < 9)
q.push(num * 10 + lastDigit + 1);
}
return ans;
}
}; /* code provided by PROGIEZ */
1291. Sequential Digits LeetCode Solution in Java
class Solution {
public List<Integer> sequentialDigits(int low, int high) {
List<Integer> ans = new ArrayList<>();
Queue<Integer> q = new ArrayDeque<>(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9));
while (!q.isEmpty()) {
final int num = q.poll();
if (num > high)
return ans;
if (low <= num && num <= high)
ans.add(num);
final int lastDigit = num % 10;
if (lastDigit < 9)
q.offer(num * 10 + lastDigit + 1);
}
return ans;
}
} // code provided by PROGIEZ
1291. Sequential Digits LeetCode Solution in Python
class Solution:
def sequentialDigits(self, low: int, high: int) -> list[int]:
ans = []
q = collections.deque([num for num in range(1, 10)])
while q:
num = q.popleft()
if num > high:
return ans
if low <= num and num <= high:
ans.append(num)
lastDigit = num % 10
if lastDigit < 9:
q.append(num * 10 + lastDigit + 1)
return ans # code by PROGIEZ
