Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1060.html

1060. Missing Element in Sorted Array

Level

Medium

Description

Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.

Example 1:

Input: A = [4,7,9,10], K = 1

Output: 5

Explanation:

The first missing number is 5.

Example 2:

Input: A = [4,7,9,10], K = 3

Output: 8

Explanation:

The missing numbers are [5,6,8,…], hence the third missing number is 8.

Example 3:

Input: A = [1,2,4], K = 3

Output: 6

Explanation:

The missing numbers are [3,5,6,7,…], hence the third missing number is 6.

Note:

  1. 1 <= A.length <= 50000
  2. 1 <= A[i] <= 1e7
  3. 1 <= K <= 1e8

Solution

If the array nums is empty, simply return k since all numbers are missing in nums.

If k is greater than or equal to the last number in nums, then only the numbers in nums are not missing and all the other numbers are missing, so the k-th missing number is k + nums[0] + nums.length - 1.

Otherwise, starting from the first letter in nums, check each number that is greater, and if a number is not in the array, then it is missing and decrease k by 1. The process ends until the end of nums is reached or k becomes 0. Finally, return the current number plus k.

  • class Solution {
        public int missingElement(int[] nums, int k) {
            if (nums == null || nums.length == 0)
                return k;
            int length = nums.length;
            if (k >= nums[length - 1])
                return k + nums[0] + length - 1;
            int num = nums[0];
            int index = 1;
            while (index < length && k > 0) {
                num++;
                if (num == nums[index])
                    index++;
                else
                    k--;
            }
            return num + k;
        }
    }
    
  • class Solution {
    public:
        int missingElement(vector<int>& nums, int k) {
            auto missing = [&](int i) {
                return nums[i] - nums[0] - i;
            };
            int n = nums.size();
            if (k > missing(n - 1)) {
                return nums[n - 1] + k - missing(n - 1);
            }
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (missing(mid) >= k) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            return nums[l - 1] + k - missing(l - 1);
        }
    };
    
  • class Solution:
        def missingElement(self, nums: List[int], k: int) -> int:
            def missing(i: int) -> int:
                return nums[i] - nums[0] - i
    
            n = len(nums)
            if k > missing(n - 1):
                return nums[n - 1] + k - missing(n - 1)
            l, r = 0, n - 1
            while l < r:
                mid = (l + r) >> 1
                if missing(mid) >= k:
                    r = mid
                else:
                    l = mid + 1
            return nums[l - 1] + k - missing(l - 1)
    
    
  • func missingElement(nums []int, k int) int {
    	missing := func(i int) int {
    		return nums[i] - nums[0] - i
    	}
    	n := len(nums)
    	if k > missing(n-1) {
    		return nums[n-1] + k - missing(n-1)
    	}
    	l, r := 0, n-1
    	for l < r {
    		mid := (l + r) >> 1
    		if missing(mid) >= k {
    			r = mid
    		} else {
    			l = mid + 1
    		}
    	}
    	return nums[l-1] + k - missing(l-1)
    }
    

All Problems

All Solutions