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


  • 0
    J

    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.


Log in to reply
 

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