DAY 78 - Finding Kth Missing Positive Integer

#leetcode #algorithms #codenewbie #coding

Hey Guys! It's day 78 and we are going to do another binary Search question. This problem is quite easy so I won't be going in depth about problem breakdown.

Question: Finding Kth Missing Positive Integer

Problem Description

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Return the kth positive integer that is missing from this array.

Example 1:

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 Overview

The problem can be solved efficiently using a binary search approach. The idea is to perform a binary search on the array to find the position where the kth missing positive integer should be located.

The approach involves the following steps:

Initialize two pointers left and right representing the search range. left starts from 0 and right starts from n - 1, where n is the size of the array.
Perform a binary search loop while left is less than or equal to right.
Calculate the midpoint mid of the search range.
Calculate the number of missing positive integers up to the mid index using missingCount = arr[mid] - (mid + 1).
Compare the missingCount with the given k:

If missingCount is less than k, it means that the kth missing positive integer is to the right of the mid index. In this case, update left = mid + 1.
If missingCount is greater than or equal to k, it means that the kth missing positive integer is to the left of or at the mid index. In this case, update right = mid - 1.

After the binary search loop, the kth missing positive integer can be found at k + right + 1.

Code:

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int n = arr.size();
        int left = 0, right = n - 1; // Initialize search range

    while (left <= right) { // Binary search loop
        int mid = (left + right) / 2; // Calculate midpoint
        int missingCount = arr[mid] - (mid + 1); // Calculate missing count

        if (missingCount < k) {
            // If missing count is less than k, move search to the right
            left = mid + 1;
        } else {
            // If missing count is greater than or equal to k, move search to the left
            right = mid - 1;
        }
    }

    // The kth missing integer is found at k + right + 1
    return k + right + 1;
    }
};