1539. Kth Missing Positive Number

LeetCode 1539. Kth Missing Positive Number

Description

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

Find thekth 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

Tags

Array, Hash Table

Solution

We use a variable i to emulate traversing the array [1,2,3,...]. Also, we assign a pointer p at the first position of arr. We compare i and arr[p]. If i is smaller, it means that i is a missing number, so decrease k by 1. Otherwise, i catches arr[p]. Thus, we move p one step forward. We keep doing this comparison until k is 0. Finally, we return i - 1 (because there is an extra i++ after exiting from the loop).

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(1)$

Code

func findKthPositive(arr []int, k int) int {
	var i, p int
	for i = 1; k != 0; i++ {
		if p < len(arr) && i == arr[p] {
			p++
			continue
		}
		k--
	}
	return i - 1
}