This afternoon I try to resolve the demo test of Codility. After thinking a lot how to increase the performance (and searching a little bit), I created this code:
function solution(A) {
let array = [...Array(1000001).keys()];
const onlyPositives = A.filter(n => n>0);
if(onlyPositives.length == 0) return 1
onlyPositives.forEach(a => {
if(array[a] != null)
array[a] = null;
});
array[0] = null;
return array.findIndex(e => e != null);
}
Anyone have another Idea?
Futhermore, you can use the same code without filtering, but in some cases the effective are less.
Another approach might be to sort the array and search for the first gap:
Another way to deal with the positive only thing. My JS solution got 100 across the board. Basically, I generate a new array whose keys will be the values of the original array and set each to some truthy value. This does two things: it takes the negative values out of the iteration loop of the new array, and also allows you to loop from the smallest value up and return the first index that gives you undefined.
O(n) solution javascript.
using two loops.
first loop puts all elements bigger then 0 into a map/object
second loop check if value existing in map.
Here is the Java 8 version of the solution which resulted in 100% after submission. I used HashSet to eliminate the duplicate element.
class Solution {
public int solution(int[] A) {
}
Here is my 100% performant solution
PROBLEM
Write a function: int solution(NSMutableArray *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,
Write an efficient algorithm for the following assumptions:
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].
OBJECTIVE-C SOLUTION O(N)
Results given by Codility
Task Score: 100%
Correctness: 100%
Performance: 100%
Time Complexity
The worst case time complexity is O(N) or O(N * log(N))
Xcode Solution Here