130

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,

enter image description here

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

10
  • I can write better solution, but get puzzled on this
    – Arefe
    Commented Aug 7, 2018 at 6:07
  • @ruakh Collections.sort() and his solution works Commented Aug 7, 2018 at 6:12
  • 3
    @TimBiegeleisen With a correctness of 20%, it absolutely does not belong on Code Review. The speed is irrelevant as long as it simply doesn't work.
    – Mast
    Commented Aug 7, 2018 at 6:14
  • 2
    The original question is asked for Java, but other programmers started to provide many answers that I didn't expect. So, I just remove the Java tag now.
    – Arefe
    Commented Aug 18, 2021 at 15:22
  • 2
    In your question: expected worst-case time complexity is O(N). But in a comment you ask for a 100% score in the codility demo test? Some answers here sort the array as part of their solution, implying O(N log(N)) rather than O(N), but still report that their solution scores 100% in the codility test. Could you clarify which is more important – the desire to score 100% on the test – or that the algorithm may perform no worse than O(N), asymptotically? Commented Aug 24, 2021 at 11:03

126 Answers 126

1
2 3 4 5
160

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;
    }
}
11
  • How would you find the first positive integer not in the set in n time? n is the size of the input, not the maximum possible integer of the problem.
    – Jorge.V
    Commented Aug 7, 2018 at 6:20
  • 12
    @Jorge.V since N is the size of the input, the first positive integer not in the input is at most N+1 (if the input array contains all the numbers between 1 and N). Therefore the second loop will run at most N+1 iterations. Hence O(N).
    – Eran
    Commented Aug 7, 2018 at 6:22
  • @Eran you could set the size of your hash set, not that it makes much of a difference, but it would prevent the possibility of having to search inside of each bin.
    – matt
    Commented Aug 7, 2018 at 6:42
  • @matt I guess you can set the initial capacity to N to save the need to resize the backing HashMap, but on the other hand, it would be wasteful if most of the input numbers are negative (and therefore not added to the Set).
    – Eran
    Commented Aug 7, 2018 at 6:46
  • 3
    Add this couple of lines so it returns when the array is like this [-1,-3] int N = A.length, res = 1; boolean found = false; Set<Integer> set = new HashSet<>(); for (int a : A) { if (a > 0) { set.add(a); } } for (int i = 1; i <= N + 1 && !found; i++) { if (!set.contains(i)) { res = i; found = true; } } return res;
    – Camilo
    Commented Aug 6, 2019 at 8:28
90

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
}

6
  • 5
    Looks like they changed the tests: chaotic sequences length=10005 (with minus) got 2 expected 101. I think the question on the site is not well written...
    – OctaviaLo
    Commented Aug 24, 2019 at 9:36
  • 1
    ``` function solution(A) { return Array.from(new Set(A.filter((a)=>a=>1))).sort((a,b)=>a-b).reduce((prev,n,i)=>{ if (n===prev) return n+1 else return prev },1) } ```
    – Nico
    Commented Jun 30, 2020 at 14:48
  • This gets 100% score. (just run it out of curiosity.
    – lesyk
    Commented Dec 20, 2020 at 18:00
  • As of August 2021 this solution passes 100% of all the sets of test cases in codility website.
    – utkarsh-k
    Commented Aug 3, 2021 at 21:42
  • As of April 2024, it passes 31% with failing completely in performance test on codility website.
    – guilemon
    Commented Apr 19 at 20:35
63

My code in Java, 100% result in Codility

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        Arrays.sort(arr);

        int smallest = 1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == smallest) {
                smallest++;
            }
        }
        return smallest;
    }
}
7
  • Perfect answer. Commented Mar 25, 2021 at 14:40
  • A perfect Solution Commented Apr 10, 2021 at 18:22
  • Arrays.sort(arr); is O(N log(N) ), while O(N) solution is expected.
    – Aivean
    Commented Jul 23, 2021 at 17:04
  • 1
    You don't need those checks. It will work with just sort and that for loop. Commented Sep 4, 2021 at 6:48
  • agree with @Aivean, in the other hand runtime complexity here O(N log(N) ), but you not use extra space, so space complexity is O(1)
    – Alex S
    Commented Jan 11, 2022 at 18:35
26

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)
6
  • I think the test case [-10,-3] breaks your solution. You will return -2 when you should return 1.
    – YagoCaruso
    Commented Sep 23, 2020 at 17:33
  • 1
    @YagoCaruso if m < 1: takes care of it. Commented Oct 13, 2020 at 15:10
  • The line A = set(A) is interesting. If you don't reuse the identifier A when creating the set, you will get 88% score instead of 100%. (Meaning one of the performance tests fail.) Apparently, Python can work faster by reusing the array when creating the set? Any comments on that? Commented Aug 30, 2021 at 11:19
  • why is this more efficient than doing A = set(A) and then looping over a range(1, 100_001) and checking if the element is in A? set(A) is O(n) and the loop is O(m), with n being the size of the array (could be 2 million) and m between 1 and 100K. I only got a 75% score for this solution and wonder why
    – hansaplast
    Commented Aug 12, 2022 at 9:08
  • This is not efficient at all. You iterate the set once just to get the max(A); then you iterate it again to get the set(A); then you create a new set with range, and you iterate A again to find the differences in the two sets. This is at least O(3N), whilst this problem can be resolved in O(N).
    – alelom
    Commented Nov 28, 2022 at 15:07
24

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

7
  • 5
    While this might be an answer, but it needs explanations and details to be written. Commented May 7, 2020 at 17:49
  • 2
    Why would you give a JavaScript answer to a question tagged with java?
    – Chris
    Commented May 8, 2020 at 1:42
  • This gets 100% score. (just run it out of curiosity.
    – lesyk
    Commented Dec 20, 2020 at 17:59
  • filter is used just so the original array is not mutated.
    – apena
    Commented Jun 24, 2021 at 22:49
  • Why would you give a JavaScript answer to a question tagged with java? The tag java has since been removed. Commented Aug 22, 2021 at 16:16
17

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;    
    }
}
5
  • 4
    Your time complexity is O(N*log(N)) so it violates the question requirement of ...expected worst-case time complexity is O(N);...
    – Anatolii
    Commented Nov 22, 2019 at 10:57
  • In if condition, can't we put if(A.indexOf(A[i] + 1) < 0){ return min; }
    – Ujjaval
    Commented Jan 24, 2020 at 7:47
  • why? explain why you think so. & indexOf is used on Lists so you'd have to convert the array to a list or use an arraylist to start with .. that is if you badly want to use indexOf. .. knowing that 1 is the most minimum, you wouldn't check against 0 maybe < 1 or < 2.. what do you think ?.. so if any number +1 is < 0 would be logically challenging as a solution .. if you also happen to return at that point, then you haven't checked the entire array for the smallest value.. you've just checked until your condition was met.
    – Timetrax
    Commented Jan 24, 2020 at 12:34
  • 2
    you should add else condition that if A[i] > min then break the loop. Since you have already sorted the array, you don't have to iterate till the end. Commented Sep 6, 2020 at 11:02
  • I would think that the Java compiler would optimize the for(;;) statement to fetch A.length once, knowing that A does not change in the loop. Commented Jan 18, 2022 at 17:28
13

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
13

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.

3
13

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
}
1
  • 1
    Nah, fails for redundant elements. It won't work for e.g. [4, 1, 2, 2]. Commented Feb 13, 2022 at 22:14
9

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;
}
1
  • Good to see other languages around
    – Arefe
    Commented May 8, 2019 at 4:19
9

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

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

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;
        }
    }
}
1
  • 1
    This solves the problem in all possible scenarios - performance and logic.
    – Abiranjan
    Commented Nov 16, 2021 at 17:27
7

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)
3
  • I know it has been a while but do you think you could add some comments to this to explain what is happening?
    – JamesG
    Commented Mar 16, 2020 at 2:12
  • @JamesG. Edited my answer above and added the intuition behind it. Hope it provides more clarity.
    – stratisxen
    Commented Mar 17, 2020 at 20:34
  • little improvement: B = set([a for a in x if a >= 0]) * we don't need zero values after all Commented Sep 30, 2021 at 6:40
6

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

1
6

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
        }
    }
}
1
  • Best one I have seen so far
    – ThangTD
    Commented Apr 11, 2023 at 16:45
6

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

2
  • This score 66% on the website.
    – lesyk
    Commented Dec 20, 2020 at 18:02
  • @lesyk Yeah. Not passed on the performance tests with large sequences. The message that occurred is "Timeout error. Killed. Hard limit reached 6 seconds". Does someone have a solution for that? Commented Dec 21, 2020 at 15:26
6

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);
}
4
  • 1
    This is interesting. Does it work 100% score in the Codility? Especially, we need to check it for negative numbers.
    – Arefe
    Commented Nov 12, 2020 at 5:15
  • 1
    The negative numbers are ignored since I am only using positive numbers to set the bit positions (the requirement was to find the first positive number). I don't have access to Codility. If you do feel free to check it out. But I would be interested in the results. I did check it out on some very large data sets. Worst case was using 1 to 100,000,000 in the array. It came back with 100,000,001 in about 1 second.
    – WJS
    Commented Nov 12, 2020 at 15:38
  • 1
    I just ran this on Codility. It received 100% on everything. Worse case test took .28 seconds.
    – WJS
    Commented Nov 12, 2020 at 17:05
  • 1
    This one is good. However you need to add another clause to your condition, specifically, if (i > 0 && i <= arr.length). This will ensure O(N) upper space and time bound. Without this clause, if your your space and time bound is O( K ), where K is maximal value of arr.
    – Aivean
    Commented Jul 23, 2021 at 17:08
5

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

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

0. Introduction

A) Languages allowed

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

B) Some remarks on your question

I write the solution below which gives a low performance

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

expected worst-case time complexity is O(N)

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

C) About the solutions presented here

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

I have striven to

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

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

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

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

import java.util.Arrays;

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

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

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

The Codility test scores 100% for an ERRONEOUS solution!

2. JavaScript

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

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

3. Python

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

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


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


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

4. C#

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

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

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

5. Swift

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

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

6. PHP

Here a solution for PHP, taken from this answer.

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

References


1 This is true even for the first solution – the Java solution – despite the the fact that this solution is wrong!

2 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. The default is Java 8, so you won't need to change the language for the first solution.

4
  • 1
    clever solution
    – ACAkgul
    Commented May 24, 2022 at 14:59
  • Can you print out the score percentage for the PHP solution Commented Jun 10, 2022 at 21:46
  • All 6 solutions score 100%, including the PHP solution. I have updated my answer to reflect this. Commented Jun 15, 2022 at 15:34
  • There are plenty of good solutions among the answers here. I've chosen to include only one solution per language. So I'm more inclined to add more of other languages than adding more solutions of languages that I've already included. Commented Nov 12, 2022 at 10:54
5

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

1
  • Amazing! Concise and well performing but it blows the brains. I'w suggest not to change the original array, sort the copy. Commented Jan 21, 2023 at 7:41
4

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
}
8
  • What is original in this answer? What purpose is special casing 1? Why let index assume values up to result.count - 1 just to exclude the upper bound with an extra if?
    – greybeard
    Commented Aug 1, 2019 at 6:41
  • special casing 1 is for if that array doesn't contain 1 that means 1 is the result which is the smallest integer not available in array. And index is assumed upto result.count - 1 just because inner condition checks for index + 1 where it will get fail with index out of bound. So we have to check only upto last index. And if the for loop finish upto last index and we don't found the smallest integer then last return line will return the next integer after the last element. You can copy this solution to codility to check the output and result. Commented Aug 2, 2019 at 7:18
  • @greybeard If this solution helped you then give up vote plz. Commented Aug 2, 2019 at 10:26
  • This is uncommented code in a language the question is not tagged with. It contains code for a special case that does "not" change the result without giving a motivation (avoiding a superlinear processing step comes to mind). It uses an extra conditional statement to fix an inapt choice of loop limit. It uses four comparisons per iteration where one would suffice. Not only does this solution not help me: It annoys me.
    – greybeard
    Commented Aug 3, 2019 at 5:33
  • 1
    Can we do it with reduce rather than for loop? Commented Oct 24, 2019 at 12:33
4

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

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;
1
  • 1
    I tried this, three of the corner cases were missing. I modified this by adding an additional statemen of "if(A[0]>1) return 1; all the corner cases got covered and gave a 100% on all three Commented Jul 5, 2022 at 6:49
4

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
}

Codility Test Result

4

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;
    }
2
  • 1
    So does return Enumerable.Range(1, 100001).Except(A).First(); Commented Sep 8, 2021 at 20:48
  • @AlexandruClonțea solution is short and conscience. Commented Sep 9, 2021 at 2:26
3

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.

5
  • expected worst-case time complexity is O(N); - adding N elements to a TreeSet requires O(NlogN) time.
    – Eran
    Commented Aug 7, 2018 at 6:30
  • @Eran I thought the first concern was getting it correct. I don't know an O(N) solution offhand.
    – matt
    Commented Aug 7, 2018 at 6:32
  • 1
    Does your code work for this set[]={1,4} .I think you will not get the min positive integer.
    – Nivedh
    Commented Aug 7, 2018 at 6:36
  • @Nivedh The first method I wrote would return 2 in that case. I updated it because it was broken for negative numbers. I also added an O(n) version.
    – matt
    Commented Aug 7, 2018 at 6:49
  • 1
    @matt The second solution is impressive. I'd use a boolean[] to express the intent that this is a flag, and rename it from hash to or appeared. And you can have N = A.length + 1, which will make the other code slightly simpler and easier to understand, as it can become appeared[i], and if (!appeared[i]) return i;. Commented Aug 7, 2018 at 9:00
3

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;
}
4
  • 1
    With your algorithm, a sample test like {-1, 2} will return 2 instead of 1. The problem is that 0 position is occupied by the negative value (-1) and your if (A[i] > 0) check will return false for it.
    – Anatolii
    Commented Aug 7, 2018 at 9:36
  • ok cant do it O(1) space, needed storage. The answer is updated
    – Arefe
    Commented Aug 7, 2018 at 10:27
  • Actually, you can do it without using additional storages if the negatives are set to 0 earlier ie you have done in your example.
    – Arefe
    Commented Aug 8, 2018 at 4:23
  • No storage is needed for this. And no need to tamper with the original array by setting anything to 0 Take a look at my solution
    – Timetrax
    Commented Sep 14, 2018 at 12:12
3
//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;
    }
}
5
  • 2
    Can you please add some text explaining why your answer works Commented Oct 31, 2018 at 23:31
  • It's good you tried and find a recursive solution I was not aware of. However, it requires a sorting in the primary method before can start the recursion and hence, can't be solved with O(N). Have a great day.
    – Arefe
    Commented Nov 2, 2018 at 1:33
  • It can be done by recursion without sorting: pastebin.com/yERsyKzV Commented Apr 1, 2019 at 0:17
  • The solution does not finish in O(n) time. e.g. [n, n-1, n-2, ....., 2, 1] will provide the worst performane O(n^2)
    – Nitesh
    Commented May 13, 2019 at 14:03
  • 1
    The solution is correct but it's performance-intensive and won't pass in the Codility
    – Arefe
    Commented Aug 6, 2019 at 8:37
1
2 3 4 5

Not the answer you're looking for? Browse other questions tagged or ask your own question.