Day 6 - Kth Missing Positive Number

January LeetCoding Challenge 2021 (33 Part Series)

1 Day1 – Check Array Formation Through Concatenation
2 Week 1 Bonus – Palindrome Permutation
… 29 more parts…
3 Day 2 Find a Corresponding Node of a Binary Tree in a Clone of That Tree
4 Day 3 – Beautiful Arrangement
5 Day 4 – Merge Two Sorted Lists
6 Day 5 – Remove Duplicates from Sorted List II
7 Day 6 – Kth Missing Positive Number
8 Day 7 – Longest Substring Without Repeating Characters
9 Day 8 – Check If Two String Arrays are Equivalent
10 Day 9 – Word Ladder
11 Day 10 – Create Sorted Array through Instructions
12 Day 11 – Merge Sorted Array
13 Day 12 – Add Two Numbers
14 Day 13 – Boats to Save People
15 Day 14 – Minimum Operations to Reduce X to Zero
16 Week 2 Bonus – Find Root of N-Ary Tree
17 Day 15 – Get Maximum in Generated Array
18 Day 16 – Kth Largest Element in an Array
19 Day 17 – Count Sorted Vowel Strings
20 Day 18 – Max Number of K-Sum Pairs
21 Week 3 Bonus – Nested List Weight Sum
22 Day 19 – Longest Palindromic Substring
23 Day 20 – Valid Parentheses
24 Day 21 – Find the Most Competitive Subsequence
25 Day 22 – Determine if Two Strings Are Close
26 Day 23 – Sort the Matrix Diagonally
27 Day 24 – Merge k Sorted Lists
28 Day 25 – Check If All 1’s Are at Least Length K Places Away
29 Day 28 – Smallest String With A Given Numeric Value
30 Day 27 – Concatenation of Consecutive Binary Numbers
31 Day 29 – Vertical Order Traversal of a Binary Tree
32 Day 30 – Minimize Deviation in Array
33 Day 31 – Next Permutation

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.
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 = [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.
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.
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


<span>import</span> <span>pytest</span>
<span>from</span> <span>.Day6</span> <span>import</span> <span>Solution</span>
<span>s</span> <span>=</span> <span>Solution</span><span>()</span>
<span>@</span><span>pytest</span><span>.</span><span>mark</span><span>.</span><span>parametrize</span><span>(</span>
    <span>"arr,k,expected"</span><span>,</span>
    <span>[</span>
        <span>([</span><span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>7</span><span>,</span> <span>11</span><span>],</span> <span>5</span><span>,</span> <span>9</span><span>),</span>
        <span>([</span><span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>],</span> <span>2</span><span>,</span> <span>6</span><span>),</span>
        <span>([</span><span>9</span><span>,</span> <span>10</span><span>,</span> <span>11</span><span>,</span> <span>12</span><span>],</span> <span>4</span><span>,</span> <span>4</span><span>),</span>
        <span>([],</span> <span>2</span><span>,</span> <span>2</span><span>),</span>
        <span>([],</span> <span>0</span><span>,</span> <span>0</span><span>),</span>
        <span>([</span><span>3</span><span>,</span> <span>10</span><span>],</span> <span>2</span><span>,</span> <span>2</span><span>),</span>
    <span>],</span>
<span>)</span>
<span>def</span> <span>test_find_kth_positive</span><span>(</span><span>arr</span><span>,</span> <span>k</span><span>,</span> <span>expected</span><span>):</span>
    <span>assert</span> <span>s</span><span>.</span><span>findKthPositive</span><span>(</span><span>arr</span><span>,</span> <span>k</span><span>)</span> <span>==</span> <span>expected</span>
<span>import</span> <span>pytest</span>
<span>from</span> <span>.Day6</span> <span>import</span> <span>Solution</span>

<span>s</span> <span>=</span> <span>Solution</span><span>()</span>


<span>@</span><span>pytest</span><span>.</span><span>mark</span><span>.</span><span>parametrize</span><span>(</span>
    <span>"arr,k,expected"</span><span>,</span>
    <span>[</span>
        <span>([</span><span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>7</span><span>,</span> <span>11</span><span>],</span> <span>5</span><span>,</span> <span>9</span><span>),</span>
        <span>([</span><span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>],</span> <span>2</span><span>,</span> <span>6</span><span>),</span>
        <span>([</span><span>9</span><span>,</span> <span>10</span><span>,</span> <span>11</span><span>,</span> <span>12</span><span>],</span> <span>4</span><span>,</span> <span>4</span><span>),</span>
        <span>([],</span> <span>2</span><span>,</span> <span>2</span><span>),</span>
        <span>([],</span> <span>0</span><span>,</span> <span>0</span><span>),</span>
        <span>([</span><span>3</span><span>,</span> <span>10</span><span>],</span> <span>2</span><span>,</span> <span>2</span><span>),</span>
    <span>],</span>
<span>)</span>
<span>def</span> <span>test_find_kth_positive</span><span>(</span><span>arr</span><span>,</span> <span>k</span><span>,</span> <span>expected</span><span>):</span>
    <span>assert</span> <span>s</span><span>.</span><span>findKthPositive</span><span>(</span><span>arr</span><span>,</span> <span>k</span><span>)</span> <span>==</span> <span>expected</span>
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


<span>from</span> <span>typing</span> <span>import</span> <span>List</span>
<span>class</span> <span>Solution</span><span>:</span>
    <span>def</span> <span>findKthPositive</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>:</span> <span>List</span><span>[</span><span>int</span><span>],</span> <span>k</span><span>:</span> <span>int</span><span>)</span> <span>-></span> <span>int</span><span>:</span>
        <span>missing_numbers</span> <span>=</span> <span>0</span>
        <span>next_expected</span> <span>=</span> <span>1</span>
        <span>for</span> <span>x</span> <span>in</span> <span>arr</span><span>:</span>
            <span>while</span> <span>x</span> <span>!=</span> <span>next_expected</span><span>:</span>
                <span>missing_numbers</span> <span>+=</span> <span>1</span>
                <span>if</span> <span>missing_numbers</span> <span>==</span> <span>k</span><span>:</span>
                    <span>return</span> <span>next_expected</span>
                <span>next_expected</span> <span>+=</span> <span>1</span>
            <span>next_expected</span> <span>+=</span> <span>1</span>
        <span>if</span> <span>len</span><span>(</span><span>arr</span><span>)</span> <span>></span> <span>0</span> <span>and</span> <span>missing_numbers</span> <span><</span> <span>k</span><span>:</span>
            <span>return</span> <span>arr</span><span>[</span><span>-</span><span>1</span><span>]</span> <span>+</span> <span>(</span><span>k</span> <span>-</span> <span>missing_numbers</span><span>)</span>
        <span>return</span> <span>k</span>
<span>from</span> <span>typing</span> <span>import</span> <span>List</span>


<span>class</span> <span>Solution</span><span>:</span>
    <span>def</span> <span>findKthPositive</span><span>(</span><span>self</span><span>,</span> <span>arr</span><span>:</span> <span>List</span><span>[</span><span>int</span><span>],</span> <span>k</span><span>:</span> <span>int</span><span>)</span> <span>-></span> <span>int</span><span>:</span>
        <span>missing_numbers</span> <span>=</span> <span>0</span>
        <span>next_expected</span> <span>=</span> <span>1</span>

        <span>for</span> <span>x</span> <span>in</span> <span>arr</span><span>:</span>
            <span>while</span> <span>x</span> <span>!=</span> <span>next_expected</span><span>:</span>
                <span>missing_numbers</span> <span>+=</span> <span>1</span>
                <span>if</span> <span>missing_numbers</span> <span>==</span> <span>k</span><span>:</span>
                    <span>return</span> <span>next_expected</span>
                <span>next_expected</span> <span>+=</span> <span>1</span>
            <span>next_expected</span> <span>+=</span> <span>1</span>

        <span>if</span> <span>len</span><span>(</span><span>arr</span><span>)</span> <span>></span> <span>0</span> <span>and</span> <span>missing_numbers</span> <span><</span> <span>k</span><span>:</span>
            <span>return</span> <span>arr</span><span>[</span><span>-</span><span>1</span><span>]</span> <span>+</span> <span>(</span><span>k</span> <span>-</span> <span>missing_numbers</span><span>)</span>

        <span>return</span> <span>k</span>
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

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.

January LeetCoding Challenge 2021 (33 Part Series)

原文链接：Day 6 – Kth Missing Positive Number

展开阅读全文

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END