Timeline for Given an array of integers, return the smallest positive integer not in it
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 8, 2020 at 23:20 | comment | added | Daniel | @PatrickRoberts, how would we go about writing a test for the algorithm you offered? | |
| Apr 5, 2019 at 9:54 | comment | added | Kanan Farzali | this is the only correct answer. | |
| Oct 30, 2017 at 16:32 | comment | added | Gabriel | This is exactly what I thought while reading the question. it's almost pseudocode. :) | |
| Oct 29, 2017 at 23:19 | history | edited | Patrick Roberts | CC BY-SA 3.0 |
corrected complexity analysis and conceded best performance to another answer
|
| Oct 29, 2017 at 21:07 | comment | added | wchargin |
@JensSchauder: Yes, I agree: simply allocating an array of length A.length seems much more straightforward to me.
|
|
| Oct 29, 2017 at 16:41 | comment | added | Jens Schauder | Sorry I was wrong and you are right, but using an array is still simpler than a Set, because for this case the identity is the perfect hash function, wouldn't it? | |
| Oct 29, 2017 at 15:47 | comment | added | wchargin | @PatrickRoberts: Sure they are. If the input array is the range of numbers from 1 to N inclusive, then the loop will run N times. N is an upper bound on the length of the loop, and moreover it is the best possible upper bound. | |
| Oct 29, 2017 at 15:17 | comment | added | Patrick Roberts |
@wchargin as I stated in my answer, the while loop is in constant time relative to N because the length of the array and the range of numbers to check are not related.
|
|
| Oct 29, 2017 at 15:16 | comment | added | wchargin |
@JensSchauder: Yes, it is: a Set in V8 or any other reasonable engine is implemented as a hash table with O(1) lookup. Patrick: it would matter; if set.has(i) took O(log N) time, then you would have Ω(N log N) time worst-case, because you invoke has as many as N times.
|
|
| Oct 29, 2017 at 14:42 | comment | added | Patrick Roberts | @JensSchauder Even if it was O(log N) (which it isn't), it doesn't matter. O(N + log N) = O(N). | |
| Oct 29, 2017 at 13:29 | comment | added | Jens Schauder | a "in" test on a set is not O(1) | |
| Oct 29, 2017 at 1:31 | comment | added | Philip Kirkbride | Thanks, this is also O(N) or O(N * log(N)), I will run a timed test between your answer and insertusernamehere. Fastest gets it. | |
| Oct 29, 2017 at 0:43 | history | edited | Patrick Roberts | CC BY-SA 3.0 |
mentioned space complexity of set
|
| Oct 29, 2017 at 0:37 | history | answered | Patrick Roberts | CC BY-SA 3.0 |