DEV Community

loading...

Day 6 - Kth Missing Positive Number

ruarfff profile image Ruairí O'Brien ・2 min read

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.
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Analysis

Alt Text

Alt Text

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)

pic
Editor guide