Really loved your explanation among all the other UA-cam channels present. I was only halfway through this video and it gave me enough confidence and clarity to solve this question by my own. Keep working on the good stuff 😄
Sir , Excellent video , but sir I did not understand why do we have to do x=abs(arr[i ]) ?? As we already put 1 for the negative values In the above loop ? So why we are again checking for positive??
Word Break can be solved using recursion + memoization: memo = {} wordDict = set(wordDict) def solve(s, wordDict): if s in wordDict: return True if s in memo: return memo[s] n = len(s) for i in range(1, n+1): if (s[:i] in wordDict) and solve(s[i:], wordDict): memo[s] = True return True memo[s] = False return False solve(s, wordDict)
there is an issue in your logic updated your logic, just checking the input array has 1 or not, in that case return 1 as an output public int FirstMissingPositive(int[] nums) { int smallestPositive = int.MaxValue; int length = nums.Length; // Step 1 - // loop entire array and mark the cells as 1 wherever cell value is N for (int i = 0; i < length; i++) { if(nums[i] > 0) { smallestPositive = Math.Min(smallestPositive, nums[i]); } if (nums[i] length) { nums[i] = 1; } } if (smallestPositive != 1) { return 1; } // Step 2 - // loop entire array and for each cell value -1 position, update to negetive to mark that value is present in range of 1-N for (int i = 0; i < length; i++) { int val = Math.Abs(nums[i]); if(nums[val - 1] > 0) nums[val - 1] *= -1; } // Step 3 - // loop entire array, any value as positive , that position + 1 is the missing element, if not found then N+1 is the missing element(eg- (1,2,3,4,5)=>O/p-6) for (int i = 0; i < length; i++) { if (nums[i] > 0) return i + 1; } return length + 1; }
I'm damn sure no better solution is available than this. Thanks a ton, sir ji! I was about to give up but found your video. Keep continue this series.
Really loved your explanation among all the other UA-cam channels present. I was only halfway through this video and it gave me enough confidence and clarity to solve this question by my own. Keep working on the good stuff 😄
Nice. I finally get it. Your visuals are perfect.
Glad it helped.
Hi, Did you stoped making newer videos on Leetcode problems?
Not stopped. But, will be adding selectively.
Great explanation Sir.Thanks
Sir , Excellent video , but sir I did not understand why do we have to do x=abs(arr[i ]) ??
As we already put 1 for the negative values In the above loop ? So why we are again checking for positive??
In between while traversing we are making the numbers -ve by multiplying with -1. So we take abs
How the heck can you figure this out without seeing the dang solution for O(1) time. Crazy
nice explanation
Thanks.
@Knowledge Center, It will be great if you can add leetcode problem "Word Break"
Word Break can be solved using recursion + memoization:
memo = {}
wordDict = set(wordDict)
def solve(s, wordDict):
if s in wordDict:
return True
if s in memo:
return memo[s]
n = len(s)
for i in range(1, n+1):
if (s[:i] in wordDict) and solve(s[i:], wordDict):
memo[s] = True
return True
memo[s] = False
return False
solve(s, wordDict)
there is an issue in your logic
updated your logic, just checking the input array has 1 or not, in that case return 1 as an output
public int FirstMissingPositive(int[] nums)
{
int smallestPositive = int.MaxValue;
int length = nums.Length;
// Step 1 -
// loop entire array and mark the cells as 1 wherever cell value is N
for (int i = 0; i < length; i++)
{
if(nums[i] > 0)
{
smallestPositive = Math.Min(smallestPositive, nums[i]);
}
if (nums[i] length)
{
nums[i] = 1;
}
}
if (smallestPositive != 1)
{
return 1;
}
// Step 2 -
// loop entire array and for each cell value -1 position, update to negetive to mark that value is present in range of 1-N
for (int i = 0; i < length; i++)
{
int val = Math.Abs(nums[i]);
if(nums[val - 1] > 0)
nums[val - 1] *= -1;
}
// Step 3 -
// loop entire array, any value as positive , that position + 1 is the missing element, if not found then N+1 is the missing element(eg- (1,2,3,4,5)=>O/p-6)
for (int i = 0; i < length; i++)
{
if (nums[i] > 0) return i + 1;
}
return length + 1;
}
so good!
Thanks.
But it will not work if there has already negative number or 0 in array
Sir ,I write the same code as you, it ran but my program didn't submit
why can't we use mex here ?
I think the problem really starts after 6 minutes
Please do make video on Leetcode Challenge September 29 - Word Break.
Awesome
Thanks.
4 for loops 😐...I did it using one while loop and one for loop.....
I did the same way could you elaborate your approach?
not working for input - 7,8,9, 11, 12
It will work as he wrote a condition to check if 1 is present or not..if 1 is not present then 1 is already returned
why are we converting negavtives into 1 .
Because we can't have negative index
It's very annoying questions