Find first missing positive

Find first missing positive is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

Given an integer array nums   (which may or may not be sorted),   find the smallest missing positive integer.

Example

•    nums  =   [1,2,0], [3,4,-1,1], [7,8,9,11,12]
•   output =   3, 2, 1

AutoHotkey

First_Missing_Positive(obj){
    Arr := [], i := 0
    for k, v in obj
        Arr[v] := true
    while (++i<Max(obj*))
        if !Arr[i]{
            m := i
            break
        }
    m := m ? m : Max(obj*) + 1
    return m>0 ? m : 1
}

Examples:

nums := [[1,2,0], [3,4,-1,1], [7,8,9,11,12], [-4,-2,-3], []]
for i, obj in nums{
    m := First_Missing_Positive(obj)
    output .= m ", "
}
MsgBox % Trim(output, ", ")
return

Output:

3, 2, 1, 1, 1

AWK

 
# syntax: GAWK -f FIND_FIRST_MISSING_POSITIVE.AWK
BEGIN {
    PROCINFO["sorted_in"] = "@ind_num_asc"
    nums = "[1,2,0],[3,4,-1,1],[7,8,9,11,12]"
    printf("%s : ",nums)
    n = split(nums,arr1,"],?") - 1
    for (i=1; i<=n; i++) {
      gsub(/[\[\]]/,"",arr1[i])
      split(arr1[i],arr2,",")
      for (j in arr2) {
        arr3[arr2[j]]++
      }
      for (j in arr3) {
        if (j <= 0) {
          continue
        }
        if (!(1 in arr3)) {
          ans = 1
          break
        }
        if (!(j+1 in arr3)) {
          ans = j + 1
          break
        }
      }
      printf("%d ",ans)
      delete arr3
    }
    printf("\n")
    exit(0)
}
 

Output:

[1,2,0],[3,4,-1,1],[7,8,9,11,12] : 3 2 1

F#

 
// Find first missing positive. Nigel Galloway: February 15., 2021
let fN g=let g=0::g|>List.filter((<) -1)|>List.sort|>List.distinct
         match g|>List.pairwise|>List.tryFind(fun(n,g)->g>n+1) with Some(n,_)->n+1 |_->List.max g+1
[[1;2;0];[3;4;-1;1];[7;8;9;11;12]]|>List.iter(fN>>printf "%d "); printfn ""
 

Output:

3 2 1

Factor

USING: formatting fry hash-sets kernel math sequences sets ;
 
: first-missing ( seq -- n )
    >hash-set 1 swap '[ dup _ in? ] [ 1 + ] while ;
 
{ { 1 2 0 } { 3 4 1 1 } { 7 8 9 11 12 } { 1 2 3 4 5 }
{ -6 -5 -2 -1 } { 5 -5 } { -2 } { 1 } { } }
[ dup first-missing "%u ==> %d\n" printf ] each

Output:

{ 1 2 0 } ==> 3
{ 3 4 1 1 } ==> 2
{ 7 8 9 11 12 } ==> 1
{ 1 2 3 4 5 } ==> 6
{ -6 -5 -2 -1 } ==> 1
{ 5 -5 } ==> 1
{ -2 } ==> 1
{ 1 } ==> 2
{ } ==> 1

Go

Translation of: Wren

package main
 
import (
    "fmt"
    "sort"
)
 
func firstMissingPositive(a []int) int {
    var b []int
    for _, e := range a {
        if e > 0 {
            b = append(b, e)
        }
    }
    sort.Ints(b)
    le := len(b)
    if le == 0 || b[0] > 1 {
        return 1
    }
    for i := 1; i < le; i++ {
        if b[i]-b[i-1] > 1 {
            return b[i-1] + 1
        }
    }
    return b[le-1] + 1
}
 
func main() {
    fmt.Println("The first missing positive integers for the following arrays are:\n")
    aa := [][]int{
        {1, 2, 0}, {3, 4, -1, 1}, {7, 8, 9, 11, 12}, {1, 2, 3, 4, 5},
        {-6, -5, -2, -1}, {5, -5}, {-2}, {1}, {}}
    for _, a := range aa {
        fmt.Println(a, "->", firstMissingPositive(a))
    }
}

Output:

The first missing positive integers for the following arrays are:

[1 2 0] -> 3
[3 4 -1 1] -> 2
[7 8 9 11 12] -> 1
[1 2 3 4 5] -> 6
[-6 -5 -2 -1] -> 1
[5 -5] -> 1
[-2] -> 1
[1] -> 2
[] -> 1

Haskell

Translation of: Wren

import Data.List
 
task :: Integral a => [a] -> a
task = go . (0 : ) . sort . filter (> 0)
    where
    go [x] = x + 1
    go (w:xs@(x:_))
        | x == w + 1 = go xs
        | otherwise = w + 1
 
main = print $ map task [[1,2,0], [3,4,-1,1], [7,8,9,11,12]]

Output:

[3,2,1]

Julia

 
for array in [[1,2,0], [3,4,-1,1], [7,8,9,11,12], [-5, -2, -6, -1]]
    for n in 1:typemax(Int)
        !(n in array) && (println("$array  =>  $n"); break)
    end
end
 

Output:

[1, 2, 0]  =>  3
[3, 4, -1, 1]  =>  2
[7, 8, 9, 11, 12]  =>  1
[-5, -2, -6, -1]  =>  1

Perl

#!/usr/bin/perl -l
 
use strict;
use warnings;
use List::Util qw( first );
 
my @tests = ( [1,2,0], [3,4,-1,1], [7,8,9,11,12],
  [3, 4, 1, 1], [1, 2, 3, 4, 5], [-6, -5, -2, -1], [5, -5], [-2], [1], []);
 
for my $test ( @tests )
  {
  print "[ @$test ]  ==>  ",
    first { not { map { $_ => 1 } @$test }->{$_}  } 1 .. @$test + 1;
  }

Output:

[ 1 2 0 ]  ==>  3
[ 3 4 -1 1 ]  ==>  2
[ 7 8 9 11 12 ]  ==>  1
[ 3 4 1 1 ]  ==>  2
[ 1 2 3 4 5 ]  ==>  6
[ -6 -5 -2 -1 ]  ==>  1
[ 5 -5 ]  ==>  1
[ -2 ]  ==>  1
[ 1 ]  ==>  2
[  ]  ==>  1

Phix

procedure test(sequence s)
    for missing=1 to length(s)+1 do
        if not find(missing,s) then
            printf(1,"%v -> %v\n",{s,missing})
            exit
        end if
    end for
end procedure
papply({{1,2,0},{3,4,-1,1},{7,8,9,11,12},{1,2,3,4,5},{-6,-5,-2,-1},{5,-5},{-2},{1},{}} ,test)

Output:

{1,2,0} -> 3
{3,4,-1,1} -> 2
{7,8,9,11,12} -> 1
{1,2,3,4,5} -> 6
{-6,-5,-2,-1} -> 1
{5,-5} -> 1
{-2} -> 1
{1} -> 2
{} -> 1

Raku

say $_, " ==> ", (1..Inf).first( -> \n { n ∉ $_ } ) for
[ 1, 2, 0], [3, 4, 1, 1], [7, 8, 9, 11, 12], [1, 2, 3, 4, 5], [-6, -5, -2, -1], [5, -5], [-2], [1], []

Output:

[1 2 0] ==> 3
[3 4 1 1] ==> 2
[7 8 9 11 12] ==> 1
[1 2 3 4 5] ==> 6
[-6 -5 -2 -1] ==> 1
[5 -5] ==> 1
[-2] ==> 1
[1] ==> 2
[] ==> 1

REXX

This REXX version doesn't need to sort the elements of the sets,   it uses an associated array.

/*REXX program finds the smallest missing positive integer in a given list of integers. */
parse arg a                                      /*obtain optional arguments from the CL*/
if a='' | a=","  then a= '[1,2,0]  [3,4,-1,1]  [7,8,9,11,12]  [1,2,3,4,5]' ,
                         "[-6,-5,-2,-1]  [5,-5]  [-2]  [1]  []"    /*maybe use defaults.*/
say 'the smallest missing positive integer for the following sets is:'
say
    do j=1  for words(a)                         /*process each set  in  a list of sets.*/
    set= translate( word(a, j), ,'],[')          /*extract   a   "  from "   "   "   "  */
    #= words(set)                                /*obtain the number of elements in set.*/
    @.= .                                        /*assign default value for set elements*/
           do k=1  for #;  x= word(set, k)       /*obtain a set element  (an integer).  */
           @.x= x                                /*assign it to a sparse array.         */
           end   /*k*/
 
           do m=1  for #  until @.m==.           /*now, search for the missing integer. */
           end   /*m*/
    if @.m==''  then m= 1                        /*handle the case of a  "null"  set.   */
    say right( word(a, j), 40)   ' ───► '   m    /*show the set and the missing integer.*/
    end          /*j*/                           /*stick a fork in it,  we're all done. */

output   when using the default inputs:

the smallest missing positive integer for the following sets is:

                                 [1,2,0]  ───►  3
                              [3,4,-1,1]  ───►  2
                           [7,8,9,11,12]  ───►  1
                             [1,2,3,4,5]  ───►  6
                           [-6,-5,-2,-1]  ───►  1
                                  [5,-5]  ───►  1
                                    [-2]  ───►  1
                                     [1]  ───►  2
                                      []  ───►  1

Ring

 
nums = [[1,2,0],[3,4,-1,1],[7,8,9,11,12]]
numnr = list(3)
numnr[1] = "[1,2,0]"
numnr[2] = "[3,4,-1,1]"
numnr[3] = "[7,8,9,11,12]"
 
for n = 1 to len(nums)
    sortNums = sort(nums[n])
    ln = len(sortNums)
    num = sortNums[ln]   
    for m = 1 to num + 1
        ind = find(nums[n],m)
        if ind < 1
           see "the smallest missing positive integer for " + numnr[n] + ": " + m + nl
           exit
        ok
    next
next
 

Output:

the smallest missing positive integer for [1,2,0]: 3
the smallest missing positive integer for [3,4,-1,1]: 2
the smallest missing positive integer for [7,8,9,11,12]: 1

Wren

Library: Wren-sort

import "/sort" for Sort
 
var firstMissingPositive = Fn.new { |a|
    var b = a.where { |i| i > 0 }.toList
    Sort.insertion(b)
    if (b.isEmpty || b[0] > 1) return 1
    var i = 1
    while (i < b.count) {
        if (b[i] - b[i-1] > 1) return b[i-1] + 1
        i = i + 1    
    }
    return b[-1] + 1
}
 
System.print("The first missing positive integers for the following arrays are:\n")
var aa = [ 
    [ 1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12], [1, 2, 3, 4, 5],
    [-6, -5, -2, -1], [5, -5], [-2], [1], []
] 
for (a in aa) System.print("%(a) -> %(firstMissingPositive.call(a))")

Output:

The first missing positive integers for the following arrays are:

[1, 2, 0] -> 3
[3, 4, -1, 1] -> 2
[7, 8, 9, 11, 12] -> 1
[1, 2, 3, 4, 5] -> 6
[-6, -5, -2, -1] -> 1
[5, -5] -> 1
[-2] -> 1
[1] -> 2
[] -> 1