Leetcode - Kth Missing Positive Number (Python)

January 2021 Leetcode Challenge
Leetcode - Kth Missing Positive Number #1539

[mohammadkareem]

this is O(N) in time complexity, you can do better by using Binary Search since the array is sorted, then time complexity would be O(logN) in average. Your solution in the interview will most likely end up with follow up question: can you do better?, so better to be prepared for it ;)

[almasabdrazak]

I don't know how, I checked solutions with fancy Math and Binary Search but yours makes more sense for me

[kartikeyaverma]

Thank you. This is way simpler than the ones in the discussion forum.

[pc]

I watch your videos everyday. Thanks a lot for your videos. They are very helpful 👌

[shuoliu]

I found very short solution:

class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
i = 0
miss = 0
while miss < k:
i += 1
if i not in arr:
miss += 1

return i


Some others say they are required to use binary though I don't know how to implement it for this task. Can you help?

[gauravkumar]

Can anyone help, what is wrong with my code.As I failed to submit in Leetcode.

class Solution(object):
def findKthPositive(self, arr, k):
"""
:type arr: List[int]
:type k: int
:rtype: int
"""
l2 = []
for i in range(1, 1001):
if i in arr:
pass
else:
l2.append(i)
if (k < 0 or k > len(l2)):
return "invalid data"
else:
return l2[k-1]/

s1= Solution()
l1= [1, 2, 3, 4]
max_val = s1.findKthPositive(l1, 2)
print(max_val)

[waleeddib]

Are you preparing for a FAANG interview?