#1539 - Kth Missing Positive Number

Easy • View on LeetCode • View on GitHub

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.

Solution

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var findKthPositive = function(arr, k) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const count = arr[mid] - mid - 1;

    if (count < k) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return left + k;
};