# Java O(n) time, O(1) space iterative solution 130ms

• ``````public List<Integer> lexicalOrder(int n) {
List<Integer> list = new ArrayList<>(n);
int curr = 1;
for (int i = 1; i <= n; i++) {
if (curr * 10 <= n) {
curr *= 10;
} else if (curr % 10 != 9 && curr + 1 <= n) {
curr++;
} else {
while ((curr / 10) % 10 == 9) {
curr /= 10;
}
curr = curr / 10 + 1;
}
}
return list;
}
``````

The basic idea is to find the next number to add.
Take 45 for example: if the current number is 45, the next one will be 450 (450 == 45 * 10)(if 450 <= n), or 46 (46 == 45 + 1) (if 46 <= n) or 5 (5 == 45 / 10 + 1)(5 is less than 45 so it is for sure less than n).
We should also consider n = 600, and the current number = 499, the next number is 5 because there are all "9"s after "4" in "499" so we should divide 499 by 10 until the last digit is not "9".
It is like a tree, and we are easy to get a sibling, a left most child and the parent of any node.

• best solution!

• really smart solution, so far best.
The only challenge here these observations are not very straightforward, likely without some fresh memorization I will forget this solution during interview. I still recommend DFS solution though since I could visualize the solution which really helps memorize it.

• @GoCodeZ
It is actually a tree with dfs method, but only we can get the next node easier:)

• This post is deleted!

• @songzec Similar idea, but less "/10", and did not waste the n+1th calculation.

``````/*
* ans[i] = ans[i-1]*10 <= n ? ans[i-1]*10 : ans[i-1]%10 < 9 ? ans[i-1] + 1 : ans[i-1]/10%10 < 9 ? ...
*/
public class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> ans = new ArrayList<>(n);
for (int i = 1, prev = 1; i < n; ++i) {
if (prev * 10 <= n) {
prev *= 10;
} else {
while (prev % 10 == 9 || prev == n) prev /= 10;
prev++;
}
}
return ans;
}
}
``````

• similar idea, a little cleaner

``````class Solution(object):
def lexicalOrder(self, n):
"""
:type n: int
:rtype: List[int]
"""
res = []
curr = 1
for _ in xrange(n):
res.append(curr)
if curr*10 <= n:
curr = curr*10
else:
if curr%10 != 9 and curr + 1 <= n:
curr = curr + 1
else:
# look back to find the digit that needs to be incremented
curr = curr/10
while (curr%10) == 9:
curr = curr/10

curr = curr + 1

return res
``````

• ``````vector<int> lexicalOrder(int n) {
vector<int> res;
int cur = 1;
while (res.size() < n) {
res.push_back(cur);
if (cur * 10 <= n) {
cur *= 10;
}
else if (cur % 10 == 9 ||cur==n) {
while ((cur % 10 == 9) || cur == n) {
cur /= 10;
}
cur += 1;
}
else if(cur<n) cur++;
}
return res;
``````

}

• Best solution! Thanks.

• ``````else {
while ((curr / 10) % 10 == 9) {
curr /= 10;
}
curr = curr / 10 + 1;
}
``````

Could you please explain this case ?

Thanks.

• @dreamer92
Consider case: curr = 4999, n = 10000, in this case the next one should be 5. And this is how I get it.

• Heya I'm getting memory limit exceeded when I use this solution, any ideas why?

• I make a little modification that is a litter simpler in your 3rd "if" branch.

``````public class Solution {
public List<Integer> lexicalOrder(int n) {
int cur = 1;
for(int i = 0; i < n; i++){
if(cur * 10 <= n){
cur *= 10;
}else if(cur % 10 != 9 && cur + 1 <= n){
cur++;
}else{
cur = cur / 10;
while(cur % 10 == 9){
cur = cur / 10;
}
cur++;
}
}
return res;
}
}``````

• Cool implementation, but there is no way to make it O(1) space, because answer already requires O(n) space

• @ZhassanB I think when we say O(1) space we usually mean O(1) extra space.

• @iambright Like it. Make it shorter:

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

}
return ans;
}
``````

• Ur idea is rewrite the recursion method into iteration, thx for the code~~lol

• Similar idea, but compares to 10, not 9

``````public class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<Integer>();
int num = 1;
for (int i=0; i<n; i++) {
if (num * 10 <= n) {
num *= 10;
} else if (num + 1 <= n || (num + 1) % 10 == 0) {
num++;
while (num % 10 == 0) num /= 10;
} else {
num = num / 10 + 1;
}
}
return res;
}
}
``````

• @iaming

Hats off. So carefully tailored and trimmed.

• Best solution! So clever!

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