Find Smallest Missing Positive Number-Using Visited Array

The visited array will help to track which integers from the original array were present. We note the matching place in the visited array for every positive number in the input array. We then search the visited array looking for the first unvisited point. The first unvisited index reveals the initial missing positive number.
We are simply noting numbers falling between 1 and n here.

C++

// C++ program to find the first missing positive number 
// using visited array

#include <iostream>
#include <vector>
using namespace std;

int missingNumber(vector<int> &arr) {
    int n = arr.size();

    // To mark the occurrence of elements
    vector<bool> vis(n, false);
    for (int i = 0; i < n; i++) {

        // if element is in range from 1 to n
        // then mark it as visited
        if (arr[i] > 0 && arr[i] <= n)
            vis[arr[i] - 1] = true;
    }

    // Find the first element which is unvisited
    // in the original array
    for (int i = 1; i <= n; i++) {
        if (!vis[i - 1]) {
            return i;
        }
    }

    // if all elements from 1 to n are visited
    // then n + 1 will be first positive missing number
    return n + 1;
}

int main() {

    vector<int> arr = {2, -3, 4, 1, 1, 7};
    cout << missingNumber(arr);
}

C

// C program to find the first missing positive number 
// using visited array

#include <stdio.h>

// Function to return the first missing positive number from
// the given unsorted array
int missingNumber(int *arr, int n) {
    // To mark the occurrence of elements
    int *vis = (int *)calloc(n, sizeof(int));
    for (int i = 0; i < n; i++) {
        // if element is in range from 1 to n
        // then mark it as visited
        if (arr[i] > 0 && arr[i] <= n)
            vis[arr[i] - 1] = 1;
    }

    // Find the first element which is unvisited
    // in the original array
    for (int i = 1; i <= n; i++) {
        if (!vis[i - 1]) {
            free(vis);
            return i;
        }
    }

    // if all elements from 1 to n are visited
    // then n+1 will be first positive missing number
    free(vis);
    return n + 1;
}

int main() {
    int arr[] = {2, -3, 4, 1, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", missingNumber(arr, n));
    return 0;
}

Java

// Java program to find the first missing positive number 
// using visited array

import java.util.Arrays;

class GfG {
    static int missingNumber(int[] arr) {
        int n = arr.length;

        // To mark the occurrence of elements
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; i++) {

            // if element is in range from 1 to n
            // then mark it as visited
            if (arr[i] > 0 && arr[i] <= n)
                vis[arr[i] - 1] = true;
        }

        // Find the first element which is unvisited
        // in the original array
        for (int i = 1; i <= n; i++) {
            if (!vis[i - 1]) {
                return i;
            }
        }

        // if all elements from 1 to n are visited
        // then n+1 will be first positive missing number
        return n + 1;
    }

    public static void main(String[] args) {
        int[] arr = {2, -3, 4, 1, 1, 7};
        System.out.println(missingNumber(arr));
    }
}

Python

# Python program to find the first missing positive number 
# using visited array

def missingNumber(arr):
    n = len(arr)

    # To mark the occurrence of elements
    vis = [False] * n
    for i in range(n):

        # if element is in range from 1 to n
        # then mark it as visited
        if 0 < arr[i] <= n:
            vis[arr[i] - 1] = True

    # Find the first element which is unvisited
    # in the original array
    for i in range(1, n + 1):
        if not vis[i - 1]:
            return i

    # if all elements from 1 to n are visited
    # then n+1 will be first positive missing number
    return n + 1

if __name__ == "__main__":
    arr = [2, -3, 4, 1, 1, 7]
    print(missingNumber(arr))

JavaScript

// JavaScript program to find the first missing positive number 
// using visited array

function missingNumber(arr) {
    let n = arr.length;

    // To mark the occurrence of elements
    let vis = new Array(n).fill(false);
    for (let i = 0; i < n; i++) {

        // if element is in range from 1 to n
        // then mark it as visited
        if (arr[i] > 0 && arr[i] <= n)
            vis[arr[i] - 1] = true;
    }

    // Find the first element which is unvisited
    // in the original array
    for (let i = 1; i <= n; i++) {
        if (!vis[i - 1]) {
            return i;
        }
    }

    // if all elements from 1 to n are visited
    // then n+1 will be first positive missing number
    return n + 1;
}

const arr = [2, -3, 4, 1, 1, 7];
console.log(missingNumber(arr));

Output

3