Concise/Easy-to-understand Java 5ms solution with Explaination


  • 88

    Original idea comes from
    http://bookshadow.com/weblog/2016/10/24/leetcode-k-th-smallest-in-lexicographical-order/

    Actually this is a denary tree (each node has 10 children). Find the kth element is to do a k steps preorder traverse of the tree.
    0_1477293053966_upload-40379731-118a-4753-bed9-1cb372790d4b

    Initially, image you are at node 1 (variable: curr),
    the goal is move (k - 1) steps to the target node x. (substract steps from k after moving)
    when k is down to 0, curr will be finally at node x, there you get the result.

    we don't really need to do a exact k steps preorder traverse of the denary tree, the idea is to calculate the steps between curr and curr + 1 (neighbor nodes in same level), in order to skip some unnecessary moves.

    Main function
    Firstly, calculate how many steps curr need to move to curr + 1.

    1. if the steps <= k, we know we can move to curr + 1, and narrow down k to k - steps.

    2. else if the steps > k, that means the curr + 1 is actually behind the target node x in the preorder path, we can't jump to curr + 1. What we have to do is to move forward only 1 step (curr * 10 is always next preorder node) and repeat the iteration.

    calSteps function

    1. how to calculate the steps between curr and curr + 1?
      Here we come up a idea to calculate by level.
      Let n1 = curr, n2 = curr + 1.
      n2 is always the next right node beside n1's right most node (who shares the same ancestor "curr")
      (refer to the pic, 2 is right next to 1, 20 is right next to 19, 200 is right next to 199).

    2. so, if n2 <= n, what means n1's right most node exists, we can simply add the number of nodes from n1 to n2 to steps.

    3. else if n2 > n, what means n (the biggest node) is on the path between n1 to n2, add (n + 1 - n1) to steps.

    4. organize this flow to "steps += Math.min(n + 1, n2) - n1; n1 *= 10; n2 *= 10;"

    Here is the code snippet:

    public int findKthNumber(int n, int k) {
        int curr = 1;
        k = k - 1;
        while (k > 0) {
            int steps = calSteps(n, curr, curr + 1);
            if (steps <= k) {
                curr += 1;
                k -= steps;
            } else {
                curr *= 10;
                k -= 1;
            }
        }
        return curr;
    }
    //use long in case of overflow
    public int calSteps(int n, long n1, long n2) {
        int steps = 0;
        while (n1 <= n) {
            steps += Math.min(n + 1, n2) - n1;
            n1 *= 10;
            n2 *= 10;
        }
        return steps;
    }

  • 0
    A

    very good explain. Thank you


  • 0

    Very interesting solution!


  • 0
    T

    @NathanNi amazing solution and even better explanation.


  • 1
    W

    what is the time complexity for this solution?


  • 0
    D

    incredibly smart...


  • 0
    O

    This is simply brilliant!


  • 0
    F

    I think the expression k=k-1 is unnecessary, we can just stop the loop when k is 1:

        public int findKthNumber(int n, int k) {
            int result = 1;
            while (k > 1) {
                int count = findKthNumber(result, result + 1, n);
                if (count < k) {
                    result++;
                    k -= count;
                } else {
                    result *= 10;
                    k--;
                }
            }
            return result;
        }
    
    //10p,10q may cause overflow, n+1 may cause overflow(not in this problem), because 1<=k<=n<=10^9
    //but in my test case, I let n be Int.Maxvalue, then n+1 may cause overflow
        private int findKthNumber(long p, long q, long n) {
            int result = 0;
            while (p <= n) {
                result += Math.min(q, n + 1) - p;
                p *= 10;
                q *= 10;
            }
            return result;
        }
    

  • 0
    A

    beautiful solution!!


  • 1
    M

    brilliant! lao ge wen!


  • 1
    M

    What if the cur = 9, cur + 1 = 10? They are not on the same level.I think you did not discuss this case.

    when cur and cur+1 are not on the same level, the kth element we are looking for must be in the cur tree. So we can search the subtree by multiply cur with 10.

    So I think, the proper understanding of this code is to treat calStep as a function which calcaulates the number of nodes in the forests n1, n1 + 1, n1 + 2, ... n2 - 1

    In order to find the kth element in preorder traversal, we will have to choose the direction we move. We can move horizontally by adding 1 to cur, or vertically by multiplying cur with 10. When the number of nodes of the cur tree is not enough, obviously we will move to the right sibling, otherwise we will search from the left most children.


  • 0
    M

    great solution, thanks for sharing and explanation.
    I think the runtime is O( logn + k ), please correct me if I'm wrong.


  • 0
    E
    This post is deleted!

  • 0
    Z

    Hi, since the worst case is traversal the whole tree, so can we say the O(n), n is the number of the node we have in the tree. please correct me if I'm wrong.


  • 0

    Perfect! Very impressive!


  • 0

    @NathanNi
    Python version:

        def findKthNumber(self, n, k):
            cur = 1
            k = k - 1
            while k > 0:
                steps = self.calSteps(n, cur)
                if steps <= k:
                    cur += 1
                    k -= steps
                else:
                    cur *= 10
                    k -= 1
            return cur
    
        def calSteps(self, n, cur):
            steps = 0
            n1, n2 = cur, cur + 1
            while n1 <= n:
                steps += min(n + 1, n2) - n1
                n1 *= 10
                n2 *= 10
            return steps
    

    My calSteps function:

        def steps(self, n, cur):
            dif = 10 ** (len(str(n)) - len(str(cur)))
            return dif / 9 + min(max(n - cur * dif + 1, 0), dif)

  • 0
    F

    @NathanNi very good idea


Log in to reply
 

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