This approach involves iterating through the array and maintaining a counter for missing positive integers. We start with the first positive number, which is 1, and determine if it is missing by comparing it to the current element in the array. If the number is missing, we decrement our k value. When k reaches zero, we have found our k-th missing number.
Time Complexity: O(n + k), where n is the length of the array. Space Complexity: O(1), as we are using constant extra space.
1public class Solution {
2 public int FindKthPositive(int[] arr, int k) {
3 int missing_count = 0;
4 int current = 1;
5 int i = 0;
6 while (missing_count < k) {
7 if (i < arr.Length && arr[i] == current) {
8 i++;
9 } else {
10 missing_count++;
11 if (missing_count == k) return current;
12 }
13 current++;
14 }
15 return -1; // this line is never reached
16 }
17 public static void Main(string[] args) {
18 int[] arr = {2, 3, 4, 7, 11};
19 Solution solution = new Solution();
20 Console.WriteLine(solution.FindKthPositive(arr, 5));
21 }
22}The C# solution works in the same way as the other implementations. It iterates over the array and checks each number against expected ones, counting missing numbers until it finds the k-th missing number.
By using binary search, a more efficient solution can be developed that reduces unnecessary checks. The key observation is that the number of missing integers before arr[i] can be calculated as arr[i] - (i + 1), which helps in deducing the position of the k-th missing number without iterating through every integer.
Time Complexity: O(log n), Space Complexity: O(1).
1function findKthPositive(arr, k) {
2 let left = 0, right = arr.length - 1;
3 while (left <= right) {
4 let mid = left + ((right - left) >> 1);
5 if (arr[mid] - (mid + 1) < k) {
6 left = mid + 1;
7 } else {
8 right = mid - 1;
9 }
10 }
11 return left + k;
12}
13
14let arr = [2, 3, 4, 7, 11];
15let k = 5;
16console.log(findKthPositive(arr, k));This JavaScript implementation also utilizes binary search to quickly find the k-th missing integer. It calculates how many numbers are missing up to a certain point and adjusts the search range accordingly.