Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 6

Description

Kth Missing Positive Number

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.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Constraints:

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• arr[i] < arr[j] for 1 <= i < j <= arr.length

Follow up:

Could you solve this problem in less than O(n) complexity?

Solution

class Solution {
public:
  int findKthPositive(vector<int>& arr, int k) {
    int pos = 0;
    int prev = 0;
    arr.push_back(INT_MAX);
    while(k) {
      while(arr[pos] - prev == 1) {
        prev = arr[pos];
        pos += 1;
      }
      if(prev + k < arr[pos]) return prev+k;
      else {
        k -= arr[pos] - prev - 1;
        prev = arr[pos];
        pos += 1;
      }
    }
    return -1;
  }
};

// Accepted
// 84/84 cases passed (9 ms)
// Your runtime beats 33.58 % of cpp submissions
// Your memory usage beats 73.33 % of cpp submissions (9.6 MB)