Find lowest positive integer that does not appear in array

Question

I am trying to solve a leetcode type problem that is a practice problem that came with an upcoming code test I need to do for a job and I am having trouble with it. Can anyone help me understand whats going wrong?

I am essentially looking for the brute force option as I dont know algos/DS.

                                                       PROBLEM:

Write a function:

function solution(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.

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].

                            HERE IS MY SOLUTION: 

function solution(A) {
    let newArray = A.sort(function(a, b){return a-b})
        let lowestNumber = 1
        for(i=0; i < newArray.length; i++) {
            if(lowestNumber > newArray[0]) {
                return lowestNumber
            }
            if(lowestNumber == newArray[i]) {
                lowestNumber = lowestNumber + 1
            }
            if(i = newArray.length - 1) {
                return lowestNumber
            }  
    }
}

The below snippet isnt working like I expect it to. lowestNumber isnt being increased and also the loop is exiting here I believe.

if(lowestNumber == newArray[i]) {
                lowestNumber = lowestNumber + 1

Thanks for your help!

Answer 1

You can do this in O(N) using a Map():

• First set every number in the array.
• Then starting from 1 look for and return the missing number in the sequence.

function solution(arr) {
  const seen = new Map();

  for (let i = 0; i < arr.length; i++) {
    seen.set(arr[i]);
  }

  for (let i = 1; i <= arr.length + 1; i++) {
    if (!seen.has(i)) return i;
  }

  return 1;
}

console.log(solution([1, 3, 6, 4, 1, 2])); //-> 5
console.log(solution([1, 2, 3]));          //-> 4
console.log(solution([-1, -3]));           //-> 1

Answer 2

I think your > should be <, and the = in if(i = newArray.length - 1) should be ===.

And lowestNumber > newArray[0] will always be true if the array contains a negative number, so 1 will be returned.

Your effort seems careless, so you are going to have to up your game for the interview.

const integers = [5, -345, 562456, 95345, 4, 232, 1, 2, 3, 7, -457];

function solution(A) {
  let newArray = A.sort((a, b) => a - b);
  let lowestNumber = 1;
  for (let i = 0; i < newArray.length; i++) {
    const n = newArray[i];
    if (n > 0) {
      if (lowestNumber < n) {
        return lowestNumber;
      } else {
        lowestNumber = n + 1;
      }
    }
  }
  return lowestNumber;
}

console.log(solution(integers));

Answer 3

The fastest solution

function solution(A) {
  // write your code in JavaScript (Node.js 8.9.4)
  if (!A) return 1;
  A.sort();
  if (A[A.length - 1] < 1) return 1;
  const setA = new Set(A);
  let length = setA.size;
  for (let i = 1; i <= length; i++) {
    if (!setA.has(i)) {
      return i;
    }
  }

  return length + 1;
}

Answer 4

I have worked same problem for nowadays, and regardless the original answer, here is my version of finding least positive number which is missing the in the array.

function findLeastPositive(array) {
  const numbersSet = new Set(array);
  let leastPositiveNumber = 1;

  while(numbersSet.has(leastPositiveNumber)) {
    leastPositiveNumber++;
  }

  return leastPositiveNumber;

}

let result = findLeastPositive([1,2,3,4,5,6,7,8,9,0]);
console.log(result);
  
result = findLeastPositive([10,11,12,13,14,15,16,17,18,19]);
console.log(result);

There are sure similar answers floating on the internet but using given array length disturbing me of which I can't explain properly why we have to create second loop starts with 1 (known the least positive number) and to N.

Using hash table (I am using Set here) for lookup table is fine idea, as in it effect to overall performance O(N) (probably initialize the Set with array) and O(1) for checking if the value in the Set or not.

Then we need to set second loop for obvious reason that checking the the smallest positive number existence, starting from 1..N range. This is the part bugged me, so I decided to go for while loop. It's obvious rather why there's a for..loop starts from 1..N on which N is the length of the array.

Answer 5

Here is 100% code

function solution(A) {
    /**
     * create new array of positive numbers in given array,
     * if there sis no specific number in given array, in result array
     * that index will be undefine
     */
    const c = A.reduce((arr, cur) => {
        if(cur > 0) arr[cur] = 1;
        return arr;
    } , [1] )

    /**
     * return first undefined index
     */
    for(let i = 0; i < c.length; i++)
        if(!c[i]) return i;

    // otherwise return the maximum index in array
    return c.length;
}

Answer 6

    function solution(arr) {
     for (let i = 1; i <= arr.length + 1; i++) {
      if (!arr.includes(i)) return i;
     }
     return 1;
    }

    console.log(solution([1, 3, 6, 4, 1, 2])); //-> 5
    console.log(solution([1, 2, 3]));          //-> 4
    console.log(solution([-1, -3]));           //-> 1