@@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)
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 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 :)
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 ?
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 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
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.
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
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 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])
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.
Suddenly my brain is not braining😂😂
This is funniest 🤣
Moving left pointer back to avoid duplicate was a bit tricky...
yes
Loving the explanation Hating the problem
hahahaaha 🤣
@@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)
yea.
AI is trash 😮💨
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 :)
You are welcome :)
Excellent expalination, I too comeup with the exact approach but struggle to code it. Thanks man.
nice :)
Very beautifully explained !
Thanks :)
good explanation as always, many thanks
Glad you liked it!
Nice explanation. Thanks. Just one tiny bug: when moving back left, we need to ensure we are not moving out of the array
but that condition wont arise coz we must have a break point otherwise the right pointer wouldnt stop!
@@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 :)
yep :)
Nice explanation, may I know which blackboard you are using?
Good explanation Sir.
Thanks :)
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 ?
can you please explain with an example
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?
Yea you can take priority queue but you will need 2 heaps. One for min and one for max
wonderful explain
Thanks :)
God damn, my head hurts hahaha
🤣 brain teaser 🧠
Thank you
welcome
thanks :)
welcome :)
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
yes.
But the candidates may differ and so you will endup maintaining all frequencies :)
@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
what an explanation!!!
thanks :)
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.
👍🏼
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
AI is useless 🥲
could explain why the n*(n+1)/2 come about?
You can enumerate and count.
it will be this always:)
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??"
yea, it was not your daily sliding window :o confusing
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
Anything is O(N)
Thankfully we dont need to consider constants :)
This guy ❤
:)
Time to practice more sliding window problems 😢
but this was an outlier :)
And i was just counting subarrays
Need to subtract the redundant ones :)
Your python does not submit on leetcode and provides wrong output. Kindly, please check
omg
How can AI take jobs if they can’t even convert codes 🥹
@nileshbhanot2776 betaa khud se code likh le cheating krne aa gya moo utha ker. Approach dekh code nhi
@@techdose4u Haha I tried to convert the cpp logic to python too but that also didn't work, i don't know why
I think it will work.
Is there any implementation issue ?
@@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])
sir is it possible if you can explain the segment or fenwick tree approach for this problem?
that will be overkill.
Nothing better than 2 pointer.
currently I am focusing on easy and optimal solutions.
Overkill is not recommended :)
why don't you move the left pointer to right man its striaght forward and less complicated for explaining!
would maintaining a index whenever I update max help last wala update will be stored and my next L would be ind+1;
The max may not be optimal.
ex. 8,7,1
repeatLimit: 2
Last max will give 8 but you needed 7 :)
I was with you until you start talking about moving L pointer.
You can rewatch and do dry run on examples to clear :)
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.
This was an outlier so cant blame anyone!