Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit | Leetcode 1438 |Detailed
492Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
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) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/longest...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
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