Timeline for Find multiple duplicates in $n$ size data set in linear time
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 27, 2020 at 22:22 | vote | accept | theSongbird | ||
| Feb 1, 2018 at 17:46 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jan 2, 2018 at 17:32 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 3, 2017 at 17:21 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 3, 2017 at 16:54 | comment | added | ryan | @D.W. Your answer was why I assumed that modification would be allowed... or else it's not possible. Also, it's the standard/go-to answer. | |
| Nov 3, 2017 at 15:59 | history | edited | theSongbird | CC BY-SA 3.0 |
added 48 characters in body
|
| Nov 3, 2017 at 15:30 | answer | added | D.W.♦ | timeline score: 2 | |
| Nov 3, 2017 at 15:21 | history | edited | D.W.♦ | CC BY-SA 3.0 |
added 48 characters in body
|
| Nov 3, 2017 at 9:01 | comment | added | theSongbird | @D.W. is right. Modification of input data is not allowed. | |
| Nov 2, 2017 at 23:27 | comment | added | D.W.♦ | I don't think modifying the input array is permitted under the usual meaning of constant space complexity. theSongBird, can you edit the question to clarify whether the input array is allowed to be modified or not? | |
| Nov 2, 2017 at 23:05 | comment | added | ryan | @cardobard_box, you can make an assumption that they're signed if you want. Either way, it is constant space under a uniform cost model. If you're using a logarithmic cost model, then just scanning through and reading all the numbers would be $O(n \log_2 n)$. | |
| Nov 2, 2017 at 22:52 | comment | added | cardobard_box | @ryan That algorithm doesn't have constant space complexity: it needs 1 extra bit per element of $ A $ to run, regardless of whether you're negating each element or adding $ n $ (for example, if $ A $'s elements are 8-bit integers and $ n > 128 $, it won't work). It only works under the assumption that $ A $'s elements are unbounded, in which case talking about memory usage doesn't make sense, since we can allocate $ k $ bits by multiplying $ A[0] $ by $ 2^k $ and using the $ k $ least significant bits to encode whatever we want. | |
| Nov 2, 2017 at 21:55 | comment | added | ryan | Without a sign bit, you could "mark" it similarly by setting $A[A[i]] = n + A[A[i]]$. Then if a value is $> n$ when checking, you know it's true value is $A[x] - n$, and it's also an indicator that $x$ has been seen already. Also, now that you've basically realized a solution, I'll link you to --> here. | |
| Nov 2, 2017 at 21:54 | comment | added | ryan | Why couldn't we use this to count duplicates? Let's say we have $A = \{3, 3, 1, 2, 4\}$. We encounter $3$ so set $A[3] = 0 - A[3]$, we get $A = \{3, 3, -1, 2, 4\}$. We encounter the next $3$, so we first check the value of $A[3]$, if it's negative we know it's a duplicate. If it's positive then we set $A[3]$ to negative and continue. | |
| Nov 2, 2017 at 21:50 | comment | added | theSongbird | @ryan Well we could modify the sign bit (given we have signed data, if not modify the "virtual" location of the sign bit) and this won't consume unnecessary space. How does this sound? (although by modifying sign bits we can't really tell wether we use this to count duplicates) | |
| Nov 2, 2017 at 21:40 | comment | added | ryan | If we know $1 \leq A[i] \leq n-1$, what if we could "mark" it by somehow utilizing the location in the array that $A[i]$ indexes to? For example, We could put some extra info in the value at $A[A[i]]$ to say we've already seen $A[i]$. You would need to make sure not to mess up the true value at $A[A[i]]$ (or at least be able to recover it somehow). | |
| Nov 2, 2017 at 21:28 | comment | added | theSongbird | @ryan Since we know the search space is $[1, n-1]$, then I suppose we can "mark" the value to anything over n (some kind of mapping by modifying the array?). Although it seems to me that your suggestion requires looking "back" in the array. | |
| Nov 2, 2017 at 21:14 | history | edited | Raphael |
edited tags
|
|
| Nov 2, 2017 at 21:12 | comment | added | ryan | You know all the numbers will be in the range $[1, n-1]$. If you come across a value $1 \leq A[i] \leq n-1$, try to think of a way that you could "mark" it using the space you already have. By "mark" it, I mean, make a note somehow that the value $A[i]$ has already been seen. Then if we come across the same value again, say $A[j] = A[i]$, we can check if the value $A[j]$ has been marked to see if it is a duplicate. So you need to figure out a way to "mark" a value in-place (O(1) space). The key here is to note that $A[i]$ will be in the range $[1, n-1]$ (use this to your advantage!) | |
| Nov 2, 2017 at 20:55 | history | asked | theSongbird | CC BY-SA 3.0 |