Last updated on January 29th, 2025 at 02:12 am

Here, we see a K-th Smallest in Lexicographical Order LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array

Level of Question

Hard

K-th Smallest in Lexicographical Order LeetCode Solution

1. Problem Statement

Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].

Example 1:
Input: n = 13, k = 2
Output: 10
Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

Example 2:
Input: n = 1, k = 1
Output: 1

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Lexicographical Order Traversal”, a specific approach to solve problems where numbers or strings need to be traversed in lexicographical (dictionary) order. The code essentially simulates a traversal of a virtual tree where each node represents a number, and the children of a node represent numbers formed by appending digits to the current number.

3. Code Implementation in Different Languages

3.1 K-th Smallest in Lexicographical Order C++

class Solution {
public:
   int calSteps(int n, long n1, long n2) {
    int steps = 0;
    while (n1 <= n) {
        steps += min((long)n + 1, n2) - n1;
        n1 *= 10;
        n2 *= 10;
    }
    return steps;
}
   int findKthNumber(int n, int k) {
        int curr = 1;
        k--;
        while (k > 0) {
            int steps = calSteps(n, curr, curr + 1);
            if (steps <= k) {
                curr += 1;
                k -= steps;
            } 
            else {
                curr *= 10;
                k--;
            }
        }
        return curr;
    }
};

3.2 K-th Smallest in Lexicographical Order Java

class Solution {
    public int findKthNumber(int n, int k) {
        int prefix=1;
        for(int count=1;count<k;){
            int currCount=getCountWithPrefix(prefix,prefix+1,n);
            if(currCount+count<=k){
                count+=currCount;
                prefix++;
            }else{
                prefix*=10;
                count++;
            }
        }
        return prefix;
    }
    private int getCountWithPrefix(long startPrefix,long endPrefix,int max){
        int count=0;
        while(startPrefix<=max){
            count+=Math.min(max+1,endPrefix)-startPrefix;
            startPrefix*=10;
            endPrefix*=10;
        }
        return count;
    }
}

3.3 K-th Smallest in Lexicographical Order JavaScript

var findKthNumber = function (n, k) {
    function dfs (l, r) {
        let nn = BigInt(n);
        if (l > nn) {
            return 0n;
        }
        if (r > nn) {
            r = nn;
        }
        return r - l + 1n + dfs(l * 10n, r * 10n + 9n);
    }
    let kn = BigInt(--k), cu = 1;
    while (kn > 0) {
        let cs = dfs(BigInt(cu), BigInt(cu));
        if (cs <= kn) {
            kn -= cs;
            cu++;
        }
        else {
            kn -= 1n;
            cu *= 10;
        }
    }
    return cu;
};

3.4 K-th Smallest in Lexicographical Order Python

class Solution(object):
    def findKthNumber(self, n, k):
        cur = 1
        k -= 1
        while k > 0:
            steps = self.getSteps(n, cur, cur+1)
            if steps <= k:
                cur += 1
                k -= steps
            else:
                cur *= 10
                k -= 1
        return cur

    def getSteps(self, n, n1, n2):
        steps = 0
        while n1 <= n:
            steps += min(n+1, n2) - n1
            n1 *= 10
            n2 *= 10
        return steps

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(log(n) * log(n))	O(1)
Java	O(log(n) * log(n))	O(1)
JavaScript	O(log(n) * log(n))	O(log(n))
Python	O(log(n) * log(n))	O(1)

• The time complexity is dominated by the nested loops: the outer loop iterates over the lexicographical tree, and the inner loop calculates the number of steps for each prefix.
• The space complexity is constant for C++, Java, and Python because no additional data structures are used. However, JavaScript uses recursion in the dfs function, which adds stack space proportional to the height of the tree.
• The algorithm is efficient for large values of n and k because it avoids generating all numbers explicitly and instead uses a tree traversal approach.