Timeline for Given an array of integers, return the smallest positive integer not in it
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 31, 2021 at 21:35 | review | Suggested edits | |||
| May 31, 2021 at 23:51 | |||||
| Feb 8, 2021 at 10:57 | comment | added | janos | @KairatDoshekenov They are not, and this is easy to verify on leetcode. | |
| Feb 7, 2021 at 21:45 | comment | added | Kairat | nums[i] != i + 1 and nums[i] != nums[nums[i] - 1] are the same | |
| Sep 2, 2019 at 10:56 | comment | added | kivagant | Just curious, how much time did it take for you to write the solution? | |
| Oct 29, 2017 at 22:32 | comment | added | gnasher729 | @wvxvw: The number of exchanges is O (n). Each exchange is constant time, so the time is also O (n). Everything else in the algorithm is O (n). Total is O (n). | |
| Oct 29, 2017 at 22:10 | comment | added | wvxvw | @Sanchises on more thorough reading, I misunderstood the requirement. Now I see, this is correct. | |
| Oct 29, 2017 at 21:35 | comment | added | Sanchises |
@wvxvw Which is exactly what this algorithm is. We're having exactly n buckets of size 1, and we skip all collisions or elements that don't fit in any bucket. If you don't believe me, I encourage you to give a counterexample for which this algorithm runs above O(n).
|
|
| Oct 29, 2017 at 21:21 | comment | added | wvxvw |
@Sanchises bucket sort isn't really O(n)... it is only somewhere near that complexity when the stars align, like when you have very specific relationship between the size of array you need to sort and the range of integers that are in that array.
|
|
| Oct 29, 2017 at 19:23 | history | edited | janos | CC BY-SA 3.0 |
added 934 characters in body
|
| Oct 29, 2017 at 18:53 | vote | accept | Philip Kirkbride | ||
| Oct 29, 2017 at 18:24 | comment | added | Sanchises |
@wvxvw It's actually a lot like bucketsort, but even faster because collisions are simply skipped, making the worst case O(n).
|
|
| Oct 29, 2017 at 16:30 | comment | added | Sanchises |
@JensSchauder You could, but you would have O(n) additional space complexity, while this algorithm only uses O(1); just to get rid of some perceived complicatedness.
|
|
| Oct 29, 2017 at 13:28 | comment | added | Jens Schauder | swapping makes this algorithm complex. You can write the number in the correct position of a fresh array (or discard them when they are to large) a second iteration over that array finds the correct number. | |
| Oct 29, 2017 at 10:27 | comment | added | wvxvw |
@gnasher729 why do you only count the number exchanges, but not the exchanges themselves towards complexity? I believe, the algorithm above is a kind of comparison-based sorting, in a way similar to insertion sort... so, we aren't even talking about O(log n) here...
|
|
| Oct 28, 2017 at 22:18 | comment | added | gnasher729 | The exchange loop runs in O (n): That's because every exchange operation puts one value x into its right place that wasn't in the right place before, and because at most N values can be in the wrong place there can be at most N exchange operations. | |
| Oct 28, 2017 at 20:49 | comment | added | Oscar Smith |
What is the time complexity of this? It isn't even that easy to confirm that it terminates, not to mention is O(n)
|
|
| Oct 28, 2017 at 19:40 | history | edited | janos | CC BY-SA 3.0 |
deleted 1 character in body
|
| Oct 28, 2017 at 19:13 | history | answered | janos | CC BY-SA 3.0 |