GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing leetcodejavascript.com — #1060 - Missing Element in Sorted Array - LeetCode JavaScript Solutions

Back to all solutions

#1060 - Missing Element in Sorted Array

Medium • View on LeetCode • View on GitHub

Array Binary Search

Problem Description

Given an integer array nums which is sorted in ascending order and all of its elements are unique and given also an integer k, return the kth missing number starting from the leftmost number of the array.

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var missingElement = function(nums, k) {
  const n = nums.length;

  if (k > getMissingCount(n - 1)) {
    return nums[n - 1] + k - getMissingCount(n - 1);
  }

  let left = 0;
  let right = n - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

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

  return nums[left - 1] + k - getMissingCount(left - 1);

  function getMissingCount(index) {
    return nums[index] - nums[0] - index;
  }
};

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.