Array - 50: Find first missing positive number in given array

Solution - 1: Using Sorting
- We sort the array
- Now start iterating the element: Ignore negative element & as soon as you get positive number, keep monitoring numbers
- Return first missing positive value

Time Complexity: O(nlog(n)), where n is number of values in array
Space Complexity: O(1)

Solution - 2:
- We'll start from 0th index & iterate all elements of all array
- If arr value is positive & less than equal to array lenegth & arr[i] is not arr[arr[i] - 1], then we need to swap the value, So we get the index value & put this value to it's correct index
- If it's not the case, then we move to next index.
- Now we traverse array values and if arr value is not equal to index + 1, retun first missing number (index + 1)

Time Complexity: O(n)
Space Complexity: O(1)

For more info, please see the video.

CHECK OUT CODING SIMPLIFIED

★☆★ VIEW THE BLOG POST: ★☆★

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 500+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★

★☆★ Send us mail at: ★☆★

[vaibhavjaiswal]

Can't believe this video has such less views. This is better than the Aman Dhattarwal's one. Sir, just please uploading these videos.

[amangupta]

I saw 2-3 videos of this particular question but still was not able to understand this. Your video explains it all. Thank you.

[codecrafts]

I have an approach. Let's make a set of all positive numbers present in given array. Then iterate a new loop. In the loop, if any consecutive number doesn't match, break it. The point where it was broken, the value of i is the answer

[ronanhughes]

I tell you what, you programmers are clever as fuck but by Jesus can you not simply explain anything without throwing in random numbers for no reason or other answers to other questions that aren’t anything to do with the question in mind 😂

[shouvikdatta]

Why did you you use "else i++ "?
Can I write directly i++? Inside the while loop...

[rajeshvenkatraman]

what if the array is [ 100, 900, -100, 120] like this?

[surajrao]

but it is giving TLE sir for this method

[shyguy]

I couldn't understand the time complexity. Are you sure its O(n). It would be great help if you can explain the complexity part in details. In your example the loop runs 10 times even though you have only 7 elements. Could it happen that the loops runs about n*n times ? In an array where every elements have to swipe multiple times?

[divyanshsingh]

sir why didnt you code this in nLOGn?That is faster than O(n)?