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!

CodePudding user response：

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));

CodePudding user response：

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

CodePudding user response：

One way:

• check if array is empty and return 1
• sort array and remove duplicates with Set
• return 1 if last number of array is lower then 1
• loop thru array and return first missing number
• check if there was missing number, if wasn't return last 1

const a = []
const b = [-8, -3, -6]
const c = [1, 3, 6, 4, 1, 2]
const d = [1, 2, 3]

function findNum(arr) {
  let res
  if (!arr.length) res = 1
  arr = [...new Set(arr.sort((a, b) => a - b))]
  if (arr[arr.length - 1] < 1) res = 1
  else {
    for (let i = 1; i <= arr.length; i  ) {
      if (arr.indexOf(i) == -1) {
        res = i;
        break;
      }
    }
  }
  if (!res) return arr[arr.length - 1]   1
  return res
}
console.log(findNum(a))
console.log(findNum(b))
console.log(findNum(c))
console.log(findNum(d))