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

I was trying to solve a problem in Codility provided below,

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

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
}

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; 
        int cap = A.length; //for efficiency — no need to calculate or access the array object’s length property per iteration 
        
        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; //this means: if (min <= 0 ){min =1}else{min = min} you can also do: if min <1 for better efficiency/less jumps
        return min;    
    }
}

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)

For Swift 4

func solution(_ A : [Int]) -> Int {
     var 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) {
     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;
}

}

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

JS

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

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

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

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

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

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
}

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

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.

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
}

100% solution in Swift, I found it here, it is really beautiful than mine 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
        }
    }
}

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

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

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

<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

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

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

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

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

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

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

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

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

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

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

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;

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

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

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
}

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.

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

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
}

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



    }
}

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;

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

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

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)

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

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

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

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;

}

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

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

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

      }
    }

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

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
}

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;

    for(let i=1; i <= (max + 1); i++) {
        r  = A.includes(i) ? 1 : i ;
        if(r>1) break;
    }

    return r;
}

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

Swift with .reduce()

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

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

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

}

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

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

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

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
}

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

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

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

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;

}

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 better case you are under O(N) complexity

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

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