K-TH MISSING POSITIVE NUMBER | LEETCODE 1539 | PYTHON SOLUTION
Vložit
- čas přidán 9. 07. 2024
- Channel Discord Community: / discord
Problem Link: leetcode.com/problems/kth-mis...
Today we are solving a fun and simple question that is really good for training your brain to think in an algorithmic way. It's First Missing Positive Number (Leetcode 1539).
TIMESTAMPS
00:00 Intro
00:08 Question Prompt
00:17 Examples
02:00 Solution Intuition
04:55 Coding
10:00 Time/Space Complexity
10:35 Outro - Věda a technologie
Thank you for making these videos. You are awesome!
Your vids and explanation are elite. Super easy to understand code, intuition explanations are straightforward, and your no BS attitude is refreshing. Thanks to your vids I actually managed to ace my Meta phone interview and am using your explanations to help study for the full loop.
If you find the time, could you cover Count and Say? That one has been KILLER to find a solution online not written by some crackhead mathematician or using var names that make sense. Thanks again for all you do!
Amazing explanation
It only needs a few lines of code and one simple while loop. You are over complicating this question. T:O(N) and S: O(1) def findKthPositive(self, arr: List[int], k: int) -> int:
i,j, count=1,0,0
while j
how about the binary search solution? this doesn't take advantage of the fact that the array is sorted
This is meant to be an easy questions for people new to LC. Binary Search solution is a bit tricky here and the linear scan is easier to understand for people just starting out with easy questions
@@crackfaang fair enough, I just feel like Meta interviewers will expect binary search solution.
@@armankhondker I agree. BST is what would be expected. Plus that'd make the question a medium. Also, this question is easy to understand in approach in BST but the final statement that actually returns the missing number isn't easy by any stretch. Most LC code will just put left + K but why it works has a lot of depth in it.
I think, i have a simpler version:
def findKthPositive(arr: List[int], k: int) -> int:
arr = set(arr)
max_num = max(arr)
not_found = []
for i in range(1, max_num+1):
if i not in arr:
not_found.append(i)
print(not_found)
if len(not_found) >= k:
return not_found[k-1]
else:
return max_num + (k - len(not_found))
Hey Thanks for the explanation!
How do you get to know this question was asked in facebook?
Leetcode premium gives you a list of questions asked by a company recently. It's user submitted based on their interviews but for Meta it's basically spot on
Can you solve the top Tiktok Question? Optimal Account Balancing
is there any reason binary search wasn't used?
It''s meant to be an easy question for people new to LC. Doing it with binary search would be overkill for someone new
Did you ever finish a coding interview early because you knew the answers to the questions already? Just eondering if that ever happens
Yea all the time. But you are expected to be fast. You have 20 minutes per question so you need to train yourself to be fast. You end up just asking the interviewer some questions or using the time to go to the bathroom/mental break
This solution will not be accepted in interview
Why on earth is this tagged easy
The solution is supposed to be simpler:
def findKthPositive(self, arr: List[int], k: int) -> int:
arr = set(arr)
max_num = max(arr)
not_found = []
for i in range(1, max_num+1):
if i not in arr:
not_found.append(i)
print(not_found)
if len(not_found) >= k:
return not_found[k-1]
else:
return max_num + (k - len(not_found))