Interview Question | Longest Consecutive Sequence | #3 | Solution| Microsoft |amazon | leetcode 128

general
1
1 Like
2

set runs in O(log n). The algo is O(n log n)

3

This can be done without sets in O(n). If you’re using sets, then the complexity is O(n\log n).

1 Like
4

How to do it O(N) ? everybody on leetcode seems to use set or map and both set and map have time complexities of insert and find O(logN) not O(1).

1 Like
5

Good 'ol radix sort. Then loop over values to get the length of the longest consequetive sequence

6

Can you please explain a bit clearly. what is "good 'ol radix sort " ?

7

Most sorting algorithms are based on comparisons. With comparison-based sorting algorithms you can only achieve \mathcal{O}(n\log n) complexity.
However there are some sorting algorithms that use specifics of what is being sorted to improve the complexity. This is the case with radix sort.

The idea is as follows: first sort based on the least significant bit. Because this bit can only have two values this is essentially a split and can be done in O(n)
Then sort in the same way on the second to least significant bit, third to …, until the most significant bit. The time to sort becomes \mathcal{O}(bn) where b is the number of bits in the largest number. In the problem this would be b=32 giving \mathcal{O}(32n)=\mathcal{O}(n).

In practice however using the comparison-based sorts is often faster because often \log n < b, plus it is already implemented in the C++ standard library.

2 Likes
8

If we consider standard constraints i.e N<=10^5 then NlogN would give us lower time complexity than O(32N) so shouldn’t we use normal sorting and then check for the solution?

9

Correct.

10

So ideally there’s no O(N) solution of the problem?

11

It comes down to the fact that complexity is only an approximation of runtime. While radix sort is indeed \mathcal{O}(n) it will often be slower than the \mathcal{O}(n\log n) sorting algorithms.

I am curious if @aneee004’s approach is any different to the one I highlighted.

12

My approach is not any different. It’s either a hash set, or radix sort. The former is efficient if n is small. The later is O(n), yes but the constant factor will be huge if the range for A_i is big.

But hey! They asked us for an \mathcal O(n) solution. Let’s not care about the constant factor :stuck_out_tongue:.

3 Likes