Longest Consecutive Sequence | Leetcode(Hard) | GooGLe

In case you are thinking to buy courses, please check below:

#dsa #leetcode #placements

[vishal_rex]

I have a doubt. Let's take a test case: [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
While loop won't execute for 3 & 2 since 1 is present. But while loop will be executed for 1 since 0 is not present, and that will be executed (n-2) times here.
I think instead of iterating over nums which consists repeated elements, we can iterate over hashset then for 1 it will execute while loop only once resulting time complexity O(n) + O(n)

[AnkitMishra-mzxt]

If you are getting TLE, just declare it as unoredered_set<int> it will pass

[sandiptasardar]

It will give tle on leetcode. Use this instead
int nums) {
unordered_set<int> s;
for(int i=0;i<nums.size();i++)
{
s.insert(nums[i]);
}
int longest = 0;
for(int num : s) {
if(s.count(num - 1)) continue;
int j = 1;
while(s.count(num + j)) j++;
longest = max(longest, j);
}
return longest;

}

[codesmart]

after watching the intution i have coded it myself, way of your teaching is magic. i am feeling the improvment. Thanks a lot

[sidhaantgupta]

The hashset solution is actually slower in practice than the sorting one

[fromdjangoimport__help__]

if u r getting error use this simple solve -- set<int>s;

for(int i=0;i<num.size();i++)

{

s.insert(num[i]);

}

int count=0;

int maxi=0;

for(auto x:s)

{

count++;

maxi=max(maxi, count);

if(s.find(x+1)==s.end())

{

count=0;

}

}

return maxi;
}

[ritesh]

Yes it does give TLE just replace nums with hashSet in second for loop
I.e
for(int num: hashSet) not
for(int num: nums) this will make complexity to o(n) he missed this by mistake

[gauravraj]

Deciding at the last that time complexity of given solution is actually ~O(n) was really challenging. Thanks Striver for this explanation.

[sarswataryan]

For those of you who might be thinking how it is O(N) -
when you calculate carefully you will see that the while loop after traversal for each element of the array can maximum go upto the sum of N that's why the time complexity will add upto 3N only.
In case of N^2 every element has the possibility to go upto N times but that is not the case above, here all of them combined can go upto maximum of N.

[codingachinilgtifirbhikrrh]

1 doubt : the time complexity will not be O(N), if it contains duplicate elements in significant numbers(n-1, n-2 etc) beacuse then it will loop for every duplicate elements and it will b order of O(N^2)

[shri]

1.Insertion in a set takes O(log(n)) time,
2. we are inserting all the elements so we have N elements to enter
3. Thus building the set itself will take O(N*log(N))
how is the algorithm O(N) and not O(N*log(N))

[shohanur_rifat]

use an unordered map insert all of the values as keys and set the key's values to 0.When you iterate through the map, set the values of the keys equal to 1 when you have checked the value so that you know the next time you have look for it that it has been checked.

[mdaffan]

we can actually iterate through the set as the set is having sorted elements and can get to the solution
and it will also be O(n) solution

[tanyacharanpahadi]

maze aa gaye. after knowing the approach its difficult to believe that this question comes under hard category. Thank you striver really missed you. <3

[RahulSingh-detb]

Your way of approaching a solution is amazing and is sufficient enough to build own solution. without looking into code, that's the beauty of your channel.
Thanks!!

btw you mistakenly written set instead of unordered_set.

[agrajgarg]

After striver posted this video, the difficulty of this question got reduced to medium. Power of striver.

[gauravidesigns]

I stopped at 3:36 of your video and tried the problem and got AC . The moment you said it would be a hash set I got it. Now watching the whole video again after solving. Thank you sir.

[itsarAnkit]

how the time complexity is O(n) as insertion on map takes log(n) time and for n size array time will be O(nlogn)

[abhishekmore]

if we add just visited map, time can be reduced by 800ms .
unordered_map<int, int> mp, vis;
for(auto num:nums)
mp[num]=1;
int ans=0, cnt;

for(auto num:nums)
{
cnt=0;


cnt++, vis[num]=1, num++;
ans=max(ans, cnt);
}
return ans;

[ranasauravsingh]

UNDERSTOOD...!!!
Thanks, striver for the video... :)