Kth Missing Positive Number

Problem: Given an array 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 = 6
Output: 10
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,14,15,...]. The 5th missing positive integer is 10.

Input: arr = [2,3,4,7,11], k = 10
Output: 15

Approach: Its very simple problem to solve. We can have many approaches like one of them could be we can have a loop from i = 1 to MAX(arr) basically we check for every positive integer from 1 to the maximum value of input array (last element of array), if 'i' is in the array or not if not we can reduce k by 1 and whenever we find k becomes 0, we return that i. Algorithm for this approach will look like:

• j = 0
• FOR i = 1 to MAX(arr) 
• IF i eq arr[j]
• j = j + 1
• ELSE
• --k
• IF k eq 0
• Return i
• return Last element of arr + k

That's all about this approach. Now do you see any problem? What if the maximum value of array and k is very large then array size and there is huge gaps between the consecutive elements in array, we will end up processing too much. 

In that case we can opt for an approach which depends on array length. You can understand the approach by just looking at the implementation.

Implementation in C#:

        public int FindKthPositive(int[] arr, int k)

        {

            if (arr == null)

            {

                return -1;

            }

            if (arr.Length == 0)

            {

                return k;

            }

            int currCountOfMissingNumber = arr[0] - 1;

            if (currCountOfMissingNumber >= k)

            {

                return k;

            }

            int remainingMissingNumbers = k - currCountOfMissingNumber;

            int prevMax = arr[0];

            for (int i = 1; i < arr.Length; ++i)

            {

                currCountOfMissingNumber += (arr[i] - (arr[i - 1] + 1));

                if (currCountOfMissingNumber >= k)

                {

                    break;

                }

                remainingMissingNumbers = k - currCountOfMissingNumber;

                prevMax = arr[i];

            }

            return prevMax + remainingMissingNumbers;

        }

Complexity: O(n)