Timeline for Given an array of integers, return the smallest positive integer not in it
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2020 at 19:00 | history | edited | Snowhawk | CC BY-SA 4.0 |
deleted 6 characters in body
|
| May 23, 2020 at 18:54 | comment | added | Snowhawk | @AshokRaj Filtering is an unstable linear complexity algorithm that moves the wanted values from the back of an array to the locations of unwanted elements we forward scan through. Scanning, either to negate values or find the min/max, is also a linear complexity operation. | |
| May 23, 2020 at 18:50 | comment | added | Snowhawk | @AlexeySh. Adjusted the code so it filters out values larger than your array size (or first 100k). This is the reason for the timeout error. | |
| May 23, 2020 at 18:44 | history | edited | Snowhawk | CC BY-SA 4.0 |
deleted 155 characters in body
|
| Jul 18, 2019 at 4:37 | comment | added | Ashok Raj | this has o(n2) complexity :( | |
| Dec 12, 2018 at 18:20 | comment | added | Alexey Sh. | I'm getting TIMEOUT ERROR for large_1(1.66 sec), large_2( >6.00 sec, 4.97 sec) and large_3(1.080 s) performance tests. On my macbook pro I'm getting 10ms for 1000000 random positive array | |
| Nov 11, 2018 at 17:52 | comment | added | XDS | Addendum: If the integers are not distinct then maybe (and I could be wrong here) a better way to tackle the resulting issue would be to modify "Make the value in filtered[index] negative" to read "If filtered[index] is not already negative then make the value in filtered[index] negative". Again I am not entirely sure about this. | |
| Nov 11, 2018 at 17:32 | comment | added | XDS | In the case that the integers in the array are not distinct I think the statement "Filter non-positive values from A" needs to be complemented with "Filter non-positive & duplicate values from A". I am not sure if .distinct() is linear complexity though. | |
| Oct 29, 2017 at 13:55 | history | edited | Snowhawk | CC BY-SA 3.0 |
added 252 characters in body
|
| Oct 29, 2017 at 13:43 | history | answered | Snowhawk | CC BY-SA 3.0 |