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
Constraints:
1 <= k <= n <= 109This approach involves systematically traversing a conceptual lexicographical tree. Each integer can be considered a node, with its child nodes being its successors in a lexicographical sense. By counting numbers in subtrees, we can determine where the k-th smallest number lies without generating the entire lexicographical list.
The given C implementation finds the k-th smallest number in a lexicographical manner using a tree traversal strategy. The helper function count_steps calculates how many numbers lie between the current root and its next sibling. This counting allows us to decide if we should move down to the next level (using the current root as a prefix) or move to the next sibling node.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log(n)^2), as we are traversing a tree where we potentially explore and count nodes at each level.
Space Complexity: O(1), since we are not using any additional data structures.
This approach leverages binary search combined with a counting function to directly determine the k-th lexicographical number. Instead of constructing the list, we estimate the position of the k-th number by adjusting potential candidates using the count of valid numbers below a mid-point candidate.
This C approach implements a binary search to find the k-th smallest lexicographical number. The count_below function determines how many numbers less than a given prefix exist. Depending on this count, we adjust our binary search to quickly converge on the result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log(n)^2), where binary search narrows down potential candidates.
Space Complexity: O(1), minimal variable storage is employed.
| Approach | Complexity |
|---|---|
| Approach 1: Lexicographical Order Tree Traversal | Time Complexity: O(log(n)^2), as we are traversing a tree where we potentially explore and count nodes at each level. |
| Approach 2: Binary Search with Counting Function | Time Complexity: O(log(n)^2), where binary search narrows down potential candidates. |
K-th Smallest in Lexicographical Order - Leetcode 440 - Python • NeetCodeIO • 15,855 views views
Watch 9 more video solutions →Practice K-th Smallest in Lexicographical Order with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor