Continuous Subarrays | Leetcode 2762

[@sivapradeep977]

Suddenly my brain is not braining😂😂

[@techdose4u]

This is funniest 🤣

[@Anikait-h3d]

Loving the explanation Hating the problem

[@techdose4u]

hahahaaha 🤣

[@heybeachMIN]

@@techdose4u Hi, your python code is not right. There is a small error there, at the end after the loop "for" you need to add to win_size + 1, that is, win_size = r - l + 1. I'm not exactly sure, but maybe this is because we don't add to the count without the condition max - min > 2 and always in the end we need to add to count and there the count in the loop starts from zero, so + 1. Sry for engl)

[@techdose4u]

yea. AI is trash 😮‍💨

[@rutikbhanushali957]

Moving left pointer back to avoid duplicate was a bit tricky...

[@techdose4u]

yes

[@ishanbhatt6067]

great call to include the complexity analysis! i came up with a similar solution but rejected it because i thought moving left pointer back would cause the complexity to become N-squared! thanks :)

[@techdose4u]

You are welcome :)

[@MP-ny3ep]

Very beautifully explained !

[@techdose4u]

Thanks :)

[@jaatharsh]

good explanation as always, many thanks

[@techdose4u]

Glad you liked it!

[@asgarantony]

Good explanation Sir.

[@techdose4u]

Thanks :)

[@freecourseplatformenglish2829]

Excellent expalination, I too comeup with the exact approach but struggle to code it. Thanks man.

[@techdose4u]

nice :)

[@freecourseplatformenglish2829]

@@techdose4u 💚💚💚

[@ujjwal_7531]

wonderful explain

[@techdose4u]

Thanks :)

[@smitshah2113]

Nice explanation. Thanks. Just one tiny bug: when moving back left, we need to ensure we are not moving out of the array

[@techdose4u]

but that condition wont arise coz we must have a break point otherwise the right pointer wouldnt stop!

[@smitshah2113]

@@techdose4u Ah, yes... the fact that the right pointer did stop means that there are two indices for which the subarray is not continuous. Hence we would stop moving left before going out of bounds. Thanks :)

[@techdose4u]

yep :)

[@Abhishek-e6d2c]

what an explanation!!!

[@techdose4u]

thanks :)

[@devmahad]

thanks :)

[@techdose4u]

welcome :)

[@lakithakare7387]

Thank you

[@techdose4u]

welcome

[@LinhHoang-ml1qo]

Hi sir, I think exactly the time complexity is O(2N) in the worst case l and r is both come to the last of index. Please confirm if my comment is false.Thank you so much and have a good day

[@techdose4u]

Anything is O(N) Thankfully we dont need to consider constants :)

[@gireeswar18]

Nice explanation, may I know which blackboard you are using?

[@pravyn350]

This guy ❤

[@techdose4u]

:)

[@vidhyarthisunav]

Your Python code in the link need minor enhancement. n = len(nums) should be used instead of right pointer to calculate the final number of subarrays to be addes outside the loop on line number 126. It should be win_size = n - left instead of win_size = right - left.

[@techdose4u]

👍🏼

[@nicolaswolyniec1354]

the python solution will give you a wrong answer. After finishing the loop, you can not use the right variable because the value is n-1 win_size = len(nums) - left count += (win_size * (win_size + 1)) // 2

[@techdose4u]

AI is useless 🥲

[@algorithmsanddatastructure3701]

i think we can adjust the left pointer also simply by maintaining the index and updating the index if the same number occuring multiple times

[@techdose4u]

yes. But the candidates may differ and so you will endup maintaining all frequencies :)

[@algorithmsanddatastructure3701]

@techdose4u i am thinking of maintaining the index of only max and min,so whenever difference is greater than the given number, it will be because max and min, so accordingly we can move the left pointer either to min or max which ever was present in the subarray

[@BigStin-0]

God damn, my head hurts hahaha

[@techdose4u]

🤣 brain teaser 🧠

[@dieformusic1705]

sir can i use priority queues to maintain min and max values so as to avoid the left movement of L pointer where i can update L pointer to the index choosen from the priority queues after checking the condition?

[@techdose4u]

Yea you can take priority queue but you will need 2 heaps. One for min and one for max

[@vishalgadade1585]

As you are moving pointer again to left when we found any fault Isn't it is disturbing cpu cycle? Because it is making knot of pointers during computation Can we optimize this knot ?

[@techdose4u]

can you please explain with an example

[@aryan51coder]

using deque makes it o(n) both time and space

[@SzrIsTaken786]

Had the sliding window part down, the maximum and minimum threw me off a bit but the formula is the part where I'm thinking "how the heck??"

[@techdose4u]

yea, it was not your daily sliding window :o confusing

[@vikasvoruganti7490]

Time to practice more sliding window problems 😢

[@techdose4u]

but this was an outlier :)

[@sailendrachettri8521]

And i was just counting subarrays

[@techdose4u]

Need to subtract the redundant ones :)

[@thetruebluesingaporeankid]

could explain why the n*(n+1)/2 come about?

[@techdose4u]

You can enumerate and count. it will be this always:)

[@AKProductionsTelugu]

why don't you move the left pointer to right man its striaght forward and less complicated for explaining!

[@firstyfirst]

would maintaining a index whenever I update max help last wala update will be stored and my next L would be ind+1;

[@techdose4u]

The max may not be optimal. ex. 8,7,1 repeatLimit: 2 Last max will give 8 but you needed 7 :)

[@eliomorningstar7392]

sir is it possible if you can explain the segment or fenwick tree approach for this problem?

[@techdose4u]

that will be overkill. Nothing better than 2 pointer. currently I am focusing on easy and optimal solutions. Overkill is not recommended :)

[@nileshbhanot2776]

Your python does not submit on leetcode and provides wrong output. Kindly, please check

[@techdose4u]

omg How can AI take jobs if they can’t even convert codes 🥹

[@satguy8481]

@nileshbhanot2776 betaa khud se code likh le cheating krne aa gya moo utha ker. Approach dekh code nhi

[@nileshbhanot2776]

@@techdose4u Haha I tried to convert the cpp logic to python too but that also didn't work, i don't know why

[@techdose4u]

I think it will work. Is there any implementation issue ?

[@nileshbhanot2776]

@@techdose4u def continuousSubarrays(self, nums: List[int]) -> int: l, res = 0, 0 mini, maxi = float("inf"), float("-inf") for r in range(len(nums)): maxi = max(nums[r], maxi) mini = min(nums[r], mini) if maxi - mini > 2: n = r - l res += ((n * (n + 1)) // 2) l = r maxi = nums[r] mini = nums[r] while l > 0 and abs(nums[r] - nums[l - 1])

[@B-Billy]

I was with you until you start talking about moving L pointer.

[@techdose4u]

You can rewatch and do dry run on examples to clear :)

[@AlbinSabu-y2v]

This is first time I see the window is going like a swing. That made me confusing(especially the double count & subtracton🥲). If I had never seen this algo my dumb brain could never figure out the soln.

[@techdose4u]

This was an outlier so cant blame anyone!