## DEV Community is a community of 615,123 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 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

``````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.

## Discussion (0) 