The Problem
Given an array
arrof positive integers sorted in a strictly increasing order, and an integerk.Find the
kthpositive 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 <= 10001 <= arr[i] <= 10001 <= k <= 1000arr[i] < arr[j] for 1 <= i < j <= arr.length
My Tests
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
My Solution
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
Analysis
My Commentary
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.
If the 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.
Top comments (0)