# Neat Java O(n) time, O(1) Space Solution with Explanation

• Let read the code first

``````public class Solution {
private int getNext(int n, int limit) {
if(n * 10 <= limit) {
return n * 10;
} else {
while(n % 10 == 9 || n >= limit) {
n /= 10;
}
return n + 1;
}
}
public List<Integer> lexicalOrder(int n) {
int curr = 1;
List<Integer> ans = new ArrayList<>();
for(int i = 0; i < n; i ++) {
curr = getNext(curr, n);
}

return ans;
}
}
``````

The core of the algorithm is the getNext method. Let's start with two good examples to understand how we can build a getNext
If n = 13, the sequence is
[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
If n = 129, the sequence is
[1, 10, 100, 101...109, 11, 110, 111...119, 12, 120, 121...129, 13, 130, 14, 15...19, 2, 20, 21...29, 3....9, 90....99]

We can find out 3 rules for getNext
Rule 1. If n * 10 <= limit, then the next number in the sequence is n * 10
Rule 2. If n % 10 != 9 AND n + 1 <= limit, then the next number in the sequence is n + 1

The above 2 rules are very obvious, if you take a not-so-close look at the 2 examples.

However, the difficulty lies in the 3rd rule. What if rule 1 or rule 2 cannot be applied to the current number.
Say we have
limit = 129 and curr = 129, then getNext(curr) = 129 / 10 + 1 = 13
or
limit = 129 and curr = 19, then getNext(curr) = 19 / 10 + 1 = 2

The above 2 situation requires us to divide the curr number by 10 and plus 1 to get the next number.

Therefore, we have rule 3.
Rule 3. If rule 1 and rule 2 does not apply, then we keep letting n = n/10, until rule 2 satisfy(we've already keep dividing 10, so we do not need rule 1 again). Then we return n + 1.

PS: In the code above, we combine rule2 and rule3.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.