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 ++) {
ans.add(curr);
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.**