Find first missing positive
- 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
<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
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
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
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
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]] 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 </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
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