Find first missing positive

From Rosetta Code
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[edit]

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
Output:
[1, 2, 0] -> 3
[3, 4, -1, 1] -> 2
[7, 8, 9, 11, 12] -> 1

Action![edit]

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

ALGOL 68[edit]

Uses the observation in the J sample that the maximum possible minimum missing positive integer is one more than the length of the list.

BEGIN # find the lowest positive integer not present in various arrays #
    # returns the lowest positive integer not present in r #
    PROC min missing positive = ( []INT r )INT:
         BEGIN
            []INT a = r[ AT 1 ]; # a is r wih lower bound 1 #
            # as noted in the J sample, the maximum possible minimum #
            # missing positive integer is one more than the length of the array # 
            # note the values between 1 and UPB a present in a #
            [ 1 : UPB a ]BOOL present;
            FOR i TO UPB a DO present[ i ] := FALSE OD;
            FOR i TO UPB a DO 
                INT ai = a[ i ];
                IF ai >= 1 AND ai <= UPB a THEN
                    present[ ai ] := TRUE
                FI
            OD;
            # find the lowest value not in present #
            INT result := UPB a + 1;
            BOOL found := FALSE;
            FOR i TO UPB a WHILE NOT found DO
                IF NOT present[ i ] THEN
                    found  := TRUE;
                    result := i
                FI
            OD;
            result
         END # min missing positive # ;
     print( ( " ", whole( min missing positive( ( 1, 2,  0         ) ), 0 ) ) );
     print( ( " ", whole( min missing positive( ( 3, 4, -1,  1     ) ), 0 ) ) );
     print( ( " ", whole( min missing positive( ( 7, 8,  9, 11, 12 ) ), 0 ) ) )
END
Output:
 3 2 1

APL[edit]

Works with: Dyalog APL
fmp  (1+⌈/)~⊢
Output:
      fmp¨ (1 2 0) (3 4 ¯1 1) (7 8 9 11 12)
3 2 1

AppleScript[edit]

Procedural[edit]

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
Output:
{3, 2, 1}


Functional[edit]

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

--------------- 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
Output:
{1, 2, 0} -> 3
{3, 4, -1, 1} -> 2
{7, 8, 9, 11, 12} -> 1

AutoHotkey[edit]

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[edit]

# 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

BASIC[edit]

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
Output:
 1  2  0 ==> 3
 3  4 -1  1 ==> 2
 7  8  9  11  12 ==> 1

BCPL[edit]

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)
$)
Output:
1 2 0 ==> 3
3 4 -1 1 ==> 2
7 8 9 11 12 ==> 1

BQN[edit]

FMP ← ⊢(⊑(¬∊˜ )/⊢)1+(↕1+⌈´)

FMP¨ ⟨⟨1,2,0⟩,⟨3,4,¯1,1⟩,⟨7,8,9,11,12⟩⟩
Output:
⟨ 3 2 1 ⟩

CLU[edit]

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
Output:
1 2 0 ==> 3
3 4 -1 1 ==> 2
7 8 9 11 12 ==> 1

F#[edit]

// 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[edit]

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

FreeBASIC[edit]

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())
Output:

3 2 1

Go[edit]

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[edit]

Translation of: Wren
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]]
Output:
[3,2,1]


Or simply as a filter over an infinite list:

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

and if xs were large, it could be defined as a set:

import Data.Set (fromList, notMember)

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

firstGap :: [Int] -> Int
firstGap xs = head $ filter (`notMember` seen) [1 ..]
  where
    seen = fromList xs
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[edit]

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

fmp=: {{ {.y-.~1+i.1+#y }}S:0

Example use:

   fmp 1 2 0;3 4 _1 1; 7 8 9 11 12
3 2 1

JavaScript[edit]

(() => {
    "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();
})();
Output:
[1,2,0] -> 3
[3,4,-1,1] -> 2
[7,8,9,11,12] -> 1

jq[edit]

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:

# 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];

# The task:
examples
| "\(first_missing_positive) is missing from \(.)"
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[edit]

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

Nim[edit]

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.

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
Output:
@[1, 2, 0] → 3
@[3, 4, -1, 1] → 2
@[7, 8, 9, 11, 12] → 1
@[-5, -2, -6, -1] → 1

Perl[edit]

#!/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[edit]

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[edit]

'''First missing natural number'''

from itertools import count


# 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)


# ------------------------- TEST -------------------------
# 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]
        ]
    ]))


# MAIN ---
if __name__ == '__main__':
    main()
Output:
[1, 2, 0] -> 3
[3, 4, -1, 1] -> 2
[7, 8, 9, 11, 12] -> 1


QBasic[edit]

Works with: QBasic
Works with: QuickBasic version 4.5
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
Output:
3
2
1


Raku[edit]

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[edit]

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[edit]

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 + "]"
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[edit]

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

True BASIC[edit]

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

Vlang[edit]

Translation of: go
fn first_missing_positive(a []int) int {
    mut b := []int{}
    for e in a {
        if e > 0 {
            b << e
        }
    }
    b.sort<int>()
    le := b.len
    if le == 0 || b[0] > 1 {
        return 1
    }
    for i in 1..le {
        if b[i]-b[i-1] > 1 {
            return b[i-1] + 1
        }
    }
    return b[le-1] + 1
}
 
fn main() {
    println("The first missing positive integers for the following arrays are:\n")
    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 {
        println("$a -> ${first_missing_positive(a)}")
    }
}
Output:
Same as go entry

Wren[edit]

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

XPL0[edit]

proc ShowMissing(Arr, Len);
int  Arr, Len, N, N0, I;
[N:= 1;
repeat  N0:= N;
        for I:= 0 to Len-1 do
            if Arr(I) = N then N:= N+1;
until   N = N0;
IntOut(0, N);  ChOut(0, ^ );
];

int I, Nums;
[for I:= 0 to 2 do
    [Nums:= [[1,2,0], [3,4,-1,1], [7,8,9,11,12], [0]];
    ShowMissing( Nums(I), (Nums(I+1)-Nums(I))/4 );
    ];
]
Output:
3 2 1