### View *Kth Missing Positive Number* on LeetCode

## Statistics

**Time Spent Coding**

15 minutes

**Time Complexity**

O(n + k) - Each element in the list must be visited on top of k elements if the entire list is increasing from 1 to n, resulting in the O(n + k) time complexity.

**Space Complexity**

O(n) - When converting a list to a set, the list is not replaced until the set is full created, resulting in the O(n) space complexity, but technically only a bit of extra space is created except for a brief moment.

**Runtime Beats**

92.14% of other submissions

## Explanation

The list is converted into a set, and then a for loop iterates from 1 to the length of the list plus k plus 1. This accommodates for all elements in every worst-case scenario. This allows for simple checks at each element, allowing the program to return the current number when k equals 0.

## Data Structure Used

**Hash Table (Set) -** An unordered container of non-repeating values.

**Visual Examples**

An array being transformed into a set, click to view

## Solution

1
2
3
4
5
6
7
8

class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
arr = set(arr)
for num in range(1, len(arr)+k+1):
if num not in arr:
k -= 1
if k == 0:
return num