Given an array
arrof positive integers sorted in a strictly increasing order, and an integer
kthpositive integer that is missing from this array.
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.
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.
1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length
import pytest from .Day6 import Solution s = Solution() @pytest.mark.parametrize( "arr,k,expected", [ ([2, 3, 4, 7, 11], 5, 9), ([1, 2, 3, 4], 2, 6), ([9, 10, 11, 12], 4, 4), (, 2, 2), (, 0, 0), ([3, 10], 2, 2), ], ) def test_find_kth_positive(arr, k, expected): assert s.findKthPositive(arr, k) == expected
from typing import List class Solution: def findKthPositive(self, arr: List[int], k: int) -> int: missing_numbers = 0 next_expected = 1 for x in arr: while x != next_expected: missing_numbers += 1 if missing_numbers == k: return next_expected next_expected += 1 next_expected += 1 if len(arr) > 0 and missing_numbers < k: return arr[-1] + (k - missing_numbers) return k
This one was actually OK. We needed to keep track of the number of missing positive numbers and keep track of the next expected positive number.
As we go through the list we increment the missing numbers as we find them and then set the next expected to the current number + 1.
I think I could have used a bit of math here to make this a lot faster but my brain is far too fried to figure that one out right now.
kth number goes beyond the bounds of the list we handle that later with
arr[-1] + (k - missing_numbers).
Finally, we just return
k. This only happens if the list is empty which we could and maybe should have checked for at top also.
There is a bit in that loop where I am doing
next_expected += 1 in 2 places which really irks me but I am out of time so leaving it as is.