查找给定序列中未出现的最小正整数

If the expected running time should be linear, you can't use a TreeSet, which sorts the input and therefore requires O(NlogN). Therefore you should use a HashSet, which requires O(N) time to add N elements.

Besides, you don't need 4 loops. It's sufficient to add all the positive input elements to a HashSet (first loop) and then find the first positive integer not in that Set (second loop).

int N = A.length;
Set<Integer> set = new HashSet<>();
for (int a : A) {
if (a > 0) {
set.add(a);
}
}
for (int i = 1; i <= N + 1; i++) {
if (!set.contains(i)) {
return i;
}
}

You're doing too much. You've create a TreeSet which is an order set of integers, then you've tried to turn that back into an array. Instead go through the list, and skip all negative values, then once you find positive values start counting the index. If the index is greater than the number, then the set has skipped a positive value.

int index = 1;
for(int a: set){
if(a>0){
if(a>index){
return index;
} else{
index++;
}
}
}
return index;

Updated for negative values.

A different solution that is O(n) would be to use an array. This is like the hash solution.

int N = A.length;
int[] hashed = new int[N];


for( int i: A){
if(i>0 && i<=N){
hashed[i-1] = 1;
}
}


for(int i = 0; i<N; i++){
if(hash[i]==0){
return i+1;
}
}
return N+1;

This could be further optimized counting down the upper limit for the second loop.

For the space complexity of O(1) and time complexity of O(N) and if the array can be modified then it could be as follows:

public int getFirstSmallestPositiveNumber(int[] arr) {
// set positions of non-positive or out of range elements as free (use 0 as marker)
for (int i = 0; i < arr.length; i++) {
if (arr[i] <= 0 || arr[i] > arr.length) {
arr[i] = 0;
}
}


//iterate through the whole array again mapping elements [1,n] to positions [0, n-1]
for (int i = 0; i < arr.length; i++) {
int prev = arr[i];
// while elements are not on their correct positions keep putting them there
while (prev > 0 && arr[prev - 1] != prev) {
int next = arr[prev - 1];
arr[prev - 1] = prev;
prev = next;
}
}


// now, the first unmapped position is the smallest element
for (int i = 0; i < arr.length; i++) {
if (arr[i] != i + 1) {
return i + 1;
}
}
return arr.length + 1;
}


@Test
public void testGetFirstSmallestPositiveNumber() {
int[][] arrays = new int[][]\{\{1,-1,-5,-3,3,4,2,8},
{5, 4, 3, 2, 1},
{0, 3, -2, -1, 1}};


for (int i = 0; i < arrays.length; i++) {
System.out.println(getFirstSmallestPositiveNumber(arrays[i]));
}
}

Output:

5

6

2

I find another solution to do it with additional storage,

/*
* if A = [-1,2] the solution works fine
* */
public static int solution(int[] A) {


int N = A.length;


int[] C = new int[N];


/*
* Mark A[i] as visited by making A[A[i] - 1] negative
* */
for (int i = 0; i < N; i++) {


/*
* we need the absolute value for the duplicates
* */
int j = Math.abs(A[i]) - 1;


if (j >= 0 && j < N && A[j] > 0) {
C[j] = -A[j];
}
}


for (int i = 0; i < N; i++) {


if (C[i] == 0) {
return i + 1;
}
}


return N + 1;
}

No need to store anything. No need for hashsets. (Extra memory), You can do it as you move through the array. However, The array has to be sorted. And we know the very most minimum value is 1

import java.util.Arrays;
class Solution {
public int solution(int[] A) {
Arrays.sort(A);
int min = 1;
/*
for efficiency — no need to calculate or access the
array object’s length property per iteration
*/
int cap = A.length;


        

for (int i = 0; i < cap; i++){
if(A[i] == min){
min++;
}
/*
can add else if A[i] > min, break;
as suggested by punit
*/
}
/*
min = ( min <= 0 ) ? 1:min;
which means: if (min <= 0 ){
min =1} else {min = min}
you can also do:
if min <1 for better efficiency/less jumps
*/
return min;
}
}

//My recursive solution:


class Solution {
public int solution(int[] A) {
return next(1, A);
}
public int next(int b, int[] A) {
for (int a : A){
if (b==a)
return next(++b, A);
}
return b;
}
}

Late joining the conversation. Based on:

https://codereview.stackexchange.com/a/179091/184415

There is indeed an O(n) complexity solution to this problem even if duplicate ints are involved in the input:

solution(A)
Filter out non-positive values from A
For each int in filtered
Let a zero-based index be the absolute value of the int - 1
If the filtered range can be accessed by that index  and  filtered[index] is not negative
Make the value in filtered[index] negative


For each index in filtered
if filtered[index] is positive
return the index + 1 (to one-based)


If none of the elements in filtered is positive
return the length of filtered + 1 (to one-based)


So an array A = [1, 2, 3, 5, 6], would have the following transformations:


abs(A[0]) = 1, to_0idx = 0, A[0] = 1, make_negative(A[0]), A = [-1,  2,  3,  5,  6]
abs(A[1]) = 2, to_0idx = 1, A[1] = 2, make_negative(A[1]), A = [-1, -2,  3,  5,  6]
abs(A[2]) = 3, to_0idx = 2, A[2] = 3, make_negative(A[2]), A = [-1, -2, -3,  5,  6]
abs(A[3]) = 5, to_0idx = 4, A[4] = 6, make_negative(A[4]), A = [-1, -2, -3,  5, -6]
abs(A[4]) = 6, to_0idx = 5, A[5] is inaccessible,          A = [-1, -2, -3,  5, -6]


A linear search for the first positive value returns an index of 3. Converting back to a one-based index results in solution(A)=3+1=4

Here's an implementation of the suggested algorithm in C# (should be trivial to convert it over to Java lingo - cut me some slack common):

public int solution(int[] A)
{
var positivesOnlySet = A
.Where(x => x > 0)
.ToArray();


if (!positivesOnlySet.Any())
return 1;


var totalCount = positivesOnlySet.Length;
for (var i = 0; i < totalCount; i++) //O(n) complexity
{
var abs = Math.Abs(positivesOnlySet[i]) - 1;
if (abs < totalCount && positivesOnlySet[abs] > 0) //notice the greater than zero check
positivesOnlySet[abs] = -positivesOnlySet[abs];
}


for (var i = 0; i < totalCount; i++) //O(n) complexity
{
if (positivesOnlySet[i] > 0)
return i + 1;
}


return totalCount + 1;
}

I think that using structures such as: sets or dicts to store unique values is not the better solution, because you end either looking for an element inside a loop which leads to O(N*N) complexity or using another loop to verify the missing value which leaves you with O(N) linear complexity but spending more time than just 1 loop.

Neither using a counter array structure is optimal regarding storage space because you end up allocating MaxValue blocks of memory even when your array only has one item.

So I think the best solution uses just one for-loop, avoiding structures and also implementing conditions to stop iteration when it is not needed anymore:

public int solution(int[] A) {
// write your code in Java SE 8
int len = A.length;
int min=1;
    

Arrays.sort(A);


if(A[len-1]>0)
for(int i=0; i<len; i++){
if(A[i]>0){
if(A[i]==min) min=min+1;
if(A[i]>min) break;
}
}
return min;
}

This way you will get complexity of O(N) or O(N * log(N)), so in the best case you are under O(N) complexity, when your array is already sorted

Try this code it works for me

import java.util.*;
class Solution {
public static int solution(int[] A) {
// write your code in Java SE 8
int m = Arrays.stream(A).max().getAsInt(); //Storing maximum value
if (m < 1) // In case all values in our array are negative
{
return 1;
}
if (A.length == 1) {


//If it contains only one element
if (A[0] == 1) {
return 2;
} else {
return 1;
}
}
int min = A[0];
int max= A[0];
int sm = 1;


HashSet<Integer> set = new HashSet<Integer>();


for(int i=0;i<A.length;i++){
set.add(A[i]);


if(A[i]<min){
min = A[i];
}
if(A[i]>max){
max = A[i];
}
}


if(min <= 0){
min = 1;
}


if(max <= 0){
max = 1;
}


boolean fnd = false;
for(int i=min;i<=max;i++){
if(i>0 && !set.contains(i)){
sm = i;
fnd = true;
break;
}
else continue;


}
if(fnd)
return sm;
else return max +1;
}


public static void main(String args[]){


Scanner s=new Scanner(System.in);


System.out.println("enter number of elements");


int n=s.nextInt();


int arr[]=new int[n];


System.out.println("enter elements");


for(int i=0;i<n;i++){//for reading array
arr[i]=s.nextInt();


}


int array[] = arr;


// Calling getMax() method for getting max value
int max = solution(array);
System.out.println("Maximum Value is: "+max);


}
}

The simplest way using while loop:

fun solution(A: IntArray): Int {
var value = 1
var find = false
while(value < A.size) {
val iterator = A.iterator()
while (iterator.hasNext()) {
if (value == iterator.nextInt()) {
find = true
value++
}
}
if (!find) {
break
} else {
find = false
}
}
return value
}

This is might help you, it should work fine!

public static int sol(int[] A)
{
boolean flag =false;
for(int i=1; i<=1000000;i++ ) {
for(int j=0;j<A.length;j++) {
if(A[j]==i) {
flag = false;
break;
}else {
flag = true;
}
}
if(flag) {
return i;
}
}
return 1;
}

package Consumer;




import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;


public class codility {
public static void main(String a[])
{
int[] A = {1,9,8,7,6,4,2,3};
int B[]= {-7,-5,-9};
int C[] ={1,-2,3};
int D[] ={1,2,3};
int E[] = {-1};
int F[] = {0};
int G[] = {-1000000};
System.out.println(getSmall(F));
}
public static int getSmall(int[] A)
{
int j=0;
if(A.length < 1 || A.length > 100000) return -1;
List<Integer> intList = Arrays.stream(A).boxed().sorted().collect(Collectors.toList());
if(intList.get(0) < -1000000 || intList.get(intList.size()-1) > 1000000) return -1;
if(intList.get(intList.size()-1) < 0) return 1;
int count=0;
for(int i=1; i<=intList.size();i++)
{
if(!intList.contains(i))return i;
count++;
}
if(count==intList.size()) return ++count;
return -1;
}
}

    public int solution(int[] A) {


int res = 0;
HashSet<Integer> list = new HashSet<>();


for (int i : A) list.add(i);
for (int i = 1; i < 1000000; i++) {
if(!list.contains(i)){
res = i;
break;
}
}
return res;
}

Python implementation of the solution. Get the set of the array - This ensures we have unique elements only. Then keep checking until the value is not present in the set - Print the next value as output and return it.

def solution(A):
# write your code in Python 3.6
a = set(A)
i = 1
while True:
if i in A:
i+=1
else:
return i
return i
pass

Works 100%. tested with all the condition as described.

//MissingInteger
public int missingIntegerSolution(int[] A) {
Arrays.sort(A);
long sum = 0;
for(int i=0; i<=A[A.length-1]; i++) {
sum += i;
}




Set<Integer> mySet = Arrays.stream(A).boxed().collect(Collectors.toSet());
Integer[] B = mySet.toArray(new Integer[0]);
if(sum < 0)
return 1;


for(int i=0; i<B.length; i++) {
sum -= B[i];
}


if(sum == 0)
return A[A.length-1] + 1;
else
return Integer.parseInt(""+sum);
}


int[] j = {1, 3, 6, 4, 1, 2,5};


System.out.println("Missing Integer : "+obj.missingIntegerSolution(j));

Output Missing Integer : 7

int[] j = {1, 3, 6, 4, 1, 2};
System.out.println("Missing Integer : "+obj.missingIntegerSolution(j));

Output Missing Integer : 5

This solution is in c# but complete the test with 100% score

public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
var positives = A.Where(x => x > 0).Distinct().OrderBy(x => x).ToArray();
if(positives.Count() == 0) return 1;
int prev = 0;
for(int i =0; i < positives.Count(); i++){


if(positives[i] != prev + 1){
return prev + 1;
}
prev = positives[i];
}
return positives.Last() + 1;
}

Here is my PHP solution, 100% Task Score, 100% correctness, and 100% performance. First we iterate and we store all positive elements, then we check if they exist,

function solution($A) {


$B = [];
foreach($A as $a){
if($a > 0) $B[] = $a;
}


$i = 1;
$last = 0;
sort($B);


foreach($B as $b){


if($last == $b) $i--; // Check for repeated elements
else if($i != $b) return $i;


$i++;
$last = $b;


}


return $i;
}

I think its one of the clears and simples functions here, the logic can be applied in all the other languages.

Simple way to get this done !!

public int  findNearestPositive(int array[])
{
boolean isNegative=false;
int number=0;
int value=0;


if(array[0]<=0 && array[array.length-1]<0)
{
return 1;




}


for(int i=0;i<array.length;i++)
{
value=i+1;
isNegative=false;


for(int j=0;j<array.length;j++)
{
if(value==array[j])
{
isNegative=true;


}


}


if(isNegative!=true)
{
if(number==0){


number=value;
}else if(value<number){
number=value;
}


}


}




if(number==0)
{


number=value+1;
}


return number;


}

I achieved 100% on this by the below solution in Python:-

def solution(A):
a=frozenset(sorted(A))
m=max(a)
if m>0:
for i in range(1,m):
if i not in a:
return i
else:
return m+1
else:
return 1

For JavaScript i would do it this way:

function solution(arr)
{
let minValue = 1;


arr.sort();


if (arr[arr.length - 1] > 0)
{
for (let i = 0; i < arr.length; i++)
{
if (arr[i] === minValue)
{
minValue = minValue + 1;
}
if (arr[i] > minValue)
{
break;
}
}
}


return minValue;
}

Tested it with the following sample data:

console.log(solution([1, 3, 6, 4, 1, 2]));
console.log(solution([1, 2, 3]));
console.log(solution([-1, -3]));

My solution in JavaScript, using the reduce() method

function solution(A) {
// the smallest positive integer = 1
if (!A.includes(1)) return 1;


// greater than 1
return A.reduce((accumulator, current) => {
if (current <= 0) return accumulator
const min = current + 1
return !A.includes(min) && accumulator > min ? min : accumulator;
}, 1000000)
}


console.log(solution([1, 2, 3])) // 4
console.log(solution([5, 3, 2, 1, -1])) // 4
console.log(solution([-1, -3])) // 1
console.log(solution([2, 3, 4])) // 1

https://codesandbox.io/s/the-smallest-positive-integer-zu4s2

<JAVA> Try this code-


private int solution(int[] A) {//Our original array


int m = Arrays.stream(A).max().getAsInt(); //Storing maximum value
if (m < 1) // In case all values in our array are negative
{
return 1;
}
if (A.length == 1) {


//If it contains only one element
if (A[0] == 1) {
return 2;
} else {
return 1;
}
}
int i = 0;
int[] l = new int[m];
for (i = 0; i < A.length; i++) {
if (A[i] > 0) {
if (l[A[i] - 1] != 1) //Changing the value status at the index of our list
{
l[A[i] - 1] = 1;
}
}
}
for (i = 0; i < l.length; i++) //Encountering first 0, i.e, the element with least value
{
if (l[i] == 0) {
return i + 1;
}
}
//In case all values are filled between 1 and m
return i+1;
}
Input: {1,-1,0} , o/p: 2
Input: {1,2,5,4,6}, o/p: 3
Input: {-1,0,-2}, o/p: 1

100% result solution in Javascript:

function solution(A) {
// only positive values, sorted
A = A.filter(x => x >= 1).sort((a, b) => a - b)


let x = 1


for(let i = 0; i < A.length; i++) {
// if we find a smaller number no need to continue, cause the array is sorted
if(x < A[i]) {
return x
}
x = A[i] + 1
}


return x
}

For Swift 4

public func solution(_ A : inout [Int]) -> Int {
let positive = A.filter { $0 > 0 }.sorted()
var x = 1
for val in positive {
// if we find a smaller number no need to continue, cause the array is sorted
if(x < val) {
return x
}
x = val + 1
}
return x
}

My code in Java, 100% result in Codility

import java.util.*;


class Solution {
public int solution(int[] arr) {


Arrays.sort(arr);


int smallest = 1;


for (int i = 0; i < arr.length; i++) {
if (arr[i] == smallest) {
smallest++;
}
}


return smallest;
}
}

My answer in Ruby

def smallest_pos_integer(arr)
sorted_array = arr.select {|x| x >= 1}.sort
res = 1


for i in (0..sorted_array.length - 1)
if res < sorted_array[i]
return res
end
res = sorted_array[i] + 1
end
res
end

My solution having 100% result in codility with Swift 4.

func solution(_ A : [Int]) -> Int {
let positive = A.filter { $0 > 0 }.sorted()
var x = 1
for val in positive{
if(x < val) {
return x
}
x = val + 1
}
return x
}

The shortest PHP solution

function solution($A) {
// write your code in PHP7.0
$lastNum = 1;
    

while(in_array($lastNum, $A)) {
$lastNum++;
}
    

return $lastNum;
}

This is my approach with Java. The time complexity of this answer is 2*O(N) because I iterate through Array A twice.

import java.util.HashMap;


public static final Integer solution(int[] A) {
HashMap<Integer, Integer> map = new HashMap<>(A.length); //O(n) space


for (int i : A) {
if (!map.containsKey(i)) {
map.put(i, i);
}
}


int minorPositive = 100000;
for (int i : A) {
if (!map.containsKey(i + 1)) {
if (i < minorPositive) {
minorPositive = i + 1;
}
}
}


if (minorPositive < 0){
minorPositive = 1;
}
return minorPositive;


}

Here's my solution in C++. It got a 100% score (100% correctness, 100% performance) (after multiple tries ;)). It relies on the simple principle of comparing its values to their corresponding index (after a little preprocessing such as sorting). I agree that your solution is doing too much; You don't need four loops.

The steps of my solution are basically:

1. Sort and remove any duplicates. There are two possible methods here, the first one utilizing std::sort, std::unique, and erase, while the second one takes advantage of std::set and the fact that a set sorts itself and disallows duplicates
2. Handle edge cases, of which there are quite a few (I missed these initially, causing my score to be quite low at first). The three edge cases are:
   • All ints in the original array were negative
   • All ints in the original array were positive and greater than 1
   • The original array had only 1 element in it
3. For every element, check if its value != its index+1. The first element for which this is true is where the smallest missing positive integer is. I.e. if vec.at(i) != i+1, then vec.at(i-1)+1 is the smallest missing positive integer.
4. If vec.at(i) != i+1 is false for all elements in the array, then there are no "gaps" in the array's sequence, and the smallest positive int is simply vec.back()+1 (the 4th edge case if you will).

And the code:

int solution(vector<int>& rawVec)
{
//Sort and remove duplicates: Method 1
std::sort(rawVec.begin(), rawVec.end());
rawVec.erase(std::unique(rawVec.begin(), rawVec.end()), rawVec.end());


//Sort and remove duplicates: Method 2
// std::set<int> s(rawVec.begin(), rawVec.end());
// rawVec.assign(s.begin(), s.end());


//Remove all ints < 1
vector<int> vec;
vec.reserve(rawVec.size());
for(const auto& el : rawVec)
{
if(el>0)
vec.push_back(el);
}


//Edge case: All ints were < 1 or all ints were > 1
if(vec.size()==0 or vec.at(0) != 1)
return 1;


//Edge case: vector contains only one element
if(vec.size()==1)
return (vec.at(0)!=1 ? 1 : 2);


for(int i=0; i<vec.size(); ++i)
{
if(vec.at(i) != i+1)
return vec.at(i-1)+1;
}
return vec.back()+1;
}

This code has been writen in Java SE 8

import java.util.*;


public class Solution {
public int solution(int[] A) {


int smallestPositiveInt = 1;


if(A.length == 0) {
return smallestPositiveInt;
}


Arrays.sort(A);


if(A[0] > 1) {
return smallestPositiveInt;
}


if(A[A.length - 1] <= 0 ) {
return smallestPositiveInt;
}


for(int x = 0; x < A.length; x++) {
if(A[x] == smallestPositiveInt) {
smallestPositiveInt++;
}
}


return smallestPositiveInt;
}
}

public static int solution(int[] A) {
Arrays.sort(A);
int minNumber = 1;
int length = A.length - 1;
int max = A[length];
Set < Integer > set = new HashSet < > ();
for (int i: A) {
if (i > 0) {
set.add(i);
}
}
for (int j = 1; j <= max + 1; j++) {
if (!set.contains(j)) {
minNumber = j;
break;
}
}
return minNumber;
}

This works very well for Java. It uses bitwise exclusive OR and assignment operator

class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
int sol = 0;
for(int val:A){
sol ^= val;
}
return sol;
}
}

My solution:

  public int solution(int[] A) {
int N = A.length;
Set<Integer> set = new HashSet<>();
for (int a : A) {
if (a > 0) {
set.add(a);
}
}
for (int index = 1; index <= N; index++) {
if (!set.contains(index)) {
return index;
}
}
return N + 1;
}

In C#, bur need improvement.

    public int solution(int[] A) {
int retorno = 0;
for (int i = 0; i < A.Length; i++)
{
int ultimovalor = A[i] + 1;
if (!A.Contains(ultimovalor))
{
retorno = (ultimovalor);
if (retorno <= 0) retorno = 1;
}
}
return retorno;
}

// you can also use imports, for example:
// import java.util.*;


// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");


class Solution {
public int solution(int[] A) {
int size=A.length;
int min=A[0];
for(int i=1;i<=size;i++){
boolean found=false;
for(int j=0;j<size;j++){
if(A[j]<min){min=A[j];}
if(i==A[j]){
found=true;
}
}
if(found==false){
return i;


}
}


if(min<0){return 1;}
return size+1;






}
}

In Kotlin with %100 score Detected time complexity: O(N) or O(N * log(N))

fun solution(A: IntArray): Int {
var min = 1
val b = A.sortedArray()
for (i in 0 until b.size) {
if (b[i] == min) {
min++
}
}
return min
}

def solution(A):
A = sorted(filter(lambda x: x >= 0, A))
if A is []:
return 1
for i in range(1, 100000):
if i not in A:
return i

100% result solution in Javascript:

function solution(A) {
let N,i=1;
A = [...new Set(A)]; // remove duplicated numbers form the Array
A = A.filter(x => x >= 1).sort((a, b) => a - b); //  remove negative numbers & sort array
while(!N){ // do not stop untel N get a value
if(A[i-1] != i){N=i}
i++;
}
return N;
}

Here is an efficient python solution:

def solution(A):
m = max(A)
if m < 1:
return 1


A = set(A)
B = set(range(1, m + 1))
D = B - A
if len(D) == 0:
return m + 1
else:
return min(D)

This solution runs in O(N) complexity and all the corner cases are covered.

   public int solution(int[] A) {
Arrays.sort(A);
//find the first positive integer
int i = 0, len = A.length;
while (i < len && A[i++] < 1) ;
--i;


//Check if minimum value 1 is present
if (A[i] != 1)
return 1;


//Find the missing element
int j = 1;
while (i < len - 1) {
if (j == A[i + 1]) i++;
else if (++j != A[i + 1])
return j;
}


// If we have reached the end of array, then increment out value
if (j == A[len - 1])
j++;
return j;
}

Here is the code in python with comments to understand the code - Codility 100% Missing Integer

Code-

def solution(A):
"""
solution at https://app.codility.com/demo/results/trainingV4KX2W-3KS/
100%
idea is to take temp array of max length of array items
for all positive use item of array as index and mark in tem array as 1 ie. present item
traverse again temp array if first found value in tem array is zero that index is the smallest positive integer
:param A:
:return:
"""
max_value = max(A)
if max_value < 1:
# max is less than 1 ie. 1 is the smallest positive integer
return 1
if len(A) == 1:
# one element with 1 value
if A[0] == 1:
return 2
# one element other than 1 value
return 1
# take array of length max value
# this will work as set ie. using original array value as index for this array
temp_max_len_array = [0] * max_value
for i in range(len(A)):
# do only for positive items
if A[i] > 0:
# check at index for the value in A
if temp_max_len_array[A[i] - 1] != 1:
# set that as 1
temp_max_len_array[A[i] - 1] = 1
print(temp_max_len_array)
for i in range(len(temp_max_len_array)):
# first zero ie. this index is the smallest positive integer
if temp_max_len_array[i] == 0:
return i + 1
# if no value found between 1 to max then last value should be smallest one
return i + 2




arr = [2, 3, 6, 4, 1, 2]
result = solution(arr)

This is my solution. First we start with 1, we loop over the array and compare with 2 elements from the array, if it matches one of the element we increment by 1 and start the process all over again.

private static int findSmallest(int max, int[] A) {


if (A == null || A.length == 0)
return max;


for (int i = 0; i < A.length; i++) {
if (i == A.length - 1) {
if (max != A[i])
return max;
else
return max + 1;
} else if (!checkIfUnique(max, A[i], A[i + 1]))
return findSmallest(max + 1, A);
}
return max;
}




private static boolean checkIfUnique(int number, int n1, int n2) {
return number != n1 && number != n2;
}

This is my solution written in ruby simple correct and efficient

def solution(arr)


sorted = arr.uniq.sort
last = sorted.last
return 1 unless last > 0


i = 1
sorted.each do |num|
next unless num > 0
return i unless num == i


i += 1
end
i


end

Here's my JavaScript solution which scored 100% with O(N) or O(N * log(N)) detected time complexity:

function solution(A) {
let tmpArr = new Array(1);


for (const currNum of A) {
if (currNum > arr.length) {
tmpArr.length = currNum;
}
tmpArr[currNum - 1] = true;
}


return (tmpArr.findIndex((element) => element === undefined) + 1) || (tmpArr.length + 1);
}

Java Solution - Inside de method solution

int N = A.length;


Set<Integer> set = new HashSet<>();
for (int a : A) {
if (a > 0) {
set.add(a);
}
}


if(set.size()==0) {
return N=1;
}


for (int i = 1; i <= N + 1; i++) {
if (!set.contains(i)) {
N= i;
break;
}
}
return N;

Solution in Scala with all test cases running:

Class Solution {


def smallestNumber(arrayOfNumbers: Array[Int]) = {
val filteredSet = arrayOfNumbers.foldLeft(HashSet.empty[Int]){(acc, next)
=> if(next > 0) acc.+(next) else acc}
getSmallestNumber(filteredSet)


}


@tailrec
private def getSmallestNumber(setOfNumbers: HashSet[Int], index: Int = 1):
Int = {
setOfNumbers match {
case emptySet if(emptySet.isEmpty) => index
case set => if(!set.contains(index)) index else getSmallestNumber(set,
index + 1)
}
}


}

My simple and (time) efficient Java solution:

import java.util.*;


class Solution {
public int solution(int[] A) {
Set<Integer> set=new TreeSet<>();
for (int x:A) {
if (x>0) {
set.add(x);
}
}


int y=1;
Iterator<Integer> it=set.iterator();
while (it.hasNext()) {
int curr=it.next();
if (curr!=y) {
return y;
}
y++;
}
return y;
}
}

Objective-C example:

 int solution(NSMutableArray *array) {
NSArray* sortedArray = [array sortedArrayUsingSelector: @selector(compare:)];
int x = 1;
for (NSNumber *number in sortedArray) {


if (number.intValue < 0) {
continue;
}
if (x < number.intValue){
return x;
}
x = number.intValue + 1;
}


return x;
}

I've not seen a C# solution that uses Linq yet... the following is the simplest way (I think) to get 100% pass on this test:

using System;
using System.Linq;


class Solution {
public int solution(int[] A) => Enumerable.Range(1, 100001).Except(A).Min();
}

However, I should note that whilst the above is simple, and will get 100% pass on the test, it's not the most efficient. For a more efficient Linq solution, something like the following will work better:

using System;
using System.Collections.Generic;


public static int solution(int[] A)
{
var set = new HashSet<int>(A);


return Enumerable.Range(1, A.Length + 1).First(i => !set.Contains(i));
}

Solution in JavaScript

function solution(A) {
let smallestInt = 1;


function existsInArray(val) {
return A.find((a) => a === val);
}


for (let index = smallestInt; index < 1000000; index++) {
if (existsInArray(index) && !existsInArray(index + 1) &&
existsInArray(smallestInt)) {
smallestInt = index + 1
}
}
return smallestInt;
}

This answer gives 100% in Python. Worst case complexity O(N).

The idea is that we do not care about negative numbers in the sequence, since we want to find the smallest positive integer not in the sequence A. Hence we can set all negative numbers to zero and keep only the unique positive values. Then we check iteratively starting from 1 whether the number is in the set of positive values of sequence A.

Worst case scenario, where the sequence is an arithmetic progression with constant difference 1, leads to iterating through all elements and thus O(N) complexity.

In the extreme case where all the elements of the sequence are negative (i.e. the maximum is negative) we can immediately return 1 as the minimum positive number.

def solution(A):
max_A=max(A)
B=set([a if a>=0 else 0 for a in A ])
b=1
if max_A<=0:
return(1)
else:
while b in B:
b+=1
return(b)

Here is a simple and fast code in PHP.

• Task Score: 100%
• Correctness: 100%
• Performance: 100%
• Detected time complexity: O(N) or O(N * log(N))

function solution($A) {
    

$x = 1;
    

sort($A);
    

foreach($A as $i){
        

if($i <=0) continue;
        

if($x < $i) return $x;
        

else $x = $i+1;
        

}
    

return $x;
}

Performance tests

Not the best C++ but it got 100% score https://app.codility.com/demo/results/demoCNNMBE-B5W/

// you can use includes, for example:
#include <algorithm>
#include <iostream>


// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;


template <class T>
bool allneg(const T start, const T end) {
T it;
for (it = start; it != end; it++) {
if (*it >= 0) return false;
}


return true;
}


int solution(vector<int> &A) {
if(A.empty()) throw std::invalid_argument("unexpected empty vector");


std::sort(A.begin(),A.end());
/*
for(size_t i = 0; i < A.size(); i++) {
std::cout << A[i] << ", ";
}*/
if(allneg(A.begin(),A.end())){
return 1;
}
int v = 1;
auto it = A.begin();
while(it!=A.end()){
if(std::binary_search(it,A.end(),v)){
v++;
} else {
return v;
}
it++;
}
return v;
}

Based on Fastest way to find smallest missing integer from list of integers and slightly faster than the above https://app.codility.com/demo/results/demoCJ7MDF-CDD/

int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
std::vector<bool> negative(1000000,false);
std::vector<bool> non_negative(1000000+1,false);
bool contain_negative = false;
bool contain_non_negative = false;
for(int a : A){
if(a<0) {
negative[-a] = true;
contain_negative = true;
} else {
non_negative[a] = true;
contain_non_negative = true;
}
}
int result = 1;
if(contain_negative && !contain_non_negative){
return result;
} else {
for(size_t i = 1; i < non_negative.size(); i++){
if(!non_negative[i]){
result = i;
break;
}
}
}
return result;
}

Swift with .reduce()

public func solution(_ A : inout [Int]) -> Int {
return A.filter { $0 > 0 }.sorted().reduce(1) { $0 < $1 ? $0 : $1 + 1}
}

100% solution in Swift, I found it here, it is really beautiful than my algo... No need to turn array as ordered, instead using dictionary [Int: Bool] and just check the positive item in dictionary.

public func solution(_ A : inout [Int]) -> Int {
var counter = [Int: Bool]()
for i in A {
counter[i] = true
}


var i = 1
while true {
if counter[i] == nil {
return i
} else {
i += 1
}
}
}

I tried it with Swift and got 100%.

public func solution(_ A : inout [Int]) -> Int {
// write your code in Swift 4.2.1 (Linux)
if A.count == 0 {
return 1
}
A = A.sorted()
if A[A.count - 1] <= 0 {
return 1
}
    

var temp = 1
    

for numb in A {
        

if numb > 0 {
            

if numb == temp {
temp += 1
}else if numb != (temp - 1) {
return temp
}
}
}
    

return temp
}

function solution(A = []) {
return (A && A
.filter(num => num > 0)
.sort((a, b) => a - b)
.reduce((acc, curr, idx, arr) =>
!arr.includes(acc + 1) ? acc : curr, 0)
) + 1;
}

solution(); // 1 solution(null); // 1 solution([]); // 1 solution([0, 0, 0]); // 1

My solution on Ruby

def solution(a)
p = {}
b = 1
a.each do |n|
p[n] = n
b = n if n > b
end


nb = b
(b-1).downto(1) do |n|
unless p[n]
nb = n
break
end
end
(nb == b) ? b+1 : nb
end


puts solution([1,3,5,4,1,2,6])
puts solution([1,3,6,4,1,2,5])
puts solution([1,2,3])

JS:

• filter to get positive non zero numbers from A array
• sort above filtered array in ascending order
• map to iterate loop of above stored result
  • if to check x is less than the current element then return
  • otherwise, add 1 in the current element and assign to x

function solution(A) {


let x = 1
    

A.filter(x => x >= 1)
.sort((a, b) => a - b)
.map((val, i, arr) => {
if(x < arr[i]) return
x = arr[i] + 1
})


return x
}


console.log(solution([3, 4, -1, 1]));
console.log(solution([1, 2, 0]));

The code below will run in O(N) time and O(N) space complexity. Check this codility link for complete running report.

The program first put all the values inside a HashMap meanwhile finding the max number in the array. The reason for doing this is to have only unique values in provided array and later check them in constant time. After this, another loop will run until the max found number and will return the first integer that is not present in the array.

   static int solution(int[] A) {
int max = -1;
HashMap<Integer, Boolean> dict = new HashMap<>();
for(int a : A) {
if(dict.get(a) == null) {
dict.put(a, Boolean.TRUE);
}
if(max<a) {
max = a;
}
}
for(int i = 1; i<max; i++) {
if(dict.get(i) == null) {
return i;
}
}
return max>0 ? max+1 : 1;
}

The code below is is simpler but my motive was to write for JavaScript, ES6 users:

function solution(A) {
   

let s = A.sort();
let max = s[s.length-1];
let r = 1;
   

// here if we have an array with [1,2,3] it should print 4 for us so I added max + 2
for(let i=1; i <= (max + 2); i++) {
r  = A.includes(i) ? 1 : i ;
if(r>1) break;
}
   

return r;
}

My Java solution got 100%. I feel this is simple and the complexity is O(n).

public int solution(int[] A) {
Integer s = 1;
List<Integer> list = new ArrayList<>();


for (int i : A) {
if (i>0) {
list.add(i);
}
}


Collections.sort(list);


for (int i : list) {
if (s < i) {
return s;
}
s = i + 1;
}


return s;
}

Let me know if we can improve this more.

This solution is in Javascript but complete the test with 100% score and less codes

function solution(A) {
let s = A.sort((a, b) => { return a - b })
let x = s.find(o => !s.includes(o+1) && o>0)
return ((x<0) || !s.includes(1)) ? 1 : x+1
}

in C#

static int solutionA(int[] A)
{
Array.Sort(A);


int minNumber = 1;


if(A.Max() < 0)
{
return minNumber;
}


for (int i = 0; i < A.Length; i++)
{
if (A[i] == minNumber)
{
minNumber++;
}
            

if (A[i] > minNumber)
{
break;
}
}


return minNumber;
}

100% Test Pass https://i.stack.imgur.com/FvPR8.png

In PHP I can achieve it from a few lines of code.

function solution($A) {
for($i=1; in_array($i,$A); $i++);
return $i;
}

Swift version using functions rather than an iterative approach

'The solution obtained perfect score' - Codility

This solution uses functions rather than an iterative approach. So the solution relies heavily on the language's optimizations. A similar approach could be done in Java such as using Java's set operations and other functions.

public func solution(_ A : inout [Int]) -> Int {
let positives = A.filter{ $0 > 0}
let max = positives.count <= 100_000 ? positives.count + 1 : 100_001
return Set(1...max).subtracting(A).min() ?? -1
}

1. Obtained all positive numbers from the source array.
2. Obtained all possible results based on the positive count. Limited the set to 100k as stated in the problem. Added 1 in case the source array was a complete sequence.
3. Returned the minimum positive number after excluding the source array's elements from the set of all possible results.

Note: The function declaration was from Codility and inout was unneeded. Returning an integer did not allow for nil so -1 was used.

Rewrite the accepted answer with Swift. Hashset in Swift is Set. I think if index is required as return value then try to use Dictionary instead.

Passed with 100% score.

public func solution(_ A: [Int]) -> Int {
let n = A.count
var aSet = Set<Int>()
    

for a in A {
if a > 0 {
aSet.insert(a)
}
}
    

for i in 1...n+1 {
if !aSet.contains(i) {
return i
}
}
    

return 1
}

The below C++ solution obtained a 100% score. The theoretical complexity of the code is. Time Complexity : O(N) amortized due to hash set and Auxiliary Space complexity of O(N) due to use of hash for lookup in O(1) time.

#include<iostream>
#include<string>
#include<vector>
#include<climits>
#include<cmath>
#include<unordered_set>


using namespace std;


int solution(vector<int>& A)
{
if(!A.size())
return(1);


unordered_set<int> hashSet;
int maxItem=INT_MIN;
for(const auto& item : A)
{
hashSet.insert(item);
if(maxItem<item)
maxItem=item;
}


if(maxItem<1)
return(1);


for(int i=1;i<=maxItem;++i)
{
if(hashSet.find(i)==hashSet.end())
return(i);
}
return(maxItem+1);
}

You could simply use this, which is a variant of Insertion-Sort, without the need of Set, or sorting the whole array.

    public static int solution(int[] A) {
//we can choose only positive integers to enhance performance
A = Arrays.stream(A).filter(i -> i > 0).toArray();
for(int i=1; i<A.length; i++){
int v1 = A[i];
int j = i-1;
while (j > -1 && A[j] > v1) {
A[j + 1] = A[j];
j = j - 1;
}
A[j + 1] = v1;
if(A[i] - A[i-1] > 1){
return A[i] + 1;
}
}
return 1;
}

First let me explain about the algorithm down below. If the array contains no elements then return 1, Then in a loop check if the current element of the array is larger then the previous element by 2 then there is the first smallest missing integer, return it. If the current element is consecutive to the previous element then the current smallest missing integer is the current integer + 1.

    Array.sort(A);


if(A.Length == 0) return 1;


int last = (A[0] < 1) ? 0 : A[0];


for (int i = 0; i < A.Length; i++)
{
if(A[i] > 0){
if (A[i] - last > 1) return last + 1;
else last = A[i];
}
}


return last + 1;

Without sorting or extra memory. Time Complexity: O(N)

  public int solution(int[] A) {
for (int i = 0; i < A.length; i++) {
if (A[i] <= 0 || A[i] >= A.length) continue;
int cur = A[i], point;
while (cur > 0 && cur <= A.length && A[cur - 1] != cur) {
point = A[cur - 1];
A[cur - 1] = cur;
cur = point;
if (cur < 0 || cur >= A.length) break;
}
}
for (int i = 0; i < A.length; i++) {
if (A[i] != i+1) return i+1;
}
return A.length + 1;
}

My python solution 100% correctness

def solution(A):


if max(A) < 1:
return 1


if len(A) == 1 and A[0] != 1:
return 1


s = set()
for a in A:
if a > 0:
s.add(a)
  

  

for i in range(1, len(A)):
if i not in s:
return i


return len(s) + 1


assert solution([1, 3, 6, 4, 1, 2]) == 5
assert solution([1, 2, 3]) == 4
assert solution([-1, -3]) == 1
assert solution([-3,1,2]) == 3
assert solution([1000]) == 1

This my implementation in Swift 4 with 100% Score. It should be a pretty similar code in Java. Let me know what you think.

public func solution(_ A : inout [Int]) -> Int {
let B = A.filter({ element in
element > 0
}).sorted()


var result = 1
for element in B {
if element == result {
result = result + 1
} else if element > result {
break
}
}


return result
}

Below is my solution

int[] A = {1,2,3};
Arrays.sort(A);
Set<Integer> positiveSet = new HashSet<>();
for(int a: A) {
if(a>0) {
positiveSet.add(a);
}
}
for(int a: A) {
int res = a+1;
if(!positiveSet.contains(res)) {
System.out.println("result : "+res);
break;
}
}

JavaScript solution without sort, 100% score and O(N) runtime. It builds a hash set of the positive numbers while finding the max number.

function solution(A) {
set = new Set()
let max = 0
for (let i=0; i<A.length; i++) {
if (A[i] > 0) {
set.add(A[i])
max = Math.max(max, A[i])
}
}


for (let i=1; i<max; i++) {
if (!set.has(i)) {
return i
}
}
return max+1
}

This is the solution in C#:

using System;
// you can also use other imports, for example:
using System.Collections.Generic;


// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");


class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
int N = A.Length;
HashSet<int> set =new HashSet<int>();
foreach (int a in A) {
if (a > 0) {
set.Add(a);
}
}
for (int i = 1; i <= N + 1; i++) {
if (!set.Contains(i)) {
return i;
}
}
return N;
}
}

I figured an easy way to do this was to use a BitSet.

• just add all the positive numbers to the BitSet.
• when finished, return the index of the first clear bit after bit 0.

public static int find(int[] arr) {
BitSet b = new BitSet();
for (int i : arr) {
if (i > 0) {
b.set(i);
}
}
return b.nextClearBit(1);
}

C# solution:

    public int solution(int[] A)
{
int result = 1;


// write your code in Java SE 8
foreach(int num in A)
{
if (num == result)
result++;


while (A.Contains(result))
result++;
}


return result;
}

I was thinking about another approach (JS, JavaScript) and got this results that score 66% because of performance issues:

    const properSet = A.filter((item) => { return item > 0 });
let biggestOutsideOfArray = Math.max(...properSet);
    

if (biggestOutsideOfArray === -Infinity) {
biggestOutsideOfArray = 1;
} else {
biggestOutsideOfArray += 1;
}
    

for (let i = 1; i <= biggestOutsideOfArray; i++) {
if(properSet.includes(i) === false) {
return i;
}
}
}

How about just playing around with loops.

import java.util.Arrays;
public class SmallestPositiveNumber {


public int solution(int[] A) {
Arrays.sort(A);
int SPI = 1;


if(A.length <= 1) return SPI;


for(int i=0; i<A.length-1; i++){


if((A[i+1] - A[i]) > 1)
{
return A[i] + 1;
}
}
return A[A.length-1]+1;
}
}

Here is my solution on Java:

public int solution(int[] A) {


int smallestPositiveInteger = 1;
        

Arrays.sort(A);


if(A[0] <= 0) return smallestPositiveInteger;


for( int i = 0; i < A.length; i++){
if(A[i] == smallestPositiveInteger)
smallestPositiveInteger++;
}


return smallestPositiveInteger;
}

With 100% Accuracy on codility in Java

    public int solution(int[] A) {
// write your code in Java SE 8


Arrays.sort(A);
int i=1;
for (int i1 = 0; i1 < A.length; i1++) {
if (A[i1] > 0 && i < A[i1]) {
return i;
}else if(A[i1]==i){
++i;
}


}
return i;
}

Shortest answer in Python. 100%

def solution(A):
return min([x for x in range(1,len(A) + 2) if x not in set(sorted([x for x in A if x>0 ]))])

My Javascript solution. This got 100%. The solution is to sort the array and compare the adjacent elements of the array.

function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
A.sort((a, b) => a - b);


if (A[0] > 1 || A[A.length - 1] < 0 || A.length === 2) return 1;


for (let i = 1; i < A.length - 1; ++i) {
if (A[i] > 0 && (A[i + 1] - A[i]) > 1) {
return A[i] + 1;
}
}


return A[A.length - 1] + 1;
}

JavaScript ES6 Solution:

function solution(A) {
if (!A.includes(1)) return 1;
return A.filter(a => a > 0)
.sort((a, b) => a - b)
.reduce((p, c) => c === p ? c + 1 : p, 1);
}
console.log(solution([1, 3, 6, 4, 1, 2]));
console.log(solution([1, 2, 3]));
console.log(solution([-1, -3]));
console.log(solution([4, 5, 6]));
console.log(solution([1, 2, 4]));

this is my code in Kotlin:

private fun soluction(A: IntArray): Int {
val N = A.size
val counter = IntArray(N + 1)


for (i in A)
if (i in 1..N)
counter[i]++
   

for (i in 1 until N + 1)
if (counter[i] == 0)
return i
     

return N + 1
}

100% in Swift using recursive function. O(N) or O(N * log(N))

var promise = 1


public func solution(_ A : inout [Int]) -> Int {
// write your code in Swift 4.2.1 (Linux)
execute(A.sorted(), pos: 0)
return promise


}


func execute(_ n:[Int], pos i:Int) {
if n.count == i || n.count == 0 { return }
if promise > 0 && n[i] > 0 && n[i]+1 < promise {
promise = n[i] + 1
} else if promise == n[i] {
promise = n[i] + 1
}
execute(n, pos: i+1)
}

This is for C#, it uses HashSet and Linq queries and has 100% score on Codility

     public int solution(int[] A)
{
var val = new HashSet<int>(A).Where(x => x >= 1).OrderBy((y) =>y).ToArray();
var minval = 1;
for (int i = 0; i < val.Length; i++)
{
if (minval < val[i])
{
return minval;
}
minval = val[i] + 1;
}


return minval;
}

A solution in kotlin using set.

Space complexity: O(N)
Time complexity: O(N)

fun solutionUsingSet(A: IntArray): Int {
val set = HashSet<Int>()
A.forEach {
if (it > 0) {
set.add(it)
}
}
// If input array has no positive numbers
if (set.isEmpty()) {
return 1
}
for (i in 1 until A.size + 1) {
if (!set.contains(i)) {
return i
}
}
// If input array has all numbers from 1 to N occurring once
return A.size + 1
}

Javascript solution:

function solution(A) {
A = [...new Set(A.sort( (a,b) => a-b))];


// If the initial integer is greater than 1 or the last integer is less than 1
if((A[0] > 1) || (A[A.length - 1] < 1)) return 1;


for (let i in A) {
let nextNum = A[+i+1];
if(A[i] === nextNum) continue;
if((nextNum - A[i]) !== 1) {
if(A[i] < 0 ) {
if(A.indexOf(1) !== -1) continue;
return 1;
}
return A[i] + 1;
}
}
}

PHP, passes 100%

function solution ($A) {


sort ($A);
$smol = 1;
  

foreach ($A as $a) {
if ($a > 0) {
if ($smol === $a) {
$smol++;
} else {
if (($a + 1) < $smol) {
$smol = ($a + 1);
}
}
}
}


return $smol;
}

A = [-1, -3]
A = [1, 4, -4, -2, 4, 7, 9]


def solution(A):
A.sort()
A = list(set(A))
A = list(filter(lambda x: x > 0, A))


if len(A) == 0:
return 1


x = min(A)
if(max(A) <= 0 or x > 1):
return 1


# print(A)
for i in range(len(A)):
increment = 1 if i+1 < len(A) else 0
payload = A[i+increment]
#print(payload, x)
if payload - x == 1:
x = payload
else:
return x + 1
print(solution(A))

In C# you can write simple below code.

public int solution(int[] A) {
int maxSize = 100000;
int[] counter = new int[maxSize];


foreach (var number in A)
{
if(number >0 && number <= maxSize)
{
counter[number - 1] = 1;
}
}


for (int i = 0; i < maxSize; i++)
{
if (counter[i] == 0)
return i + 1;
}




return maxSize + 1;
}

C# version

class Solution {
public int solution(int[] A) {
var res=1;
Array.Sort(A);
for(int i=0; i< A.Length; i++)
{
if(res<A[i])
{
break;
}


res= (A[i]>0?A[i]:0) + 1;
}
return res;
}

}

I used Python. First I sorted, then filtered corner cases, then removed elements <1. Now element and index are comparable.

def solution(A):
A = sorted(set(A))
if A[0]>1 or A[-1]<=0:
return 1
x = 0
while x<len(A):
if A[x]<=0:
A.pop(x)
x-=1
x+=1
for i, x in enumerate(A):
if not x==i+1:
return i+1
return i+2

Codility finds it okay..

this got 100% for C#:

using System;
using System.Collections.Generic;
using System.Linq;
public static int solution(int[] A)
{
List<int> lst = A.Select(r => r).Where(r => r > 0).OrderBy(r => r).Distinct().ToList();


Console.WriteLine(string.Join(", ", lst));
            

if (lst.Count == 0)
return 1;


for (int i = 0; i < lst.Count; i++)
{
if (lst[i] != i + 1)
return i + 1;
}
return lst.Count + 1;
}

input : A: IntArray

// Sort A to find the biggest number in the last position on the list
A.sort()
// create `indexed for loop` from `1` to the biggest number in the last position on the list
for (int i = 1; i < A[A.length]; i++) {
// check for current index (positive number)  not found in the list
if ((i in A).not()) println("Answe : $i")
}

The task asks for the minimal non-existing in the array A integer, which is greater than 0.

I think this is the right solution:

1. get the A into a set, to minimize the size by eliminate duplicates and getting the search in the set availability with Set.contains() method.
2. Check the max value in the set. if it is smaller than 0, then return 1 (smallest integer, which is not contained in the set and larger than 0)
3. If the max value is greater than 0, stream through the integers from 1 to max value and check if any of them is missing from the set, then return it.

Here is the solution:

public static int solution(int[] A) {
Set<Integer> mySet = new HashSet<>();
Arrays.stream(A).forEach(mySet::add);
int maxVal = Collections.max(mySet);
return maxVal <=0 ? 1 :
IntStream.range(1, maxVal).filter(i -> !mySet.contains(i)).findFirst().orElse(1);
}

In PHP, this passed 100% correctness and performance

function solution($A){
$min = 1;
sort($A);
for($i = 0 ; $i < count($A); $i++){
if($A[$i] == $min){
$min++;
}
}
return $min;
}

Swift 5 Answer

func getSmallestPositive(array: [Int]) -> Int {


let positive = Array(Set(array))
let positiveArray = positive.filter({$0 > 0}).sorted()
var initialNumber = 1
for number in 0..<positiveArray.count {
let item = positiveArray[number]
if item > initialNumber {
return initialNumber
}
initialNumber = item + 1
}
return initialNumber
}

Usage

    var array = [1, 3, 6, 4, 1, 2]
let numbeFinal = getNumber(array: array)
print(numbeFinal)

This my solution in R

Solution <- function(A){
if(max(A) < 1){
return(1)
}
B = 1:max(A)
if(length(B[!B %in% A])==0){
return(max(A)+1)
}
else {
return(min(B[!B %in% A]))
}
}

Evaluate the function in sample vectors

C = c(1,3,6,4,1,2)
D = c(1,2,3)
E = c(-1,-3)
G = c(-1,-3,9)


Solution(C)
Solution(D)
Solution(E)
Solution(G)

I have done it using Linq. Pure C# . Working fine for below inputs :

//int[] abc = { 1,5,3,6,2,1}; // working
//int[] abc = { 1,2,3}; -- working
//int[] abc = { -1, -2, -3 }; -- working
//int[] abc = { 10000, 99999, 12121 }; -- working


//find the smallest positive missing no.


Array.Sort(abc);
int[] a = abc.Distinct().ToArray();
int output = 0;


var minvalue = a[0];
var maxValue = a[a.Length - 1];


for (int index = minvalue; index < maxValue; index++)
{
if (!a.Contains(index))
{
output = index;
break;
}
}


if (output == 0)
{
if (maxValue < 1)
{
output = 1;
}
else
{
output = maxValue + 1;
}
}


Console.WriteLine(" Output :" + output);

Swift

public func solution(_ A : inout [Int]) -> Int {
// write your code in Swift 4.2.1 (Linux)


var smallestValue = 1
if A.count == 0 {
return smallestValue
}
A.sort()
if (A[0] > 1) || (A[A.count - 1] <= 0) {
return smallestValue
}
for index in 0..<A.count {
if A[index] == smallestValue {
smallestValue = smallestValue + 1
}
}
return smallestValue
}

0. Introduction

A) Languages allowed

The Codility skills assessment demo test allows for solutions written in 18 different languages: C, C++, C#, Go, Java 8, Java 11, JavaScript, Kotlin, Lua, Objective-C, Pascal, PHP, Perl, Python, Ruby, Scala, Swift 4, Visual Basic.

B) Some remarks on your question

I write the solution below which gives a low performance

There is no reason to worry about performance until you have a correct solution. Always make sure the solution is correct before you even think about how fast or slow your algorithm/code is!

expected worst-case time complexity is O(N)

Well, as the asker of the question, it is your decision what requirements should be met in an answer. But if the goal is to score 100% in the Codility (performance) test, then there is no need to demand O(N). There are plenty of solutions in the answers here which are O(N log N) and not O(N), but still pass all 4 performance tests. This proves that the O(N) requirement on time complexity is unnecessarily harsh (if the sole aim is to score 100% on the Codility test).

C) About the solutions presented here

All of the solutions presented here are either refactored versions of already published answers, or inspired by such answers. All solutions here score 100% in the Codility skills assessment demo test. ¹

I have striven to

• explicitly reference each original answer/solution,
• provide a runnable jdoodle link for each solution,
• use the same 8 tests (chosen by myself) for all the solutions,
• choose solutions that score 100% (meaning 5 of 5 for correctness and 4 of 4 for performance/speed),
• make it easy to copy-paste the answers directly into the Codility skills assessment demo test,
• focus on some of the most used languages.

1. Java: the Codility test for correctness is incorrect (!)

I will use one of the existing answers to demonstrate that the Codility test for correctness is flawed for the edge case when the given array is empty.
In an empty array, the smallest positive missing integer is clearly 1. Agreed?

But the Codility test suite seems to accept just about any answer for the empty array.
In the code below, I deliberately return -99 for the empty array, which is obviously incorrect.
Yet, Codility gives me a 100% test score for my flawed solution. (!)

import java.util.Arrays;


/**
https://app.codility.com/demo/take-sample-test 100%
https://stackoverflow.com/a/57067307
https://jdoodle.com/a/3B0D
To run the program in a terminal window:
javac Solution.java && java Solution && rm Solution.class
Terminal command to run the combined formatter/linter:
java -jar ../../../checkstyle-8.45.1.jar -c ../../../google_checks.xml *.java
*/
public class Solution {
/** Returns the smallest positive integer missing in intArray. */
public static int solution(int[] intArray) {
if (intArray.length == 0) { // No elements at all.
return -99; // So the smallest positive missing integer is 1.
}
Arrays.sort(intArray);
// System.out.println(Arrays.toString(intArray)); // Temporarily uncomment?
if (intArray[0] >= 2) { // Smallest positive int is 2 or larger.
return 1; // Meaning smallest positive MISSING int is 1.
}
if (intArray[intArray.length - 1] <= 0) { // Biggest int is 0 or smaller.
return 1; // Again, smallest positive missing int is 1.
}
int smallestPositiveMissing = 1;
for (int i = 0; i < intArray.length; i++) {
if (intArray[i] == smallestPositiveMissing) {
smallestPositiveMissing++;
} // ^^ Stop incrementing if intArray[i] > smallestPositiveMissing. ^^
}   // Because then the smallest positive missing integer has been found:
return smallestPositiveMissing;
}


/** Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically). */
public static void main(String[] args) {
System.out.println("Hello Codility Demo Test for Java, B");
int[] array1 = {-1, -3};
System.out.println(solution(array1));
int[] array2 = {1, -1};
System.out.println(solution(array2));
int[] array3 = {2, 1, 2, 5};
System.out.println(solution(array3));
int[] array4 = {3, 1, -2, 2};
System.out.println(solution(array4));
int[] array5 = {};
System.out.println(solution(array5));
int[] array6 = {1, -5, -3};
System.out.println(solution(array6));
int[] array7 = {1, 2, 4, 5};
System.out.println(solution(array7));
int[] array8 = {17, 2};
System.out.println(solution(array8));
}
}

Below is a screen dump of the result from the test.
As the solution is clearly wrong, of course it should not score 100%! ²

2. JavaScript

Below is a JavaScript solution.
This one has not been posted before, but is inspired by one of the previous answers.

/**
https://app.codility.com/demo/take-sample-test 100%
(c) Henke 2022 https://stackoverflow.com/users/9213345
https://jdoodle.com/a/3AZG
To run the program in a terminal window:
node CodilityDemoJS3.js
Terminal command to run the combined formatter/linter:
standard CodilityDemoJS3.js
https://github.com/standard/standard
*/
function solution (A) {
/// Returns the smallest positive integer missing in the array A.
let smallestMissing = 1
// In the following .reduce(), the only interest is in `smallestMissing`.
// I arbitrarily return '-9' because I don't care about the return value.
A.filter(x => x > 0).sort((a, b) => a - b).reduce((accumulator, item) => {
if (smallestMissing < item) return -9 // Found before end of the array.
smallestMissing = item + 1
return -9 // Found at the end of the array.
}, 1)
return smallestMissing
}
// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).
// Note! The following lines need to be left out when running the
// Codility Demo Test at https://app.codility.com/demo/take-sample-test :
console.log('Hello Codility Demo Test for JavaScript, 3.')
console.log(solution([-1, -3]))
console.log(solution([1, -1]))
console.log(solution([2, 1, 2, 5]))
console.log(solution([3, 1, -2, 2]))
console.log(solution([]))
console.log(solution([1, -5, -3]))
console.log(solution([1, 2, 4, 5]))
console.log(solution([17, 2]))

.as-console-wrapper { max-height: 100% !important; top: 0; }

3. Python

Python has come to compete with Java as one of the most used programming languages worldwide.
The code below is a slightly rewritten version of this answer.

#!/usr/bin/env python3
'''
https://app.codility.com/demo/take-sample-test 100%
https://stackoverflow.com/a/58980724
https://jdoodle.com/a/3B0k
To run the program in a terminal window:
python codility_demo_python_a.py
Command in the terminal window to run the linter:
py -m pylint codility_demo_python_a.py
https://pypi.org/project/pylint/
Dito for autopep8 formatting:
autopep8 codility_demo_python_a.py --in-place
https://pypi.org/project/autopep8/
'''




def solution(int_array):
'''
Returns the smallest positive integer missing in int_array.
'''
max_elem = max(int_array, default=0)
if max_elem < 1:
return 1
int_array = set(int_array)  # Reusing int_array although now a set
# print(int_array)  # <- Temporarily uncomment at line beginning
all_ints = set(range(1, max_elem + 1))
diff_set = all_ints - int_array
if len(diff_set) == 0:
return max_elem + 1
return min(diff_set)




# Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).
# Note! The following lines need to be commented out when running the
# Codility Demo Test at https://app.codility.com/demo/take-sample-test :
print('Hello Codility Demo Test for Python3, a.')
print(solution([-1, -3]))
print(solution([1, -1]))
print(solution([2, 1, 2, 5]))
print(solution([3, 1, -2, 2]))
print(solution([]))
print(solution([1, -5, -3]))
print(solution([1, 2, 4, 5]))
print(solution([17, 2]))

4. C#

Here a solution for C#, inspired by a previous answer.

using System;
using System.Linq;
/// https://app.codility.com/demo/take-sample-test 100%
/// (c) 2021 Henke, https://stackoverflow.com/users/9213345
/// https://jdoodle.com/a/3B0Z
/// To initialize the program in a terminal window, only ONCE:
///   dotnet new console -o codilityDemoC#-2 && cd codilityDemoC#-2
/// To run the program in a terminal window:
///   dotnet run && rm -rf obj && rm -rf bin
/// Terminal command to run 'dotnet-format':
///   dotnet-format --include DemoC#_2.cs && rm -rf obj && rm -rf bin
public class Solution {
/// Returns the smallest positive integer missing in intArray.
public int solution(int[] intArray) {
var sortedSet =
intArray.Where(x => x > 0).Distinct().OrderBy(x => x).ToArray();
// Console.WriteLine("[" + string.Join(",", sortedSet) + "]"); // Uncomment?
if (sortedSet.Length == 0) return 1; // The set is empty.
int smallestMissing = 1;
for (int i = 0; i < sortedSet.Length; i++) {
if (smallestMissing < sortedSet[i]) break; // The answer has been found.
smallestMissing = sortedSet[i] + 1;
} // Coming here means all of `sortedSet` had to be traversed.
return smallestMissing;
}


/// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).
/// NOTE! The code below must be removed before running the Codility test.
static void Main(string[] args) {
Console.WriteLine("Hello Codility Demo Test for C#, 2.");
int[] array1 = { -1, -3 };
Console.WriteLine((new Solution()).solution(array1));
int[] array2 = { 1, -1 };
Console.WriteLine((new Solution()).solution(array2));
int[] array3 = { 2, 1, 2, 5 };
Console.WriteLine((new Solution()).solution(array3));
int[] array4 = { 3, 1, -2, 2 };
Console.WriteLine((new Solution()).solution(array4));
int[] array5 = { };
Console.WriteLine((new Solution()).solution(array5));
int[] array6 = { 1, -5, -3 };
Console.WriteLine((new Solution()).solution(array6));
int[] array7 = { 1, 2, 4, 5 };
Console.WriteLine((new Solution()).solution(array7));
int[] array8 = { 17, 2 };
Console.WriteLine((new Solution()).solution(array8));
}
}

5. Swift

Here is a solution for Swift, taken from this answer.

/**
https://app.codility.com/demo/take-sample-test 100%
https://stackoverflow.com/a/57063839
https://www.jdoodle.com/a/4ny5
*/
public func solution(_ A : inout [Int]) -> Int {
/// Returns the smallest positive integer missing in the array A.
let positiveSortedInts = A.filter { $0 > 0 }.sorted()
// print(positiveSortedInts) // <- Temporarily uncomment at line beginning
var smallestMissingPositiveInt = 1
for elem in positiveSortedInts{
// if(elem > smallestMissingPositiveInt) then the answer has been found!
if(elem > smallestMissingPositiveInt) { return smallestMissingPositiveInt }
smallestMissingPositiveInt = elem + 1
}
return smallestMissingPositiveInt // This is if the whole array was traversed.
}
// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 (but vertically).
// Note! The following lines need to be left out when running the
// Codility Demo Test at https://app.codility.com/demo/take-sample-test :
print("Hello Codility Demo Test for Swift 4, A.")
var array1 = [-1, -3]
print(solution(&array1))
var array2 = [1, -1]
print(solution(&array2))
var array3 = [2, 1, 2, 5]
print(solution(&array3))
var array4 = [3, 1, -2, 2]
print(solution(&array4))
var array5 = [] as [Int]
print(solution(&array5))
var array6 = [1, -5, -3]
print(solution(&array6))
var array7 = [1, 2, 4, 5]
print(solution(&array7))
var array8 = [17, 2]
print(solution(&array8))

6. PHP

Here a solution for PHP, taken from this answer.

<?php
/**
https://app.codility.com/demo/take-sample-test 100%
https://stackoverflow.com/a/60535808
https://www.jdoodle.com/a/4nB0
*/
function solution($A) {
$smallestMissingPositiveInt = 1;
sort($A);
foreach($A as $elem){
if($elem <=0) continue;
if($smallestMissingPositiveInt < $elem) return $smallestMissingPositiveInt;
else $smallestMissingPositiveInt = $elem + 1;
}
return $smallestMissingPositiveInt;
}
// Demo examples. --> Expected output: 1 2 3 4 1 2 3 1 .
// Note! The starting and ending PHP tags are needed when running
// the code from the command line in a *.php file, but they and
// the following lines need to be left out when running the Codility
// Demo Test at https://app.codility.com/demo/take-sample-test :
echo "Hello Codility Demo Test for PHP, 1.\n";
echo solution([-1, -3]) . " ";
echo solution([1, -1]) . " ";
echo solution([2, 1, 2, 5]) . " ";
echo solution([3, 1, -2, 2]) . " ";
echo solution([]) . " ";
echo solution([1, -5, -3]) . " ";
echo solution([1, 2, 4, 5]) . " ";
echo solution([17, 2]) . " ";
?>

References

• The Codility skills assessment demo test
• The LeetCode playground
• A correct Java solution
• A correct JavaScript solution
• A correct Python 3 solution
• A correct C# solution
• A correct Swift 4 solution
• A correct PHP solution

Go language : Find the smallest positive integer that does not occur in a given sequence

GO language:

• sort above given array in ascending order
• map to iterate loop of above stored result, if to check x is less than the current element then return, otherwise, add 1 in the current element and assign to x

package main
    

import (
"fmt"
"sort"
)


func Solution(nums []int) int {
sort.Ints(nums)
x := 1
for _, val := range nums {
if(x < val) {
return x
}
if(val >= 0) {
x = val + 1
}
}
return x
}


func main() {


a1 := []int{1, 3, 6, 4, 1, 2}
fmt.Println(Solution(a1))    // Should return : 5


a2 := []int{1, 2, 3}
fmt.Println(Solution(a2))    // Should return : 4


a3 := []int{-1, -3}
fmt.Println(Solution(a3))    // Should return : 1


a4 := []int{4, 5, 6}
fmt.Println(Solution(a4))    // Should return : 1


a5 := []int{1, 2, 4}
fmt.Println(Solution(a5))    // Should return : 3


}

Ruby 2.2 solution. Total score 77% due to somewhat weak performance.

def solution(a)
positive_sorted = a.uniq.sort.select {|i| i > 0 }
return 1 if (positive_sorted.empty? || positive_sorted.first > 1)


positive_sorted.each do |i|
res = i + 1
next if positive_sorted.include?(res)
return res
end
end

This code has been written in C

The existing was in C++ and Java

function solution(A) {
// only positive values, sorted
int i,j,small,large,value,temp,skip=0;
int arr[N];
for(i=0;i<N;i++)
{
value = A[i];
for(j=i;j<N;j++)
{
if(value > A[j])
{
temp = value;
value = A[j];
A[j] = temp;
}
}
        

arr[i] = value;
}
small = arr[0];
large = arr[N-1];
for(i=0;i<N;i++)
{
if(arr[i] == arr[i+1])
{
for(j=i;j<(N);j++)
{
arr[j] = arr[j+1];
}
skip++;
}
        

}
if(large < 0)
{
return 1;
}
for(i=0;i<(N);i++)
{
if(arr[i] != (small+i))
{
return (arr[i-1]+1);
}
else if(arr[i] == large)
{
return (large+1);
}
}
}

This is my 100% correct solution with swift 4 using Set and avoiding the use of sorted().

     let setOfIntegers = Set<Int>(A)
var max = 0
for integer in stride(from: 1, to: A.count + 1, by: 1) {
max = integer > max ? integer : max
if (!setOfIntegers.contains(integer)) {
return integer
}
}
        

return  max + 1

for JavaScript

let arr = [1, 3, 6, 4, 1, 2];
let arr1 = [1, 2, 3];
let arr2 = [-1, -3];


function solution(A) {
let smallestInteger = 1;


A.forEach(function (val) {
if (A.includes(smallestInteger)) {
if (val > 0) smallestInteger++;
}
});


return smallestInteger;
}


console.log(solution(arr));
console.log(solution(arr1));
console.log(solution(arr2));

C++ Answer to this question.

#include <vector>
#include <algorithm>
using namespace std;
  

// One function works for all data types.  This would work
// even for user defined types if operator '>' is overloaded
template <typename T> T myMax(T x, T y)
{
return (x > y) ? x : y;
}


int removeDuplicates(vector<int> &arr, int n)
{
// Return, if array is empty or contains a single
// element
if (n == 0 || n == 1)
return n;
 

int temp[n];
 

// Start traversing elements
int j = 0;
// If current element is not equal to next element
// then store that current element
for (int i = 0; i < n - 1; i++)
if (arr[i] != arr[i + 1])
temp[j++] = arr[i];
 

// Store the last element as whether it is unique or
// repeated, it hasn't stored previously
temp[j++] = arr[n - 1];
 

// Modify original array
for (int i = 0; i < j; i++)
arr[i] = temp[i];
 

return j;
}
 

int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)0
std::vector<int> vect2;
int temp= 1;
// if(A.size() == 0)
// {
//     return 0;
// }
{


sort(A.begin(), A.end());
int n = sizeof(A) / sizeof(A[0]);
n = removeDuplicates(A, n);
         

        

for(int i=0; i<A.size(); i++)
{
if(A[i]!= i+1)
{
              

temp = i+1;
break;
}
else{
temp = i+2;
}
                

//  return i+1;
}
return temp;
}
}


int main()
{
   



std::vector<int> vect;
vect.push_back(1);
vect.push_back(2);
vect.push_back(3);


cout<<solution(vect);
return 0;
}

In JS,

function solution(A) {
    

let arr = [...new Set(A)].sort();
let fullArr = [];
let smallest = 1;
for(let i=1; i<= arr.length ; i++){
fullArr.push(i);
}
  

let difference = fullArr.filter(x => !arr.includes(x));
if(difference.length > 0)
smallest = difference[0];
else {
smallest = arr[arr.length-1];
smallest++
}
  

return smallest;
}

The equivalent and simplest code in Python 3.6

def solution(A):
ab = set(range(1,abs(max(A))+2)).difference(set(A))
return min(ab)

Passed all test cases, Correctness test cases, and Performance test cases

Algorithm

for element element is array which is in range [1, N] and not in its correct place, swap this element with element of its correct place. Which ever index don’t match with its element is the answer.

class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for(int i = 0; i < n;) {
if(nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i]-1]) {
swap(nums,nums[i]-1,i);
} else {
i++;
}
}
for(int i = 0; i < n; i++) {
if(nums[i] != i+1) return i+1;
}
return n+1;
}


private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}}

function solution(A) {
const mylist = new Set(A);
for(i=1;i<= mylist.size+1;i++){
if(!mylist.has(i)) {
return i;
}
}
}

Linear complexity O(2N) which simplifies to O(N). I used two sequentials loops, no nested loops. Performance 100%, Correctness 100% according to codility: https://app.codility.com/demo/results/trainingR7Y4E4-REP/. It shows 1 min completion time because I forgot to set length of (1000000 + 1) so I re-ran test again

// you can also use imports, for example:
import java.util.Arrays;


// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");


class Solution {
public int solution(int[] array) {
boolean[] nums = new boolean[1000000 + 1];// for indexing purpose.


Arrays.stream(array).forEach(i -> {
if(i > 0) {
nums[i] = true;
}
});


if(!nums[1])
return 1;


for(int i = 2; i < nums.length; i++) {
if(!nums[i])
return i;
}


return 1;
}
}

here is a nice solution in Python:

#!/usr/bin/env python3


def solution(A):
max_number=max(A)


if max_number<0:
return 1


set_A=set(A)
set_B=set(range(1,max_number+1))
set_D=set_B-set_A


if len(set_D)==0:
return max_number+1
else:
return min(set_D)








print(solution([1,3,6,4,1,2])) #should print 5
print(solution([1,2,3])) #should print 4
print(solution([-1,-3])) #should print 1

Sort way with JS

function solution(A) {
let result = 1;
A.sort((a, b) => a - b);
for (let i = 0; i < A.length; i++) {
if (A[i] === result) {
result++;
}
}
return result;
}