LeetCode-in-Java

1539. Kth Missing Positive Number

Easy

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 5^th 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 2^nd 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

Solution

public class Solution {
    public int findKthPositive(int[] arr, int k) {
        int missed = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i == 0) {
                missed += arr[0] - 1;
                if (missed >= k) {
                    return k;
                }
            } else {
                missed += arr[i] - arr[i - 1] - 1;
                if (missed >= k) {
                    missed -= arr[i] - arr[i - 1] - 1;
                    int result = arr[i - 1];
                    while (missed++ < k) {
                        result++;
                    }
                    return result;
                }
            }
        }
        int result = arr[arr.length - 1];
        while (missed++ < k) {
            result++;
        }
        return result;
    }
}

This site is open source. Improve this page.