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.
If the expected running time should be linear, you can't use a TreeSet
, which sorts the input and therefore requires O(NlogN)
. Therefore you should use a HashSet
, which requires O(N)
time to add N
elements.
Besides, you don't need 4 loops. It's sufficient to add all the positive input elements to a HashSet
(first loop) and then find the first positive integer not in that Set (second loop).
int N = A.length;
Set<Integer> set = new HashSet<>();
for (int a : A) {
if (a > 0) {
set.add(a);
}
}
for (int i = 1; i <= N + 1; i++) {
if (!set.contains(i)) {
return i;
}
}
100% result solution in Javascript:
function solution(A) {
// only positive values, sorted
A = A.filter(x => x >= 1).sort((a, b) => a - b)
let x = 1
for(let i = 0; i < A.length; i++) {
// if we find a smaller number no need to continue, cause the array is sorted
if(x < A[i]) {
return x
}
x = A[i] + 1
}
return x
}
My code in Java, 100% result in Codility
import java.util.*;
class Solution {
public int solution(int[] arr) {
int smallestInt = 1;
if (arr.length == 0) return smallestInt;
Arrays.sort(arr);
if (arr[0] > 1) return smallestInt;
if (arr[arr.length - 1] <= 0) return smallestInt;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == smallestInt) {
smallestInt++;
}
}
return smallestInt;
}
}
Here is an efficient python solution:
def solution(A):
m = max(A)
if m < 1:
return 1
A = set(A)
B = set(range(1, m + 1))
D = B - A
if len(D) == 0:
return m + 1
else:
return min(D)