Day 6 - Kth Missing Positive Number

The Problem

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

My Tests

Link to code

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.