LeetCode 440 is a challenging Hard-level problem that combines greedy algorithms, prefix tree traversal, and mathematical counting to efficiently find the k-th smallest number in lexicographical order without generating the entire sequence.
📜 Problem Statement
Given two integers n and k, return the k-th smallest number in lexicographical (dictionary) order from the range [1, n].
Constraints:
1 <= k <= n <= 10^9The solution must handle large inputs efficiently
Core Problem Examples
Example 1: Basic Case
Input: n = 13, k = 2
Output: 10
Explanation:
Lexicographical order: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
The 2nd smallest number is 10
Example 2: Edge Case
Input: n = 1, k = 1
Output: 1
Explanation: Only one number exists in range [1, 1]
Example 3: Large Numbers
Input: n = 100, k = 10
Output: 17
Explanation: Efficient traversal without generating full sequence
🧠 Algorithm Strategy: Prefix Tree Traversal with Gap Counting
Visual Representation: 10-ary Prefix Tree
The lexicographical order can be visualized as a 10-ary tree where each node represents a number prefix:
Root
/ | \
1 2 3 ... 9
/| | |
10 11 20 30 ...
|
100 101 ...
Key Algorithm Concepts
Concept 1: Lexicographical Tree Traversal
Numbers in lexicographical order follow a preorder traversal pattern:
Visit current node (add to result)
Traverse left subtree (multiply by 10)
Traverse right siblings (increment by 1)
Concept 2: Gap Counting Strategy
Instead of generating all numbers, we calculate gaps between prefixes to determine:
Whether to move to next sibling (skip current subtree)
Whether to go deeper into current subtree
Concept 3: Greedy Decision Making
At each step, we decide the optimal path based on:
Current position in the sequence
Remaining steps to reach k-th position
Size of subtrees ahead
The Gap Counting Algorithm: Core Logic
Understanding the getGap Function
The getGap(a, b, n) function calculates how many valid numbers exist between prefix a and prefix b within the constraint n.
Gap Calculation Example
For n = 13, calculating getGap(1, 2, 13):
Level 0: [1] → count = 1
Level 1: [10, 11, 12, 13] → count = 4
Total gap = 5 numbers between prefix 1 and 2
Step-by-Step Algorithm Walkthrough
For n = 13, k = 2:
Start:
curr = 1, i = 1Calculate gap between 1 and 2:
gap = 5Check condition:
i + gap = 1 + 5 = 6 > k = 2Decision: Go deeper into subtree 1
Update:
curr = 10, i = 2Result: Return
10(the 2nd number)
Optimized Implementation Solutions
C++ Solution (Most Efficient)
class Solution {
public:
int findKthNumber(int n, int k) {
long curr = 1;
for (int i = 1; i < k;) {
long gap = getGap(curr, curr + 1, n);
if (i + gap <= k) {
// Skip current subtree, move to next sibling
i += gap;
curr++;
} else {
// Go deeper into current subtree
i++;
curr *= 10;
}
}
return curr;
}
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 ES6+ Solution
/**
* Find k-th smallest number in lexicographical order
* @param {number} n - Upper bound
* @param {number} k - Target position
* @return {number} - K-th smallest number
*/
const 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) {
const gap = getGap(curr, curr + 1, n);
if (i + gap <= k) {
i += gap;
curr++;
} else {
i++;
curr *= 10;
}
}
return curr;
};
Python Solution with Type Hints
class Solution:
def findKthNumber(self, n: int, k: int) -> int:
"""
Find k-th smallest number in lexicographical order
Time: O(log²n), Space: O(1)
"""
def getGap(a: int, b: int, n: int) -> int:
"""Calculate numbers between prefix a and b"""
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
Java Solution
public class Solution {
public int findKthNumber(int n, int k) {
long curr = 1;
for (int i = 1; i < k;) {
long gap = getGap(curr, curr + 1, n);
if (i + gap <= k) {
i += gap;
curr++;
} else {
i++;
curr *= 10;
}
}
return (int) curr;
}
private long getGap(long a, long b, long n) {
long gap = 0;
while (a <= n) {
gap += Math.min(n + 1, b) - a;
a *= 10;
b *= 10;
}
return gap;
}
}
Advanced Test Cases
Comprehensive Test Suite
Small Range Tests
// Test Case 1: Minimum input
n = 1, k = 1 → Output: 1
Explanation: Only one number in range
// Test Case 2: Single digit range
n = 9, k = 5 → Output: 5
Explanation: [1,2,3,4,5,6,7,8,9] - direct indexing
// Test Case 3: Two digit boundary
n = 10, k = 2 → Output: 10
Explanation: [1,10,2,3,4,5,6,7,8,9]
Medium Range Tests
// Test Case 4: Classic example
n = 13, k = 2 → Output: 10
Explanation: [1,10,11,12,13,2,3,4,5,6,7,8,9]
// Test Case 5: Mid-range selection
n = 100, k = 50 → Output: 38
Explanation: Efficient subtree skipping
Large Scale Tests
// Test Case 6: Large n, small k
n = 1000000, k = 100 → Output: 1000
Explanation: Demonstrates O(log²n) efficiency
// Test Case 7: Large n, large k
n = 1000000, k = 500000 → Output: 5xxxxx
Explanation: Complex tree traversal patterns
Edge Case Analysis
Boundary Conditions
Minimum Values:
n = 1, k = 1Power of 10 Boundaries:
n = 10, 100, 1000Maximum k:
k = n(last lexicographical number)Large Numbers:
n = 10^9(constraint maximum)
Complexity Analysis
Time Complexity Breakdown
Overall Time Complexity: O(log²n)
Outer loop iterations: O(log n) - maximum tree depth
getGap function calls: O(log n) per call - digit levels to traverse
Combined: O(log n × log n) = O(log²n)
Space Complexity Analysis
Space Complexity: O(1)
Only using constant extra variables
No recursion stack or additional data structures
Optimal space efficiency for large inputs
Performance Comparison
Approach Time Complexity Space Complexity Scalability Brute Force Generation O(n) O(n) Poor for large n Recursive Tree Traversal O(log²n) O(log n) Good, but stack risk Iterative Gap Counting O(log²n) O(1) Excellent
Common Implementation Pitfalls and Solutions
Critical Mistakes to Avoid
Mistake 1: Integer Overflow
// Wrong: Using int for large calculations
int gap = getGap(curr, curr + 1, n);
// Correct: Using long to prevent overflow
long gap = getGap(curr, curr + 1, n);
Mistake 2: Incorrect Gap Calculation
// Wrong: Off-by-one errors in gap calculation
gap += min(n, b) - a; // Missing +1
// Correct: Proper range calculation
gap += min(n + 1, b) - a;
Mistake 3: Wrong Termination Condition
// Wrong: Infinite loop potential
while (i <= k) { // Should be i < k
// ... logic
}
Debugging Strategies
Strategy 1: Trace Small Examples
Walk through n = 13, k = 2 step by step:
Visualize the prefix tree structure
Calculate gaps manually for verification
Track variable changes at each iteration
Strategy 2: Validate Gap Function
Test getGap function independently:
// Test: getGap(1, 2, 13) should return 5
// Verify: [1, 10, 11, 12, 13] = 5 numbers
Strategy 3: Boundary Testing
Test with
k = 1(first element)Test with
k = n(last element)Test with powers of 10
Interview Preparation and Advanced Topics
Technical Interview Focus Points
What interviewers evaluate:
Problem comprehension: Understanding lexicographical vs numerical order
Algorithm design: Developing efficient tree traversal strategy
Mathematical reasoning: Gap counting logic and optimization
Code quality: Clean, bug-free implementation
Complexity analysis: Accurate time/space complexity assessment
Follow-up Questions and Extensions
Question 1: Memory-Constrained Environment
"How would you solve this with O(1) space complexity?"
Answer: Our solution already achieves O(1) space! The iterative approach with gap counting uses only constant extra memory.
Question 2: Range Queries
"Find all numbers between k1-th and k2-th positions efficiently."
vector<int> findKthRange(int n, int k1, int k2) {
vector<int> result;
// Adapt existing algorithm for range queries
return result;
}
Question 3: Lexicographical Ranking
"Given a number, find its lexicographical rank among [1, n]."
Question 4: Pattern Matching
"Find k-th number with specific digit patterns in lexicographical order."
Advanced Optimization Techniques
Technique 1: Precomputed Powers
// Cache powers of 10 for faster calculations
vector<long> powers = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
Technique 2: Iterative Deepening
// Optimize for cases where k is small
if (k <= 9) {
return k; // Direct return for single digits
}
Related LeetCode Problems and Learning Path
Prerequisite Problems
LeetCode 386: Lexicographical Numbers (Foundation)
LeetCode 89: Gray Code (Pattern Recognition)
LeetCode 60: Permutation Sequence (Combinatorial Counting)
Skills Development Path
Master basic lexicographical concepts (LeetCode 386)
Understand prefix trees and counting (LeetCode 440)
Apply to permutation problems (LeetCode 60)
Extend to complex combinatorics (Advanced problems)
Production Code Considerations
Error Handling and Validation
class Solution {
public:
int findKthNumber(int n, int k) {
// Input validation
if (k < 1 || k > n || n < 1) {
throw invalid_argument("Invalid input parameters");
}
// Handle edge cases
if (n == 1) return 1;
if (k == 1) return 1;
// Main algorithm
return findKthNumberInternal(n, k);
}
private:
int findKthNumberInternal(int n, int k) {
// Implementation as shown above
}
};
Performance Monitoring
#include <chrono>
int findKthNumberWithTiming(int n, int k) {
auto start = chrono::high_resolution_clock::now();
int result = findKthNumber(n, k);
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
cout << "Execution time: " << duration.count() << " microseconds" << endl;
return result;
}
Conclusion
LeetCode 440 represents a sophisticated application of mathematical optimization and algorithmic efficiency in competitive programming. The solution demonstrates several key principles:
Core Takeaways
Efficient counting can replace brute force generation
Tree visualization helps understand complex traversal patterns
Greedy decisions based on mathematical analysis optimize performance
Careful implementation prevents common pitfalls like integer overflow
Algorithm Design Principles
Divide and conquer through prefix tree partitioning
Mathematical optimization via gap counting
Iterative refinement avoiding recursion overhead
Boundary handling for edge cases and constraints
Real-World Applications
Database indexing with lexicographical ordering
File system navigation with dictionary-sorted paths
Search engine optimization with keyword ranking
Distributed systems with consistent hashing
The journey from understanding lexicographical order to implementing efficient tree traversal showcases the evolution from basic algorithms to advanced optimization techniques essential for senior software engineering roles.
If you learned something new today, consider following for more in-depth problem breakdowns and sharing this with your fellow devs. 👨💻
