Find the smallest positive number missing from an unsorted array.

Given an unsorted array arr[] with both positive and negative elements, the task is to find the smallest positive number missing from the array.

Find the smallest positive number missing from an unsorted array.

Note: You can modify the original array.

Examples:-

Input:  arr[] = {2, 3, 7, 6, 8, -1, -10, 15}

Output: 1

Input:  arr[] = { 2, 3, -7, 6, 8, 1, -10, 15 }

Output: 4

Input: arr[] = {1, 1, 0, -1, -2}

Output: 2

Naive Approach:-

A naive method to solve this problem is to search all positive integers, starting from 1 in the given array. 

Time Complexity:- O(N²) because we may have to search at most n+1 numbers in the given array.

Auxiliary Space:- O(1)

Smallest positive number missing from an unsorted array by Marking Elements:

The idea is to mark the elements which are present in the array then traverse over the marked array and return the first element which is not marked.

Follow the steps below to solve the problem:

• Create a list full of 0’s with the size of the max value of the given array. 
• Now, whenever we encounter any positive value in the original array, change the index value of the list to 1. 
• After that simply iterate through the modified list, the first 0 encountered, (index value + 1) should be the answer.

Below is the implementation of the above approach :-

Python3 Code:- 👇

# Python3 Program to find the smallest
# positive missing number
 
 
def solution(A):  # Our original array
 
    m = max(A)  # Storing maximum value
    if m < 1:
 
        # In case all values in our array are negative
        return 1
    if len(A) == 1:
 
        # If it contains only one element
        return 2 if A[0] == 1 else 1
    l = [0] * m
    for i in range(len(A)):
        if A[i] > 0:
            if l[A[i] - 1] != 1:
 
                # Changing the value status at the index of our list
                l[A[i] - 1] = 1
    for i in range(len(l)):
 
        # Encountering first 0, i.e, the element with least value
        if l[i] == 0:
            return i + 1
            # In case all values are filled between 1 and m
    return i + 2
 
 
# Driver Code
if __name__ == '__main__':
    arr = [0, 10, 2, -10, -20]
    print(solution(arr)) 

C++ Code :- 👇

// C++ implementation of the approach
#include 
using namespace std;
 
// Function to return the first missing positive number from
// the given unsorted array
int firstMissingPos(int A[], int n)
{
 
    // To mark the occurrence of elements
    bool present[n + 1] = { false };
 
    // Mark the occurrences
    for (int i = 0; i < n; i++) {
 
        // Only mark the required elements
        // All non-positive elements and the elements
        // greater n + 1 will never be the answer
        // For example, the array will be {1, 2, 3} in the
        // worst case and the result will be 4 which is n +
        // 1
        if (A[i] > 0 && A[i] <= n)
            present[A[i]] = true;
    }
 
    // Find the first element which didn't appear in the
    // original array
    for (int i = 1; i <= n; i++)
        if (!present[i])
            return i;
 
    // If the original array was of the type {1, 2, 3} in
    // its sorted form
    return n + 1;
}
 
// Driver code
int main()
{
 
    int arr[] = { 0, 10, 2, -10, -20 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << firstMissingPos(arr, size);
}
 
// This code is contributed by GeeksCodes (GeeksCodes) 

C Code :- 👇

// C implementation of the approach
#include 
#include 
 
// Function to return the first missing positive number from
// the given unsorted array
int firstMissingPos(int A[], int n)
{
 
    // To mark the occurrence of elements
    bool present[n + 1];
    for (int i = 0; i < n; i++)
        present[i] = false;
 
    // Mark the occurrences
    for (int i = 0; i < n; i++) {
 
        // Only mark the required elements
        // All non-positive elements and the elements
        // greater n + 1 will never be the answer
        // For example, the array will be {1, 2, 3} in the
        // worst case and the result will be 4 which is n +
        // 1
        if (A[i] > 0 && A[i] <= n)
            present[A[i]] = true;
    }
 
    // Find the first element which didn't appear in the
    // original array
    for (int i = 1; i <= n; i++)
        if (!present[i])
            return i;
 
    // If the original array was of the type {1, 2, 3} in
    // its sorted form
    return n + 1;
}
 
// Driver code
int main()
{
 
    int arr[] = { 0, 10, 2, -10, -20 };
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("%d", firstMissingPos(arr, size));
}
 
// This code is contributed by GeeksCodes (GeeksCodes) 

Java Code :- 👇

// Java Program to find the smallest positive missing number
import java.util.*;
public class GFG {
 
    static int solution(int[] A)
    {
        int n = A.length;
        // Let this 1e6 be the maximum element provided in
        // the array;
        int N = 1000010;
 
        // To mark the occurrence of elements
        boolean[] present = new boolean[N];
 
        int maxele = Integer.MIN_VALUE;
 
        // Mark the occurrences
        for (int i = 0; i < n; i++) {
 
            // Only mark the required elements
            // All non-positive elements and the elements
            // greater n + 1 will never be the answer
            // For example, the array will be {1, 2, 3} in
            // the worst case and the result will be 4 which
            // is n + 1
            if (A[i] > 0 && A[i] <= n)
                present[A[i]] = true;
 
            // find the maximum element so that if all the
            // elements are in order can directly return the
            // next number
            maxele = Math.max(maxele, A[i]);
        }
 
        // Find the first element which didn't
        // appear in the original array
        for (int i = 1; i < N; i++)
            if (!present[i])
                return i;
 
        // If the original array was of the
        // type {1, 2, 3} in its sorted form
        return maxele + 1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 0, 10, 2, -10, -20 };
        System.out.println(solution(arr));
    }
}
 
// This code is contributed by GeeksCodes (GeeksCodes) 

JavaScript Code :- 👇

// Javascript Program to find the smallest
// positive missing number
 
    function solution(A)
    {
        let n = A.length;
        // To mark the occurrence of elements
        let present = new Array(n+1);
         
         
        for(let i=0;i 0 && A[i] <= n)
            {
                present[A[i]] = true;
            }
        }
        // Find the first element which didn't
        // appear in the original array
 
        for (let i = 1; i <= n; i++)
        {
            if (!present[i])
            {
                return i;
            }
        }
        // If the original array was of the
        // type {1, 2, 3} in its sorted form
        return n + 1;
    }
     
    // Driver Code
    let arr = [0, 10, 2, -10, -20]
    document.write(solution(arr)); 

C# Code :- 👇

// C# Program to find the smallest
// positive missing number
using System;
using System.Linq;
 
class GFG {
    static int solution(int[] A)
    {
        // Our original array
 
        int m = A.Max(); // Storing maximum value
 
        // In case all values in our array are negative
        if (m < 1) {
            return 1;
        }
        if (A.Length == 1) {
 
            // If it contains only one element
            if (A[0] == 1) {
                return 2;
            }
            else {
                return 1;
            }
        }
        int i = 0;
        int[] l = new int[m];
        for (i = 0; i < A.Length; i++) {
            if (A[i] > 0) {
                // Changing the value status at the index of
                // our list
                if (l[A[i] - 1] != 1) {
                    l[A[i] - 1] = 1;
                }
            }
        }
 
        // Encountering first 0, i.e, the element with least
        // value
        for (i = 0; i < l.Length; i++) {
            if (l[i] == 0) {
                return i + 1;
            }
        }
 
        // In case all values are filled between 1 and m
        return i + 2;
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 0, 10, 2, -10, -20 };
        Console.WriteLine(solution(arr));
    }
}