Welcome to Subscribe On Youtube

Question

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

 1539. Kth Missing Positive Number

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

 Find 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

Algorithm

o(N)

A linear solution is because the title gives an array of positive integers in ascending order, and the array theoretically starts from 1. So ideally, the relationship between the number nums[i] and its corresponding subscript i should be nums[i] = i + 1. So when scanning the input array, if the difference between the number and its corresponding subscript is greater than 1, it means that the number is missing in the middle. When the gap is greater than or equal to K, the Kth missing number is found.

o(logN)

Binary search. Because the input array is ordered, find the midpoint in mid, which is similar to the second approach, comparing the current number on the index with the difference between the index. If the difference is less than K, look for the right half of the array; otherwise, look for the left half of the array.

Code

Java

public class Kth_Missing_Positive_Number {

    class Solution_binary {
        public int findKthPositive(int[] arr, int k) {
            int left = 0;
            int right = arr.length;
            int mid = 0;
            while (left < right) {
                mid = left + (right - left) / 2;
                if (arr[mid] - mid >= k + 1) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left + k;
        }
    }

    class Solution {
        public int findKthPositive(int[] arr, int k) {
            int len = arr.length;
            for (int i = 0; i < len; i++) {
                if (arr[i] - i - 1 >= k) { // @note: not ==k , because could be multiple miss with a giant leap
                    return k + i;
                }
            }
            return k + len;
        }
    }
}

Java

  • class Solution {
    public int findKthPositive(int[] arr, int k) {
        List<Integer> list = new ArrayList<Integer>();
        int length = arr.length;
        int max = arr[length - 1];
        int index = 0;
        for (int i = 1; i < max; i++) {
            if (arr[index] == i)
                index++;
            else
                list.add(i);
        }
        int size = list.size();
        if (size >= k)
            return list.get(k - 1);
        else
            return max + k - size;
    }
}

  • // OJ: https://leetcode.com/problems/kth-missing-positive-number/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int findKthPositive(vector<int>& A, int k) {
        for (int i = 1, j = 0; i <= 2000; ++i) {
            if (j < A.size() && A[j] == i) ++j;
            else if (--k == 0) return i;
        }
        return -1;
    }
};

  • class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        if arr[0] > k:
            return k
        left, right = 0, len(arr)
        while left < right:
            mid = (left + right) >> 1
            if arr[mid] - mid - 1 >= k:
                right = mid
            else:
                left = mid + 1
        return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1)

All Problems

All Solutions