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

11l

<lang 11l>V nums = [[1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12]]

L(l) nums

  L(n) 1..
     I n !C l
        print(l‘ -> ’n)
        L.break</lang>

Output:

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

Action!

<lang Action!>DEFINE PTR="CARD"

BYTE FUNC Contains(INT ARRAY a INT len,x)

 INT i

 FOR i=0 TO len-1
 DO
   IF a(i)=x THEN
     RETURN (1)
   FI
 OD

RETURN (0)

BYTE FUNC FindFirstPositive(INT ARRAY a INT len)

 INT res

 res=1
 WHILE Contains(a,len,res)
 DO
   res==+1
 OD

RETURN (res)

PROC PrintArray(INT ARRAY a INT len)

 INT i

 Put('[)
 FOR i=0 TO len-1
 DO
   IF i>0 THEN Put(' ) FI
   PrintI(a(i))
 OD
 Put('])

RETURN

PROC Test(PTR ARRAY arr INT ARRAY lengths INT count)

 INT ARRAY a
 INT i,len,first

 FOR i=0 TO count-1
 DO
   a=arr(i) len=lengths(i)
   PrintArray(a,len)
   Print(" -> ")
   first=FindFirstPositive(a,len)
   PrintIE(first)
 OD

RETURN

PROC Main()

 DEFINE COUNT="5"
 PTR ARRAY arr(COUNT)
 INT ARRAY
   lengths=[3 4 5 3 0],
   a1=[1 2 0],
   a2=[3 4 65535 1],
   a3=[7 8 9 11 12],
   a4=[65534 65530 65520]

 arr(0)=a1 arr(1)=a2 arr(2)=a3
 arr(3)=a4 arr(4)=a4
 Test(arr,lengths,COUNT)

RETURN</lang>

Output:

Screenshot from Atari 8-bit computer

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

APL

Works with: Dyalog APL

<lang APL>fmp ← ⊃(⍳1+⌈/)~⊢</lang>

Output:

      fmp¨ (1 2 0) (3 4 ¯1 1) (7 8 9 11 12)
3 2 1

AppleScript

Procedural

<lang applescript>local output, aList, n set output to {} repeat with aList in {{1, 2, 0}, {3, 4, -1, 1}, {7, 8, 9, 11, 12}}

   set n to 1
   repeat while (aList contains n)
       set n to n + 1
   end repeat
   set end of output to n

end repeat return output</lang>

Output:

<lang applescript>{3, 2, 1}</lang>

Functional

Defining the value required in terms of pre-existing generic primitives:

<lang applescript>--------------- FIRST MISSING NATURAL NUMBER -------------

-- firstGap :: [Int] -> Int on firstGap(xs)

   script p
       on |λ|(x)
           xs does not contain x
       end |λ|
   end script
   
   find(p, enumFrom(1))

end firstGap

---

TEST -------------------------

on run

   script test
       on |λ|(xs)
           showList(xs) & " -> " & (firstGap(xs) as string)
       end |λ|
   end script
   
   unlines(map(test, ¬
       {{1, 2, 0}, {3, 4, -1, 1}, {7, 8, 9, 11, 12}}))
   
   --> {1, 2, 0} -> 3
   --> {3, 4, -1, 1} -> 2
   --> {7, 8, 9, 11, 12} -> 1

end run

---

GENERIC ------------------------

-- enumFrom :: Enum a => a -> [a] on enumFrom(x)

   script
       property v : missing value
       on |λ|()
           if missing value is not v then
               set v to 1 + v
           else
               set v to x
           end if
           return v
       end |λ|
   end script

end enumFrom

-- find :: (a -> Bool) -> Gen [a] -> Maybe a on find(p, gen)

   -- The first match for the predicate p
   -- in the generator stream gen, or missing value
   -- if no match is found.
   set mp to mReturn(p)
   set v to gen's |λ|()
   repeat until missing value is v or (|λ|(v) of mp)
       set v to (|λ|() of gen)
   end repeat
   v

end find

-- intercalate :: String -> [String] -> String on intercalate(delim, xs)

   set {dlm, my text item delimiters} to ¬
       {my text item delimiters, delim}
   set s to xs as text
   set my text item delimiters to dlm
   s

end intercalate

-- map :: (a -> b) -> [a] -> [b] on map(f, xs)

   -- The list obtained by applying f
   -- to each element of xs.
   tell mReturn(f)
       set lng to length of xs
       set lst to {}
       repeat with i from 1 to lng
           set end of lst to |λ|(item i of xs, i, xs)
       end repeat
       return lst
   end tell

end map

-- mReturn :: First-class m => (a -> b) -> m (a -> b) on mReturn(f)

   -- 2nd class handler function lifted into 1st class script wrapper. 
   if script is class of f then
       f
   else
       script
           property |λ| : f
       end script
   end if

end mReturn

-- showList :: [a] -> String on showList(xs)

   script go
       on |λ|(x)
           x as string
       end |λ|
   end script
   "{" & intercalate(", ", map(go, xs)) & "}"

end showList

-- unlines :: [String] -> String on unlines(xs)

   -- A single string formed by the intercalation
   -- of a list of strings with the newline character.
   set {dlm, my text item delimiters} to ¬
       {my text item delimiters, linefeed}
   set s to xs as text
   set my text item delimiters to dlm
   s

end unlines</lang>

Output:

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

AutoHotkey

<lang 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

}</lang> Examples:<lang AutoHotkey>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</lang>

Output:

3, 2, 1, 1, 1

AWK

<lang AWK>

1. 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)

} </lang>

Output:

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

BASIC

<lang basic>10 DEFINT A-Z: DIM D(100) 20 READ X 30 FOR A=1 TO X 40 READ N 50 FOR I=1 TO N 60 READ D(I) 70 PRINT D(I); 80 NEXT I 90 PRINT "==>"; 100 M=1 110 FOR I=1 TO N 120 IF M<D(I) THEN M=D(I) 130 NEXT I 140 FOR I=1 TO M+1 150 FOR J=1 TO N 160 IF D(J)=I GOTO 200 170 NEXT J 180 PRINT I 190 GOTO 210 200 NEXT I 210 NEXT A 220 DATA 3 230 DATA 3, 1,2,0 240 DATA 4, 3,4,-1,1 250 DATA 5, 7,8,9,11,12</lang>

Output:

 1  2  0 ==> 3
 3  4 -1  1 ==> 2
 7  8  9  11  12 ==> 1

BCPL

<lang bcpl>get "libhdr"

let max(v, n) = valof $( let x = !v

   for i=1 to n-1
       if x<v!i do x := v!i
   resultis x

$)

let contains(v, n, el) = valof $( for i=0 to n-1

       if v!i=el resultis true
   resultis false

$)

let fmp(v, n) = valof

   for i=1 to max(v,n)+1
       unless contains(v,n,i) resultis i

let show(len, v) be $( for i=0 to len-1 do writef("%N ", v!i)

   writef("==> %N*N", fmp(v, len))

$)

let start() be $( show(3, table 1,2,0)

   show(4, table 3,4,-1,1)
   show(5, table 7,8,9,11,12)

$)</lang>

Output:

1 2 0 ==> 3
3 4 -1 1 ==> 2
7 8 9 11 12 ==> 1

BQN

<lang bqn>FMP ← ⊢(⊑(¬∊˜ )/⊢)1+(↕1+⌈´)

FMP¨ ⟨⟨1,2,0⟩,⟨3,4,¯1,1⟩,⟨7,8,9,11,12⟩⟩</lang>

Output:

⟨ 3 2 1 ⟩

CLU

<lang clu>contains = proc [T, U: type] (needle: T, haystack: U) returns (bool)

          where T has equal: proctype (T,T) returns (bool),
                U has elements: itertype (U) yields (T)
   for item: T in U$elements(haystack) do
       if item = needle then return(true) end
   end
   return(false)

end contains

fmp = proc [T: type] (list: T) returns (int)

     where T has elements: itertype (T) yields (int)
   n: int := 1
   while contains[int, T](n, list) do
       n := n + 1
   end
   return(n)

end fmp

start_up = proc ()

   si = sequence[int]
   ssi = sequence[si]
   po: stream := stream$primary_output()
   tests: ssi := ssi$[si$[1,2,0], si$[3,4,-1,1], si$[7,8,9,11,12]]
   
   for test: si in ssi$elements(tests) do
       for i: int in si$elements(test) do
           stream$puts(po, int$unparse(i) || " ")
       end
       stream$putl(po, "==> " || int$unparse(fmp[si](test)))
   end

end start_up</lang>

Output:

1 2 0 ==> 3
3 4 -1 1 ==> 2
7 8 9 11 12 ==> 1

F#

<lang fsharp> // 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 "" </lang>

Output:

3 2 1

Factor

<lang 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</lang>

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

FreeBASIC

<lang freebasic>function is_in( n() as integer, k as uinteger ) as boolean

   for i as uinteger = 1 to ubound(n)
       if n(i) = k then return true
   next i
   return false

end function

function fmp( n() as integer ) as integer

   dim as uinteger i = 1
   while is_in( n(), i )
       i+=1
   wend
   return i

end function

dim as integer a(1 to 3) = {1, 2, 0} dim as integer b(1 to 4) = {3, 4, -1, 1} dim as integer c(1 to 5) = {7, 8, 9, 11, 12}

print fmp(a()) print fmp(b()) print fmp(c())</lang>

Output:

3
2
1

Go

Translation of: Wren

<lang go>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))
   }

}</lang>

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

<lang Haskell>import Data.List (sort)

task :: Integral a => [a] -> a task = go . (0 :) . sort . filter (> 0)

 where
   go [x] = succ x
   go (w : xs@(x : _))
     | x == succ w = go xs
     | otherwise = succ w

main :: IO () main =

 print $
   map
     task
     [[1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12]]</lang>

Output:

[3,2,1]

Or simply as a filter over an infinite list: <lang haskell>---------- FIRST MISSING POSITIVE NATURAL NUMBER ---------

firstGap :: [Int] -> Int firstGap xs = head $ filter (`notElem` xs) [1 ..]

---

TEST -------------------------

main :: IO () main =

 (putStrLn . unlines) $
   fmap
     (\xs -> show xs <> " -> " <> (show . firstGap) xs)
     [ [1, 2, 0],
       [3, 4, -1, 1],
       [7, 8, 9, 11, 12]
     ]</lang>

and if xs were large, it could be defined as a set: <lang haskell>import Data.Set (fromList, notMember)

---

FIRST MISSING POSITIVE NATURAL NUMBER ---------

firstGap :: [Int] -> Int firstGap xs = head $ filter (`notMember` seen) [1 ..]

 where
   seen = fromList xs</lang>

Output:

Same output for notElem and notMember versions above:

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

J

The first missing positive can be no larger than 1 plus the length of the list.

Note that the {{ }} delimiters on definitions was introduced in J version 9.2

<lang J>fmp=: {{ {.y-.~1+i.1+#y }}S:0</lang>

Example use:

<lang J> fmp 1 2 0;3 4 _1 1; 7 8 9 11 12 3 2 1</lang>

JavaScript

<lang javascript>(() => {

   "use strict";

   // ---------- FIRST MISSING NATURAL NUMBER -----------

   // firstGap :: [Int] -> Int
   const firstGap = xs => {
       const seen = new Set(xs);

       return filterGen(
           x => !seen.has(x)
       )(
           enumFrom(1)
       )
       .next()
       .value;
   };

   // ---------------------- TEST -----------------------
   // main :: IO ()
   const main = () => [
           [1, 2, 0],
           [3, 4, -1, 1],
           [7, 8, 9, 11, 12]
       ]
       .map(xs => `${show(xs)} -> ${firstGap(xs)}`)
       .join("\n");

   // --------------------- GENERIC ---------------------

   // enumFrom :: Int -> [Int]
   const enumFrom = function* (x) {
       // A non-finite succession of
       // integers, starting with n.
       let v = x;

       while (true) {
           yield v;
           v = 1 + v;
       }
   };

   // filterGen :: (a -> Bool) -> Gen [a] -> Gen [a]
   const filterGen = p =>
       // A stream of values which are drawn
       // from a generator, and satisfy p.
       xs => {
           const go = function* () {
               let x = xs.next();

               while (!x.done) {
                   const v = x.value;

                   if (p(v)) {
                       yield v;
                   }
                   x = xs.next();
               }
           };

           return go(xs);
       };

   // show :: a -> String
   const show = x => JSON.stringify(x);

   // MAIN ---
   return main();

})();</lang>

Output:

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

jq

Works with: jq

Works with gojq, the Go implementation of jq

In case the target array is very long, it probably makes sense either to sort it, or to use a hash, for quick lookup. For the sake of illustration, we'll use a hash: <lang jq>

1. input: an array of integers

def first_missing_positive:

 INDEX(.[]; tostring) as $dict
 | first(range(1; infinite)
         | . as $n

| select($dict|has($n|tostring)|not) ) ;

def examples:

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

1. The task:

examples | "\(first_missing_positive) is missing from \(.)"</lang>

Output:

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

Julia

<lang 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

</lang>

Output:

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

Nim

Translation of: Julia

In order to avoid the O(n) search in arrays, we could use an intermediate set built from the sequence. But this is useless with the chosen examples.

<lang Nim>for a in [@[1, 2, 0], @[3, 4, -1, 1], @[7, 8, 9, 11, 12], @[-5, -2, -6, -1]]:

 for n in 1..int.high:
   if n notin a:
     echo a, " → ", n
     break</lang>

Output:

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

Perl

<lang 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;
 }</lang>

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

with javascript_semantics
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

Python

<lang python>First missing natural number

from itertools import count

1. firstGap :: [Int] -> Int

def firstGap(xs):

   First natural number not found in xs
   return next(x for x in count(1) if x not in xs)

1. ------------------------- TEST -------------------------
2. main :: IO ()

def main():

   First missing natural number in each list
   print('\n'.join([
       f'{repr(xs)} -> {firstGap(xs)}' for xs in [
           [1, 2, 0],
           [3, 4, -1, 1],
           [7, 8, 9, 11, 12]
       ]
   ]))

1. MAIN ---

if __name__ == '__main__':

   main()</lang>

Output:

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

QBasic

Works with: QBasic

Works with: QuickBasic version 4.5

<lang qbasic>DECLARE FUNCTION isin (n(), k) DECLARE FUNCTION fmp (n())

DIM a(3) FOR x = 1 TO UBOUND(a): READ a(x): NEXT x DIM b(4) FOR x = 1 TO UBOUND(b): READ b(x): NEXT x DIM c(5) FOR x = 1 TO UBOUND(c): READ c(x): NEXT x

PRINT fmp(a()) PRINT fmp(b()) PRINT fmp(c()) Sleep END

DATA 1,2,0 DATA 3,4,-1,1 DATA 7,8,9,11,12

FUNCTION fmp (n())

   j = 1
   WHILE isin(n(), j)
       j = j + 1
   WEND
   fmp = j

END FUNCTION

FUNCTION isin (n(), k)

   FOR i = LBOUND(n) TO UBOUND(n)
       IF n(i) = k THEN isin = 1
   NEXT i

END FUNCTION</lang>

Output:

3
2
1

Raku

<lang perl6>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], []</lang>

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. <lang ring>/*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. */</lang>

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

<lang ring>nums = [[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 n = 1 to len(nums)

     see "the smallest missing positive integer for "
     ? (arrayToStr(nums[n]) + ": " + fmp(nums[n]))

next

func fmp(ary)

     if len(ary) > 0
           for m = 1 to max(ary) + 1
                 if find(ary, m) < 1 return m ok
           next ok return 1

func arrayToStr(ary)

     res = "[" s = ","
     for n = 1 to len(ary)
           if n = len(ary) s = "" ok
           res += "" + ary[n] + s
     next return res + "]"</lang>

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
the smallest missing positive integer for [1,2,3,4,5]: 6
the smallest missing positive integer for [-6,-5,-2,-1]: 1
the smallest missing positive integer for [5,-5]: 1
the smallest missing positive integer for [-2]: 1
the smallest missing positive integer for [1]: 2
the smallest missing positive integer for []: 1

Ruby

<lang ruby>nums = [1,2,0], [3,4,-1,1], [7,8,9,11,12] puts nums.map{|ar|(1..).find{|candidate| !ar.include?(candidate) }}.join(", ")</lang>

Output:

3, 2, 1

True BASIC

<lang qbasic>FUNCTION isin (n(), k)

   FOR i = LBOUND(n) TO UBOUND(n)
       IF n(i) = k THEN LET isin = 1
   NEXT i

END FUNCTION

FUNCTION fmp (n())

   LET j = 1
   DO WHILE isin(n(), j) = 1
      LET j = j + 1
   LOOP
   LET fmp = j

END FUNCTION

DIM a(3) FOR x = 1 TO UBOUND(a)

   READ a(x)

NEXT x DIM b(4) FOR x = 1 TO UBOUND(b)

   READ b(x)

NEXT x DIM c(5) FOR x = 1 TO UBOUND(c)

   READ c(x)

NEXT x

PRINT fmp(a()) PRINT fmp(b()) PRINT fmp(c())

DATA 1,2,0 DATA 3,4,-1,1 DATA 7,8,9,11,12 END</lang>

Wren

Library: Wren-sort

<lang ecmascript>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))")</lang>

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