Find first missing positive
Given an integer array nums (which may or may not be sorted), find the smallest missing positive integer.
- Task
- Example
- nums = [1,2,0], [3,4,-1,1], [7,8,9,11,12]
- output = 3, 2, 1
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>
- 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 ⟩
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
Go
<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
<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 of an infinite list:
<lang haskell>---------- FIRST MISSING POSITIVE NATURAL NUMBER ---------
firstGap :: [Int] -> Int firstGap xs = head $ filter (`notElem` xs) [1 ..]
TEST -------------------------
main :: IO () main =
mapM_ putStrLn $
fmap
(\xs -> show xs <> " -> " <> (show . firstGap) xs)
[ [1, 2, 0],
[3, 4, -1, 1],
[7, 8, 9, 11, 12]
]</lang>
- Output:
[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>
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>
- 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 \(.)"</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
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
<lang 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)</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
Python
<lang python>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()</lang>
- Output:
[1, 2, 0] -> 3 [3, 4, -1, 1] -> 2 [7, 8, 9, 11, 12] -> 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
Wren
<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