Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit | Leetcode 1438 |Detailed
Вставка
- Опубліковано 27 сер 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 24th Video of our Playlist "Sliding Window : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good and standard Sliding Window Problem : Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit | 2 Approaches | Dry Runs | Thought Process | Leetcode 1438 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit | 2 Approaches | Dry Runs | Thought Process | Leetcode 1438 | codestorywithMIK
Company Tags : UBER
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach-1: Using Sliding Window + Heap
Algorithm: This approach employs two heaps (priority queues) to maintain the maximum and minimum values within the current sliding window.
Max-Heap: Keeps track of the maximum values.
Min-Heap: Keeps track of the minimum values.
Both heaps store pairs of values and their indices.
As the window slides, the heaps are updated to ensure that the difference between the maximum and minimum values within the window does not exceed the specified limit.
If the difference exceeds the limit, the start of the window (i) is adjusted, and elements are popped from the heaps if they fall outside the new window.
The length of the longest valid subarray is continuously updated.
Time Complexity: O(n log n) due to heap operations.
Space Complexity: O(n) to store elements in the heaps.
Approach-2: Using Sliding Window + Multiset
Algorithm: This approach uses a multiset to maintain all elements in the current sliding window, allowing efficient access to the minimum and maximum values.
As new elements are added to the window, they are inserted into the multiset.
If the difference between the maximum and minimum values exceeds the limit, the start of the window (i) is incremented, and the corresponding element is removed from the multiset.
The length of the longest valid subarray is updated in each iteration.
Time Complexity: O(n log n) due to multiset operations (insertions and deletions).
Space Complexity: O(n) to store elements in the multiset.
Comparison
Both approaches use a sliding window technique combined with a data structure that supports efficient retrieval of the minimum and maximum values within the window.
Approach-1 (Using Heaps):
More complex due to maintaining two heaps.
Slightly more operations required to keep the heaps balanced and valid.
Approach-2 (Using Multiset):
Simpler to implement.
Direct access to the minimum and maximum values using rbegin() and begin().
Both approaches have the same time and space complexity but differ in the data structures used and the specific implementation details.
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024
Correction - Video - 24
You have a God gifted talent of intelligence and explaining it so simply. Than you so much🎉
True ,wish I had teacher like him earlier!!!!
Please don't stop posting video and if you have time then please do contest discussion also
God Gifted Mic Bhai, Thank you for Explaining so easily
Nice you stopped writing topic name in video thumbnail. It is necessary to understand problem first and build Intuition. i hope you will not show topics in video thumbnail in your future videos as well :)
Yes Please Contest problems too...the hard and medium ones❤❤
Thanks, approach 2 was really amazing. I was able to solve it on my own with the 1st approach but what was more amazing was that you showed us why we need a TreeMap data structure while building the intuition.
today i did the first question with a multiset , amazing explanation ❤❤
00:07 Find the longest continuous subarray with an absolute difference less than or equal to a given limit
02:12 Finding the longest continuous subarray with absolute difference less than or equal to limit.
06:23 To validate a sub-array, find the difference between its maximum and minimum elements.
08:27 Identifying valid subarrays based on difference limit.
12:38 Using a heap can efficiently track the minimum element within the window.
14:43 Implementing window sliding technique for efficient computation
18:33 Analyzing subarrays based on element limits
20:47 Algorithm for finding longest continuous subarray with absolute difference less than or equal to limit
24:13 Dry runs help in gaining clarity for solving problems.
25:59 Understanding the shifting of elements in the max and min heaps during traversal.
29:41 Finding valid subarrays with absolute difference less than limit.
31:40 Iterating through the array and checking limits for valid subarrays
35:40 Algorithm for finding longest continuous subarray with absolute difference less than or equal to limit
38:07 Discussed time complexity and approach for a sliding window problem
41:58 Efficient data structure for finding maximum and minimum elements with a given limit
43:50 Explanation of using Multi Set in C++ for efficient operations
47:20 Explanation of using max heap and multi set for inserting and removing elements.
Thank you bhai
Complete legend. Detailed each step
Thank you MIK! You're the best
thanks for the multiple dry run
Thanks sir ❤ only question explain kr k pause krne bataya uske liye mere 😢 you care for us 😢😢 thank you so much
Thanks a lot sir!
bro pls add time stamp in future videos. It , saves lot of time.
Please resume dp concept series
Bhaiya pleas leetcode ke contest ke question ke solution bhi explain krdo please apki explanation boht badiya lagti h please.....
waiting for the series where you will do contest problems
I felt this was hard but man you explain so well.
I have solved this prolem using multiset, I think multiset wala approach is more intuitive than using priority queue
Thanks a lot bhaiya ❤❤ Bohot hi pyara explanation tha 🔥
Bhaiya weekend aagya..partion dp concept videos
Little correction !!!! TIme stamp 9:19 , a lil minute error , diff b/w max and min is 7 not 6
@codestorywithMIK Hi sir, you discuss the 2nd approach which is using the TreeMap but there also arises one problem i.e if we have all unique elements then we have to traverse through all the elements of the map as I think there is no any way to get the smallest and largest element directly in O(1) time complexity. Can you please discuss it?
At last, I really like your explanation of the question problem like a story, I want to thank you for your great videos
legit. thanks a lot legend
Great video as always
Amazing Expalnation 😊
Bhai aap please contest ki 3 and 4 problem discuss kara laro please bhai request h
Great explaination!
if its possible please make an explainer on the O(N) approach ie deque approach🙏🙏
Great Explanation Bhaiya!!! Thank you...
great explanation man ...
Awesome explanation sir
Sir my kind request please upload a video on today's contest 3rd question. It is quite difficult solving dp.
Exactly 💯
try to think something related to consecutive negative numbers and apply pick not pick conditions accordingly
+1
Solve "Leetcode : 239. Sliding Window Maximum" before attempting this.
Waiting for this ❤
Amazing Explainations!!😍
Amazing explanation man
Solved using Multiset as we can get min/max in O(1) . and deletion in O(1) whenever window's absolute difference exceed limit
bhai multiset jaise STLs ko kaha se parha ?
Can you share any good resource.
@@gui-codes gfg se padhle bhai
int longestSubarray(vector& nums, int limit) {
int ans = 1;
int n = nums.size();
int i = 0;
int j = 0;
multiset st;
while(j
Awesome as always.
Preety Good Easy Solution with multiset and sliding window
int longestSubarray(vector& nums, int limit) {
int ans = 1;
int n = nums.size();
int i = 0;
int j = 0;
multiset st;
while(j
amazing explanation
Why didn't we use two deques for maintaining min and Max of the window avoiding that extra log n term which comes with heap and multiset?
one doubt, pop should be O(1) right, as we just delete the top element....
the push is log(n) time
correct ?
please confirm...
Thank you so much
[1,5,6,7,8,10,6,5,6]
limit:- 4
Answer = 5
can you explain this example
please👃
sir make some more questions video on segment tree
Guru ji Longest Nice subarray pe solution bna do please
this question must be marked hard
sahi me yaar.
@@gui-codes nahi yarr multiset use krte ho toh bhot easy hai , easy medium hoga
bhaiya segmenr tree ki playlist continue krdo,interview h
@codestorywithMIK , Thanks for your so detailed video but how TreeMap store duplicate value ?
i think TreeSet does not store duplicate value but TreeMap can store
Bhaiya aapne bola tha weekend pe *longest valid parantheses* ka video daaloge... Please bhaiya ye important q h interview k liye
i tried using in tree set in java..but it doesn't store duplicate elements..
Sir, one thing i want to point out that you always take elements sorted in heaps.. But that's not always true in heaps, only the top element can be surely claimed as min or max... And heap structure changes on addition or deletion of elements to maintain that top value condition... So it's not good to talk like this that the max element will be in bottommost position in minheap or something like that. Though, i understand you're just taking that way to explain it better way but people can have misconception about heaps by this.
Correct me if I'm wrong.
Why st.erase(st. Find(nums[i])) why not st. Erase(nums[i])??
There are 3 variants of erase in multiset.
1) void erase (iterator position);
2) size_type erase (const value_type& val);
3) void erase (iterator first, iterator last);
If you use 1st one, it will only delete the single element pointed by the iterator position.
If you use 2nd one, it will delete all occurrences of that element from the multiset. We don’t want that here because we can have duplicate elements.
I do it with map and sliding window concept
Sir mereko kaise pata chalega ki isme heap use hoga question main ki nhi
I could solve this by sliding window and multiset.
Which notepad do you use?
sir mujhe yeh max heap ur min heap wala question smghj nhi aaya
Question says - difference b/w any two elements
Then why are we talking diff of largest and smallest?
See 5:03 in the video bro.
The question say difference b/w any two elements MUST not exceed limit.
So, for any subarray, instead of checking diference b/w every possible 2 elements pair (if they are crossing limit or not), you can simply check if the difference between highest and lowest number in that subarray is
Bhaiya tumara linkedin id thetho i will mention u in my leetcode acheivements
Hey,
That’s sweet of you ❤️
www.linkedin.com/in/mazhar-imam-khan-95a34ab3?
rep++
o(n) wala approach nahi bataye aap?
❤
💥💥💥💥💥explain most optimized solution from leetcode solution section💥💥💥💥💥💥💥💥💥💥💥💥💥💥💥💥💥💥
Can you make your video in english
50 mins for 1 qs explanation ??
please share your slides
TLE
//int n=nums.size(),ans=0;
//for(int i=0;i
day-23 of saying lord🫡