Revisions to Given an array of integers, return the smallest positive integer not in it

added 268 characters in body

Source Link

edited Nov 1, 2017 at 8:27

2.2k
15
23

How about this solution, which – if I'm not mistaken – should fulfill all requirements:

create a second array
run through all elements of the input array
for each number set the respective key in the second array to true
run through the second array and return the first key which value comes back as undefined
if no match is found, return 1, so it will work for an empty input array as well

function findNumber(values) {
  let result = [];

  for (let i = 0; i < values.length; ++i) {
    if (0 <= values[i]) {
      result[values[i]] = true;
    }
  }

  for (let i = 1; i <= result.length; ++i) {
    if (undefined === result[i]) {
      return i;
    }
  }

  return 1
}

Try it yourself

^{Patrick and I had a discussion about the real time performance of our solutions (Here's Patrick's elegant solution using Set). We set up a test, containing around 1000 elements in the input array, including lots of negative values. You can try the test yourself.}

^{[JollyJoker suggested a similar version](https://codereview.stackexchange.com/questions/179037/given-an-array-of-integers-return-the-smallest-positive-integer-not-in-it/179053#comment340062_179053) in the comments using JavaScript's built-ins `filter`, `reduce` and `findIndex`. I fixed the suggested solution for edge cases and added it to the performance test. You can now [test all three solutions](https://jsfiddle.net/tdqwtsf8/). Keep in mind that these built-ins come with some overhead.} ^{[Janos added code for his algorithm as well](https://codereview.stackexchange.com/a/179042/21444) now. To complete the performance test, I've added it as well and [here's the final fiddle containing all four solutions](https://jsfiddle.net/7k7kwz92/).}

How about this solution, which – if I'm not mistaken – should fulfill all requirements:

create a second array
run through all elements of the input array
for each number set the respective key in the second array to true
run through the second array and return the first key which value comes back as undefined
if no match is found, return 1, so it will work for an empty input array as well

function findNumber(values) {
  let result = [];

  for (let i = 0; i < values.length; ++i) {
    if (0 <= values[i]) {
      result[values[i]] = true;
    }
  }

  for (let i = 1; i <= result.length; ++i) {
    if (undefined === result[i]) {
      return i;
    }
  }

  return 1
}

Try it yourself

^{Patrick and I had a discussion about the real time performance of our solutions (Here's Patrick's elegant solution using Set). We set up a test, containing around 1000 elements in the input array, including lots of negative values. You can try the test yourself.}

^{[JollyJoker suggested a similar version](https://codereview.stackexchange.com/questions/179037/given-an-array-of-integers-return-the-smallest-positive-integer-not-in-it/179053#comment340062_179053) in the comments using JavaScript's built-ins `filter`, `reduce` and `findIndex`. I fixed the suggested solution for edge cases and added it to the performance test. You can now [test all three solutions](https://jsfiddle.net/tdqwtsf8/). Keep in mind that these built-ins come with some overhead.}

How about this solution, which – if I'm not mistaken – should fulfill all requirements:

create a second array
run through all elements of the input array
for each number set the respective key in the second array to true
run through the second array and return the first key which value comes back as undefined
if no match is found, return 1, so it will work for an empty input array as well

function findNumber(values) {
  let result = [];

  for (let i = 0; i < values.length; ++i) {
    if (0 <= values[i]) {
      result[values[i]] = true;
    }
  }

  for (let i = 1; i <= result.length; ++i) {
    if (undefined === result[i]) {
      return i;
    }
  }

  return 1
}

Try it yourself

^{Patrick and I had a discussion about the real time performance of our solutions (Here's Patrick's elegant solution using Set). We set up a test, containing around 1000 elements in the input array, including lots of negative values. You can try the test yourself.}

^{[JollyJoker suggested a similar version](https://codereview.stackexchange.com/questions/179037/given-an-array-of-integers-return-the-smallest-positive-integer-not-in-it/179053#comment340062_179053) in the comments using JavaScript's built-ins `filter`, `reduce` and `findIndex`. I fixed the suggested solution for edge cases and added it to the performance test. You can now [test all three solutions](https://jsfiddle.net/tdqwtsf8/). Keep in mind that these built-ins come with some overhead.} ^{[Janos added code for his algorithm as well](https://codereview.stackexchange.com/a/179042/21444) now. To complete the performance test, I've added it as well and [here's the final fiddle containing all four solutions](https://jsfiddle.net/7k7kwz92/).}

added 524 characters in body

Source Link

edited Oct 30, 2017 at 13:48

insertusernamehere

2.2k
15
23

How about this solution? If, which – if I'm not mistaken, it – should fulfill theall requirements:

create a second array
run through all elements of the input array
for each number set the respective key in the second array to true
run through the second array and return the first key which value comes as back as undefined
if no match is found, return 1, so it will work for an empty input array as well

function findNumber(values) {
  let result = []; 

  for (let i = 0; i < values.length; ++i) {
    if (0 <= values[i]) {
      result[values[i]] = true;
    }
  }

  for (let i = 1; i <= result.length; ++i) {
    if (undefined === result[i]) {
      return i;
    }
  }

  return 1
}

Try it yourself

^{Patrick and I had a discussion about the real time performance of our solutions (Here's Patrick's elegant solution using Set). We set up a test, containing around 1000 elements in the input array, including lots of negative values. You can try the test yourself.}

^{[JollyJoker suggested a similar version](https://codereview.stackexchange.com/questions/179037/given-an-array-of-integers-return-the-smallest-positive-integer-not-in-it/179053#comment340062_179053) in the comments using JavaScript's built-ins `filter`, `reduce` and `findIndex`. I fixed the suggested solution for edge cases and added it to the performance test. You can now [test all three solutions](https://jsfiddle.net/tdqwtsf8/). Keep in mind that these built-ins come with some overhead.}

How about this solution? If I'm not mistaken, it should fulfill the requirements:

create a second array
run through all elements of the input array
for each number set the respective key in the second array to true
run through the second array and return the first key which value comes as back undefined
if no match is found, return 1, so it will work for an empty input array as well

function findNumber(values) {
  let result = [];
  for (let i = 0; i < values.length; ++i) {
    if (0 <= values[i]) {
      result[values[i]] = true;
    }
  }

  for (let i = 1; i <= result.length; ++i) {
    if (undefined === result[i]) {
      return i;
    }
  }

  return 1
}

Try it yourself

^{Patrick and I had a discussion about the real time performance of our solutions (Here's Patrick's elegant solution using Set). We set up a test, containing around 1000 elements in the input array, including lots of negative values. You can try the test yourself.}

How about this solution, which – if I'm not mistaken – should fulfill all requirements:

create a second array
run through all elements of the input array
for each number set the respective key in the second array to true
run through the second array and return the first key which value comes back as undefined
if no match is found, return 1, so it will work for an empty input array as well

function findNumber(values) {
  let result = []; 

  for (let i = 0; i < values.length; ++i) {
    if (0 <= values[i]) {
      result[values[i]] = true;
    }
  }

  for (let i = 1; i <= result.length; ++i) {
    if (undefined === result[i]) {
      return i;
    }
  }

  return 1
}

Try it yourself

^{Patrick and I had a discussion about the real time performance of our solutions (Here's Patrick's elegant solution using Set). We set up a test, containing around 1000 elements in the input array, including lots of negative values. You can try the test yourself.}

^{[JollyJoker suggested a similar version](https://codereview.stackexchange.com/questions/179037/given-an-array-of-integers-return-the-smallest-positive-integer-not-in-it/179053#comment340062_179053) in the comments using JavaScript's built-ins `filter`, `reduce` and `findIndex`. I fixed the suggested solution for edge cases and added it to the performance test. You can now [test all three solutions](https://jsfiddle.net/tdqwtsf8/). Keep in mind that these built-ins come with some overhead.}

added 365 characters in body

Source Link

edited Oct 29, 2017 at 9:40

insertusernamehere

2.2k
15
23

How about this solution? If I'm not mistaken, it should fulfill the requirements:

create a second array
run through all elements of the input array
for each number set the respective key in the second array to true
run through the second array and return the first key which value comes as back undefined
if no match is found, return 1, so it will work for an empty input array as well

function findNumber(values) {
  let result = [];
  for (let i = 0; i < values.length; ++i) {
    if (0 <= values[i]) {
      result[values[i]] = true;
    }
  }

  for (let i = 1; i <= result.length; ++i) {
    if (undefined === result[i]) {
      return i;
    }
  }

  return 1
}

Try it yourself

^{Patrick and I had a discussion about the real time performance of our solutions (Here's Patrick's elegant solution using Set). We set up a test, containing around 1000 elements in the input array, including lots of negative values. You can try the test yourself.}

How about this solution? If I'm not mistaken, it should fulfill the requirements:

create a second array
run through all elements of the input array
for each number set the respective key in the second array to true
run through the second array and return the first key which value comes as back undefined
if no match is found, return 1, so it will work for an empty input array as well

function findNumber(values) {
  let result = [];
  for (let i = 0; i < values.length; ++i) {
    if (0 <= values[i]) {
      result[values[i]] = true;
    }
  }

  for (let i = 1; i <= result.length; ++i) {
    if (undefined === result[i]) {
      return i;
    }
  }

  return 1
}

Try it yourself

How about this solution? If I'm not mistaken, it should fulfill the requirements:

create a second array
run through all elements of the input array
for each number set the respective key in the second array to true
run through the second array and return the first key which value comes as back undefined
if no match is found, return 1, so it will work for an empty input array as well

function findNumber(values) {
  let result = [];
  for (let i = 0; i < values.length; ++i) {
    if (0 <= values[i]) {
      result[values[i]] = true;
    }
  }

  for (let i = 1; i <= result.length; ++i) {
    if (undefined === result[i]) {
      return i;
    }
  }

  return 1
}

Try it yourself

^{Patrick and I had a discussion about the real time performance of our solutions (Here's Patrick's elegant solution using Set). We set up a test, containing around 1000 elements in the input array, including lots of negative values. You can try the test yourself.}

edited body

Source Link

edited Oct 29, 2017 at 9:18

insertusernamehere

2.2k
15
23

Loading

Source Link

created Oct 28, 2017 at 22:21

insertusernamehere

2.2k
15
23

Loading

Stack Exchange Network

Return to Answer