Smallest positive missing number

Find the smallest positive missing number in the given array.
Example: [0, -10, 1, 3, -20], Ans = 2
Constrains:
1<=N<=10^6
-10^6<=Ai<=10^6

This question has been asked in companies like amazon, samsung, snapdeal etc.

To solve this question click here:(https://practice.geeksforgeeks.org/problems/smallest-positive-missing-number-1587115621/1)

Approach 1:
We can solve the problem naively by looping over all the positive integers and checking if each of them is present in the array or not. Whenever a number is not found in the array, we return it and break the algorithm. Time compexity:O(n^2)

Approach 2:
We can solve this problem in linear time by using hashing. We loop over all the positive numbers, and check if it is present in the array or not by using a lookup table or hash map in O(1) time. The first element not found in the array will be the answer.

JAVA CODE:

import java.util.*;
import java.util.HashSet;

public class Smallest_pos_missing_no {
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter a number:");
        int n=sc.nextInt();
        int[] arr=new int[n];
        System.out.println("Enter the elements of the array:");
        for(int i=0;i<n;i++)
        {
            arr[i]=sc.nextInt();
        }
       int res= smallest_pos(arr,n);
       System.out.println(res);
    }
    public static int smallest_pos(int arr[],int n)
    {
        HashSet<Integer> hash=new HashSet<Integer>();
        for(int i=0;i<n;i++)
        {
            hash.add(arr[i]);
        }
        for(int i=1;i<=n+1;i++)
        {
            if(!hash.contains(i))
            {
                return i;
            }
        }
        return -1;

    }
}

Comments

[Alex Lohr]

In JS, the solution would be filtering negative numbers and comparing to the index:

const smallestMissingPositiveNumber =
  (array) => array
    .filter(num => num >= 0)
    .find((num, idx) => num !== idx) - 1

Obviously, if the positive numbers don't start at zero, we need to find out the starting number and add that as difference.

[Alex Lohr]

Since filter already creates a new array, there's no need to destructure it.

The only "real world application" I can think of is usually job interviews.