🌍 Beginner-Friendly Guide to Solving "K-th Smallest in Lexicographical Order" LeetCode 440 (C++ | JavaScript | Python)

#programming #javascript #cpp #python

Hey coding pioneers! 🧭
Today, we’re tackling a Hard problem that blends greedy algorithms with lexicographical tree traversal — a neat and elegant concept hiding behind a deceptively simple prompt.

Let’s dive into LeetCode 440: K-th Smallest in Lexicographical Order — and we’ll break it down in a clean, beginner-friendly way. 💡

📜 Problem Overview

Given two integers n and k, return the k-th smallest number in lexicographical (dictionary) order from the range [1, n].

🧾 Example 1:

Input: n = 13, k = 2  
Output: 10
Explanation: Lexicographical order → [1,10,11,12,13,2,3,4,5,6,7,8,9]

🧾 Example 2:

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

🧠 Intuition & Strategy

This problem can be visualized as a 10-ary tree (prefix tree) rooted at 1, where each node represents a number and each child adds another digit to it.

Think of lexicographical order as a preorder traversal of this virtual tree:

1 → 10 → 100...
Then backtrack and go to 2 → 20 → 200..., and so on.

Our goal is to traverse this tree until we reach the k-th node.

🔍 Key Insight:

We don’t need to generate the entire order. Instead, we count how many nodes (i.e., numbers) are between a prefix a and its sibling prefix b = a + 1.

This count is called a “gap”, and we use it to decide whether to:

Move to the next sibling (increment a)
Go deeper in the subtree (multiply a by 10)

📘 getGap(a, b, n)

This helper function calculates how many numbers exist in the range [a, b) under the lexicographical tree and up to n.

E.g., getGap(1, 2, 13) returns how many numbers lie between 1 and 2:
=> [1, 10, 11, 12, 13] => 5

⚙️ C++ Code (Efficient)

class Solution {
 public:
  int findKthNumber(int n, int k) {
    long ans = 1;

    for (int i = 1; i < k;) {
      const long gap = getGap(ans, ans + 1, n);
      if (i + gap <= k) {
        i += gap;
        ++ans;
      } else {
        ++i;
        ans *= 10;
      }
    }

    return ans;
  }

 private:
  long getGap(long a, long b, long n) {
    long gap = 0;
    while (a <= n) {
      gap += min(n + 1, b) - a;
      a *= 10;
      b *= 10;
    }
    return gap;
  }
};

🌐 JavaScript Version

var findKthNumber = function(n, k) {
    let curr = 1;
    let i = 1;

    const getGap = (a, b, n) => {
        let gap = 0;
        while (a <= n) {
            gap += Math.min(n + 1, b) - a;
            a *= 10;
            b *= 10;
        }
        return gap;
    };

    while (i < k) {
        let gap = getGap(curr, curr + 1, n);
        if (i + gap <= k) {
            i += gap;
            curr++;
        } else {
            i++;
            curr *= 10;
        }
    }

    return curr;
};

🐍 Python Version

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def getGap(a: int, b: int, n: int) -> int:
            gap = 0
            while a <= n:
                gap += min(n + 1, b) - a
                a *= 10
                b *= 10
            return gap

        curr = 1
        i = 1

        while i < k:
            gap = getGap(curr, curr + 1, n)
            if i + gap <= k:
                i += gap
                curr += 1
            else:
                i += 1
                curr *= 10

        return curr

🧪 Test Case Scenarios

Input: n = 13, k = 2  
Output: 10  
→ Lexicographical: [1,10,11,12,13,2,3...]

Input: n = 100, k = 10  
Output: 17  
→ We skip prefixes based on calculated gaps.

Input: n = 1000000, k = 1000  
Output: Efficient tree traversal returns result in milliseconds.

Input: n = 1, k = 1  
Output: 1  
→ Base case

🧮 Time & Space Complexity

Time Complexity: O(log n * log n)
- log n levels in the tree
- Each getGap call takes O(log n) time

Space Complexity: O(1)
- Constant extra space (no recursion or data structures)