LeetCode — Kth Missing Positive Number

Problem Link: https://leetcode.com/problems/kth-missing-positive-number/

Photo by Paweł Czerwiński on Unsplash

Problem Description: Given an array arr of positive integers sorted in a
strictly increasing order, and an integer k.
Find the kth positive integer that is missing from this array.

Example:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Approach Used: Arrays, Mathematical

Explanation: In this question, we need to find the kth missing number. So we traverse the array and keep a track of the count of missing numbers until that element. If at any element the number of missing element crosses ‘k’ then we know that the kth missing number is between the current element and previous element. With a little bit of mathematics, we can find it. There can also be corner cases where the kth missing element lies after the last element or before the first element of the array. We need to take care of those cases also.
In the beginning, we will count the number of missing elements before the first element of the array and take care if it is a corner case.
After that, we will run a loop and check the number of missing elements between two adjacent elements. If adding it to total missing elements doesn’t exceed k then we will simply add it and proceed further. Otherwise, we will find the number of missing elements left from k after the previous element (k-total_missing_till_previous). We will then add this difference to the previous element and that’ll be our answer.

Code: (Java)

public int findKthPositive(int[] arr, int k) {
        //keep a count of total missign numbers
        int total_missing = 0;
        
        //if first element not 1 then some numbers missing from starting
        if(arr[0]!=1){
            //if more than 1 element than add it to total missing numbers
            if(arr.length>1)
                total_missing = arr[0]-1;
            else{
                //if only one element then
                //if k is more than current element missing element will be one more than k
                if(arr[0]<=k)
                    return k+1;
                
                //else k will be the answer
                return k;
            }
        }
        
        //if more than one element and there are k numbers missing before starting than k is the answer
        if(total_missing>=k)
            return k;
        
        for(int i=1; i<arr.length; i++){
            //find count of missing number between adjacent elements
            int current_missing=(arr[i]-arr[i-1]-1);
            
            //if it exceed k
            if(total_missing+current_missing>=k)
                //below formula will return kth missing element
                return arr[i-1]+(k-total_missing);
            
            //if it doesn't exceed k then add it to total missing
            total_missing+=current_missing;
        }
        
        //corner case: if kth missing element is beyond last element of array
        return arr[arr.length-1]+(k-total_missing);
    }

Complexity:
Space Complexity: O(1). Only using two integers to store missing count.
Time Complexity: O(n). In the worst case (if kth missing number is beyond the last element of array), we will have to traverse all the elements of the array.