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

I was trying to solve this problem:

> Write a function: > > class Solution { public int solution(int[] A); } > > that, given an array A of N integers, returns the smallest positive > integer (greater than 0) that does not occur in A. > > For example, given A = [1, 3, 6, 4, 1, 2], the function should return > 5. > > Given A = [1, 2, 3], the function should return 4. >
> Given A = [−1, −3], the function should return 1. > > Assume that: > > N is an integer within the range [1..100,000]; each element of array A > is an integer within the range [−1,000,000..1,000,000]. Complexity: > > expected worst-case time complexity is O(N); expected worst-case space > complexity is O(N) (not counting the storage required for input > arguments).

I wrote the solution below which gives a low performance, however, I can't see the bug.

public static int solution(int[] A) {

        Set<Integer> set = new TreeSet<>();

        for (int a : A) {
            set.add(a);
        }

        int N = set.size();

        int[] C = new int[N];

        int index = 0;

        for (int a : set) {
            C[index++] = a;
        }

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

            if (C[i] > 0 && C[i] <= N) {
                C[i] = 0;
            }
        }

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

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

        return (N + 1);
    }

The score is provided here,

I will keep investigating myself, but please inform me if you can see better.

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

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
}

My code in Java, 100% result in Codility

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        int smallestInt = 1;

        if (arr.length == 0) return smallestInt;

        Arrays.sort(arr);

        if (arr[0] > 1) return smallestInt;
        if (arr[arr.length - 1] <= 0) return smallestInt;

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

        return smallestInt;
    }
}

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)

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

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

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
}

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.

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

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
}

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

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)

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);
}

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

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

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

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

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

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
}

0. Introduction

A) Languages allowed

The codility 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% on 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. I have strived 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 demo test,
• try to have some of the most used languages respresented.

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.
Since the solution is wrong, of course it should not score 100%! ¹

"The codility test scores 100% for an erroneous solution"

---

¹ You can try running the test yourself at https://app.codility.com/demo/take-sample-test. You will have to sign up to do so. Simply copy-paste all of the code from the snippet above. The default is Java 8, so you won't need to change the language.

2. A JavaScript solution

Below is a JavaScript solution.
It has not been published 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. A Python solution

Python has come to compete with Java as one of the most used programming languages worldwide. So here is a Python solution. 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. A C# solution

Here is a solution for C#.
This solution too is 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. A Swift solution

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. A PHP solution

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

/**
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 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]) . " ";

Reference

• LeetCode Playground

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
}

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

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
}

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

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

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

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

<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

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

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

}

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

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

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;

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

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

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

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

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

}

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

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

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:

  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;
   
 

    }
}

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

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

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

// Codility Interview Question Solved Using Javascript

const newArray = []; //used in comparison to array with which the solution is required

const solution = (number) => {
  //function with array parameter 'number'
  const largest = number.reduce((num1, num2) => {
    return num1 > num2
      ? num1
      : num2; /*finds the largest number in the array to
                                   be used as benchmark for the new array to
                                   be created*/
  });

  const range = 1 + largest;
  for (
    let x = 1;
    x <= range;
    x++ //loop to populate new array with positive integers
  ) {
    if (x > range) {
      break;
    }
    newArray.push(x);
  }
  console.log("This is the number array: [" + number + "]"); //array passed
  console.log("This is the new array: [" + newArray + "]"); //array formed in relation to array passed
  const newerArray = newArray.filter((elements) => {
    //array formed frome unique values of 'newArray'
    return number.indexOf(elements) == -1;
  });
  console.log(
    "These are numbers not present in the number array: " + newerArray
  );

  const lowestInteger = newerArray.reduce((first, second) => {
    //newerArray reduced to its lowest possible element by finding the least element in the array
    return first < second ? first : second;
  });
  console.log("The lowest positive integer is " + lowestInteger);
};
solution([1, 2, 3, 4, 6]); //solution function to find the lowest possible integer invoked

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

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

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

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

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

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

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
}

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

}

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);
}

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
}

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

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

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

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;

}

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