5 ms·
> Given an array of integers, write a function that will remove all duplicates. (be sure to add the obligatory followup, what is its runtime?) > The “aha” mome
by saagarjha 4y ago
> Given an array of integers, write a function that will remove all duplicates. (be sure to add the obligatory followup, what is its runtime?)
> The “aha” moment here comes if you realize that by sorting the input, you can just walk along the array with all duplicates being next to each other, resulting in an efficient solution.
You could also stick all the numbers in a set, since it seems like order doesn't matter…
- bitbearr 4y agoYeah, which improves the time complexity too. Plus many languages offer easy list to set conversion
- trinovantes 4y agoDoes it? Set insertion is O(log n) and you need to insert n items.
- orlp 4y agoNot if you use a hash set. This is expected O(n) time to de-duplicate an array of integers while maintaining the original order (more explicitly written than I normally would in Rust for didactical purposes): let mut hash_set = HashSet::new(); let mut len = 0; for i in 0..arr.len() { if !hash_set.contains(&arr[i]) { hash_set.insert(arr[i]); arr[len] = arr[i]; len += 1; } } arr.truncate(len);
- trinovantes 4y agoGood point but it's not exactly a free lunch. You're trading memory for the speedup. You can also use radix sort for what I'd like to call "fake" O(n) sort since physical hardware puts an upper limit on the hidden constant.
- saagarjha 4y agoRadix sort generally places far more restrictions on the keys than a set would.
- Cyphonetic 4y agoBut to order a list is O(n log n)
- trinovantes 4y agoIn the worst case, you need to insert every element into your set to find out if there's no duplicate hence it'll take O(n log n) too
- pclmulqdq 4y agoNot with a hash set - that gives you expected amortized O(1) insertion (yes, both expected and amortized). In contrast, a generalized sort is O(n log n), but you can sort numeric types in O(n).
- sfink 4y agoIt doesn't change the time complexity. Both are O(n). Your point about convenience stands, though. Actually, if you go into fully pedantic mode, the set version is worse. Hash-based set insertion is commonly taken to be O(1), but that depends on hash comparison being O(1), which depends on using single-word hash values, which means your n is bounded by eg 2^63 (50% occupancy) or whatever. Honestly fine in practice, but hash lookup isn't "as" O(1) as indexing into an array. (ie, it requires a less realistic cost model.) You also need your keys' length to be bounded by a constant. Otherwise just hashing everything will exceed O(n).
- orlp 4y agoO(1) indexing into an array is a much bigger lie in practice than relying on single-word hash values. It breaks down much, much sooner which is why we have multiple levels of caches to try and hide this. In reality random indexing is O(sqrt(n)) for 2D memory chips, and at best O(cbrt(n)) in our 3D physical world.
- Joker_vD 4y agoAnd adding two numbers is also O(m+n) where m, n is their length in bits, sure.
- deleted 4y ago[deleted]