1539. Kth Missing Positive Number
Tags:
Medium
Skills:
Binary Search
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Approach - Linear search
Time and space complexity
Solution - Linear search
1function findKthPositive(arr: number[], k: number): number {
2 let missing_count = 0;
3 let current = 1;
4 let index = 0;
5 while(missing_count < k) {
6 if(index < arr.length && arr[index] === current) {
7 index++
8 } else {
9 missing_count++;
10 if(missing_count === k) {
11 return current;
12 }
13 }
14 current++
15 }
16
17 return -1;
18
19};Approach - Binary Search
Phương pháp này tối ưu hơn bằng cách sử dụng tính chất của mảng sắp xếp
Time and space complexity
Solution
1function findKthPositive(arr: number[], k: number): number {
2 let left = 0;
3 let right = arr.length;
4
5 while(left < right) {
6 const mid= left + Math.floor((right - left) /2);
7 const missing = arr[mid] - (mid + 1);
8
9 if(missing >= k) {
10 right = mid
11 } else {
12 left = mid + 1
13 }
14 }
15
16 return left + k;
17};