Kth Missing Positive Number Leetcode Solution

Table of Contents

Problem statement

In the problem “Kth Missing Positive Number” we are given an array arr, which is sorted in strictly increasing order and a number k.

Our task is to find out the Kth positive missing number in the array.

Example

arr = [1,2,3,4], k = 2

Explanation:

As in the given array, the first missing number is 5 and the second missing number is 6. So, the answer is 6.

Brute Force Approach for Kth Missing Positive Number Leetcode Solution

The brute force approach to solve this problem is as follows:

Traverse the array.
Every time we will calculate the number of missing numbers.
if the number of missing positive numbers is greater than or equal to k then we will return i+k.
After the complete traversal of the array if the number of missing elements is less than k then we will return the size of the array+k.

Implementation

C++ code for Kth Missing Positive Number

#include <bits/stdc++.h> 
using namespace std; 
    int findKthPositive(vector<int>& arr, int k) {
        for(int i=0;i<arr.size();i++)
        {
            int x=arr[i]-(i+1);
            if(x>=k)
                return i+k;
        }
        return arr.size()+k;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4};
 int k=2;
 int ans=findKthPositive(arr,k);
 cout<<ans<<endl;
 return 0;
}

Java code for Kth Missing Positive Number

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int findKthPositive(int[] arr, int k) {
        for(int i=0;i<arr.length;i++)
        {
            int x=arr[i]-(i+1);
            if(x>=k)
                return i+k;
        }
        return arr.length+k;
    }   
  public static void main(String[] args) {
        int [] arr = {1,2,3,4};
        int k=2;
        int ans=findKthPositive(arr,k); 
        System.out.println(ans);
  }
}

Complexity Analysis of Kth Missing Positive Number Leetcode Solution

Time complexity

The time complexity of the above code is O(n) because we are using a linear search that takes O(n) time in the worst case. Here n is the length of the given array.

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answer.

Binary Search Approach for Kth Missing Positive Number Leetcode Solution

The time complexity of the above algorithm is O(n) because we may need to traverse the complete array in the worst case. We can improve the time complexity of the solution using a binary search in place of linear search.

let’s first define the range of our search for binary search. So start will be index 0 and end will be the last index of the given array.
We will find the mid index then we will check if the number of missing positive numbers is less than k:
1. then start will become mid+1.
2. else end will become mid.
return end+k.