Smallest positive number missing from an unsorted array | GeeksforGeeks

Our courses :

Please Like, Comment and Share the Video among your friends.

Install our Android App:

If you wish, translate into the local language and help us reach millions of other geeks:

Follow us on Facebook:

And Twitter:

Also, Subscribe if you haven't already! :)

[shahjadansari]

at 09:51 you are taking a new sub-size array for all positive elements, then how it will be O(1) space complexity there.

[inewmoon]

In my opinion, easiest way to have an extra space of n+2 and find missing smallest positive element in O(n) time complexity.
Steps:
1. take a Boolean array of size n+2 with default false value at each index.
2. Iterate the original array and skip the elements which are negative and if we encounter positive value we just update the second array with true using positive value as index for the second array only if positive value is less than or equal to n+1. (We are very sure that our answer will lie in 1 to n+1 range).
3. Simply iterate the second array from index 1 and if you encounter false value, break the loop, that index is your answer.
Time complexity - O(n+n)
Space complexity - O(n+2) but optimised (i.e. Boolean array) compared to integer array extra space.
Hope, this helps. 🤠

[aryan]

At 18:40 example. Suppose we have only 3 elements - 3, 1, 20, all positive. So the array we have been allotted is of size 3. Therefore, When we are trying to put negative signs on the numbers, we will not be able to mark for the number 3. Since index 3 will not be present in the original array. How can you, thereby increase index by 1 and then solve?

[biswadeepchoudhury]

One possible Approach -
• Create an empty set.
• Look for the target item in the set first.
If present increment the target by 1 and check again.
• If not present in the set, check each item in the list. If that item == target then increment the target by 1, else add it to the list.
• End processing once the target item is not present in the set and the list is fully traversed.
• Print the target.

given_list = [2, 3, -3, -2, -6, 1, 5]
l = len(given_list)
s = set()
tar = 1
j = 0
i = 0
while(tar > 0):
if tar not in s:
if(i != (l - 1)):
for i in range(j, l):
if(given_list[i] > 0):
if(given_list[i] == tar):
tar += 1
j = i + 1
break
else:
s.add(given_list[i])
else:
break
else:
tar += 1
print(tar)

[nagendravelpuri]

time taken but very good explanation sir!!!

[avinashavi]

In your space complexity is O(no of positive number) but the question is O(1)

[jaiho]

In this question you have taken extra array for positive elements, then how it is in O(1) extra space .

[AnuragKumar-zxew]

i my opinion, there is no need of any extra segregation function, as you are just putting negative no. in other array

[ganeshanand]

How is [-4, -2, 6, 7] a possible outcome. Index 1(0) is marked but there is no 1 in the array. Am I wrong or the example wrong?

[itsmathsforu]

This will not work if array starts with 0.-1 is out of index

[AmanGupta-wbyw]

From the solution given on gfg site, in the function findMissingPositive(arr + shift, size - shift) its sending arr+shift directly. Is that possible or we need to make another array ?

[ShlomoPongratz]

The algorithm with sort does not require O(1) space but O(logN) because of the stack requirement.

[khushipandey]

What if in an input 0 is also present.

[chandrakesh]

/*missing no= sum of all positive no. till max element of array - sum of all positive no. in array
*/
public class Main {
public static void main(String[] args) {
int[] a={1, -1, 0, 2, -2, -3, 3, -4, 4, -6};
int sum=0, max=a[0];
for(int i=0;i<a.length;i++){
sum=sum+ (a[i]>=0?a[i]:0);
if(max<a[i])
max=a[i];
}

System.out.println( max*(max+ 1)/2 -sum );
}
}

[akashmehra]

Good explanation ....got the approach 👍

[PrashantPatil.]

in simple words "you are wrong and you are making a of lot confusion"