Smallest positive integer that does not occur in an array

Question

I am attempting this question using javascript. When I run my implementation on the website I get 11%, which asides from poor runtime states that I fail four hidden tests.

I cannot understand how my implementation is failing. I understand its not a great implementation and there are cleaner working answers in the linked question, but I am still curious what false logic I am using.

  A = A.filter(a => a > 0).sort()

  if (A.length === 0) {
    return 1
  }
  
  if (A.length === 1) {
    return A[0] + 1
  }

  for (let i = 0; i < A.length; i++) {
    let curr = A[i]
    let next = A[i + 1]

    if (curr !== next && (curr + 1) !== next) {
      return curr + 1
    }
  }

My logic is that since I am traversing a sorted array of positive integers from lowest to highest, if the current element + 1 doesn't equal the following element (i.e. [5,7] would be 5 + 1 != 7), there is a gap, which is the missing integer.

And if the loop gets all the way to the end, the last if statement still triggers since next is undefined, which would return the max value + 1.

dont know if this is it sort() does weird things with negative numbers in it . try something like `[-1,4,2,-3].sort()` and `[-1,4,2,-3].sort((a,b) => a-b)` to see what i meant — cmgchess, Apr 16 '23 at 19:57
Unless you are using [Typed Arrays](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/TypedArray), `sort()` will give you lexicographic order, not numeric order, i.e. [1,11,2] instead of [1,2,11] — Moritz Ringler, Apr 16 '23 at 20:09
@cmgchess `.sort()` is called upon an array without negative numbers — Bergi, Apr 16 '23 at 20:17
Your function fails to return the expected result (`1`) for simple inputs such as `[2,3]` or `[2]`. — Bergi, Apr 16 '23 at 20:18
Also, as Moritz mentioned: https://stackoverflow.com/questions/1063007/how-to-sort-an-array-of-integers-correctly — Bergi, Apr 16 '23 at 20:20
Thank you both for providing failing examples! ChatGPT failed to provide me a _single_ one.. The logical fallacies are clear as day now — myol, Apr 17 '23 at 06:46

Onyambu · Answer 1 · 2023-04-17T01:26:34.730

1

Instead of sorting the array, just look for the max of the array and use that within your function. Note that instead of working on arrays, you could use sets. The set .has method is faster than include method.

function  smallest_positive(ar){
    let set = new Set(ar)
    let mx = Math.max(...set);
    for(let i = 1; i < mx; i++) 
        if(!set.has(i)) return i;
    return mx < 1 ? 1: mx + 1;
}; 

console.log(smallest_positive([-1,4,2,-3]))
console.log(smallest_positive([1, 2, 3]))
console.log(smallest_positive([5,7]))
console.log(smallest_positive([1, 3, 6, 4, 1, 2]))

edited Apr 17 '23 at 01:26

answered Apr 17 '23 at 00:32

Onyambu

67,392
3
24
53

Repeatedly using `.includes()` is way worse than sorting the array – Bergi Apr 17 '23 at 01:08
1

@Bergi just fixed and used `.has`. That should be better – Onyambu Apr 17 '23 at 01:25
The complexity of this solution is `O(M)`, where `M = max(arr)`. The question states an expected complexity of `O(N)`. – Abhinav Mathur Apr 17 '23 at 03:30
1

@AbhinavMathur Not really. This is a short circuited function. Note that in whatever case you have, the order for this way less than N. I am not iterating through all numbers to M. I am just using M as the upper bound. Eg, let your array be `[1000, -1]`, max is 1000. but i will only iterate once since 1 is not in the array and short circuit the function thus returning 1. If you had `[-1,-2,-3,-4,-5]` max is `-1` and the for loop is completely ignored since `i>max` So we just return 1. – Onyambu Apr 17 '23 at 05:28
@AbhinavMathur In a worst case scenario where we have `[..., -5,-4,-3,-2,-1,0,1,2,3,4,5,6,...n]` note that i will iterate from 1 to n and then output n+1. Only iterating a subset of the array. Which is way better that iterating through all the elements of the vector. – Onyambu Apr 17 '23 at 05:28
@Onyambu can't you use `N` as the upper bound then? – Abhinav Mathur Apr 17 '23 at 13:51
@AbhinavMathur yes. But I would prefer the `N = Set.length` which is considerably smaller than `N = array.length` But still would work the same. Bothfunctions will be short circuited at the same value. So – Onyambu Apr 17 '23 at 14:57

Smallest positive integer that does not occur in an array

1 Answers1