I am aware that this exact problem has been asked around before. The purpose of my question is to figure out why my specific solution is not working. Codility does not allow us to see the full test cases they use, and apparently my code is failing some of the test cases. My code has worked for most of the test cases I've tried, but failing for their ones which I can't see.
Problem: Write a function 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.
Given A = [2, 2, 2], the function should return 1.
etc
My solution
function solution(A) {
const positivesOfA = A.filter(elem => elem > 0);
const limit = Math.max(...A);
let res = [];
if (positivesOfA.length == 0) {
return 1;
} else {
for (var i = 1; i <= limit; i ) {
if (!A.includes(i)) {
res.push(i);
}
}
return (res.length == 0 ? limit 1 : Math.min(...res))
}
}
What is wrong this?
EDIT: having looked into it, the codility platform does test for efficiency and performance. However, it says that I still failed 1/4 test cases. So the test case is still an issue with, along with performance for which I got 0 marks.
CodePudding user response：
My guess, which could be wrong, is that since your function succeeds in a some tests but fails deeper in the testing, is that the test could be feeding really big arrays into your function, and checking against a minimum efficiency or maximum execution time.
In the solution, you're iterating over the whole input array for each value in the array, so that's a time complexity of O(n2). So when the input gets really big, it'll start taking some time to run includes() for each value in the array. And even if you break when you find the answer, if there's no missing integer then it'll still take some time to run.
Here's a solution that:
- Creates an array of unique number by creating and spreading a
Set: O(n) - Sorts the array: O(n log(n))
- Walks down the sorted array once and when it finds the missing integer, it returns it: O(n)
Research Greedy Algorithms, they're usually what questions like this are looking for.
const a = [1, 3, 6, 4, 1, 2]
function findMissing(array) {
const unique = [...new Set(array)]
const sorted = unique.sort((a,b) => a - b)
const max = sorted[sorted.length - 1]
const min = sorted[0]
if (min > 1) return 1
if (max < 1) return 1
const positives = sorted.filter(num => num > 0)
for (let i = 1; i <= max; i ) {
if (positives[i - 1] !== i) {
return i
}
}
return max 1
}
console.log(findMissing(a))
console.log(findMissing([1,2,3,5,6,4, 8]))
console.log(findMissing([-1, -2, 1]))Here's an event faster approach which uses a Set which has a prototype function has() which is O(1) in checking whether an element exists, so we can event skip sorting the array, and traverse starting from 1 to the maximum value, and returning the missing integer when we find it.
The overall time complexity would be O(n) which is even better than the approach above. Think of it kind of like checking a dictionary or hashtable in terms of efficiency.
const a = [1, 3, 6, 4, 1, 2]
function findMissing(array) {
const set = new Set(array)
const max = Math.max(...set)
const min = Math.min(...set)
if (min > 1) return 1
if (max < 1) return 1
for (let i = 1; i <= max; i ) {
if (!set.has(i)) {
return i
}
}
return max 1
}
console.log(findMissing(a))
console.log(findMissing([1,2,3,5,6,4, 8]))
console.log(findMissing([-1, -2, 1]))CodePudding user response：
Here's an O(N) solution to the problem.
Basically, the answer must be between 1 and array.length 1, because the array can only disqualify at most array.length numbers. That means we can use an array of the same length as storage to solve the problem using O(N) memory.
We'll actually solve the problem for integers >= 0 and apply a bias to adapt it to the general case. The bias basically puts item X at index X - bias. e.g. the 5 gets stored at array[4]. The 1 gets stored at array[0]. (I set a default bias of 1 to suit your case.)
- For each element ("at the cursor"), we swap it with the element at its own index position in the array. e.g. if we see a 3 we move it to position 3, and move whatever was in position 3 back to where our cursor is.
- If we find that it already contains the element matching the index, then we can discard it (duplicates don't matter) and swap in the element at the end of the array instead, shrinking the array by 1. Similarly if we find a negative number or a number that is greater than the current length of the array, we can swap in the element at the end of the array.
- We continue following this chain until we locate a value with the same index as the cursor thus closing the chain. We increment the cursor and repeat.
- When we close the first chain in this manner, we will have put the 1 in the 1st position. Upon completing the next chain we will have put the 2 in the 2's position, etc. until we have put every element in its correct position.
- When we run out of elements, the cursor will be pointing at the position of the first missing element.
- Note: If we have put all elements in their correct position the cursor will be one past the end of the array, which still gives us the correct answer of whatever should be stored at array[length]. (With your bias of 1 this will N 1, as specified).
Here is an implementation and test suite of the cases you provided.
i is the cursor and j follows the chain.
let cases = [
/* expected result, array */
[5, [1, 3, 6, 4, 1, 2]],
[4, [1, 2, 3]],
[1, [-1, -3]],
[1, [2, 2, 2]],
];
console.log(
cases.every(([expected, array]) => findSmallest(array) === expected)
? 'pass' : 'fail');
function findSmallest([...a], bias = 1) {
let N = a.length;
let i = 0;
let j;
while (i < N) {
j = a[i] - bias;
if (j < i || j >= N) {
a[i] = a[--N];
} else if (j === i) {
i;
} else {
let J = a[j];
if (J === a[i]) {
a[j] = a[--N];
} else {
a[j] = a[i];
a[i] = J;
}
}
}
return i bias;
}