Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit | Leetcode 1438 |Detailed

Показать описание

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

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

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

codestorywithMIK

Рекомендации по теме

Комментарии

You have a God gifted talent of intelligence and explaining it so simply. Than you so much🎉

Polly

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.

manibhushankumarsingh

Please don't stop posting video and if you have time then please do contest discussion also

ramandeepsingh

God Gifted Mic Bhai, Thank you for Explaining so easily

kaustubhchaudhari

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.

pavittarkumarazad

today i did the first question with a multiset, amazing explanation ❤❤

StackUnderFlow

Yes Please Contest problems too...the hard and medium ones❤❤

anjanasahay

Thanks sir ❤ only question explain kr k pause krne bataya uske liye mere 😢 you care for us 😢😢 thank you so much

ShardulPrabhu

@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

manishdubey

I have solved this prolem using multiset, I think multiset wala approach is more intuitive than using priority queue

ashutoshpandey

Little correction !!!! TIme stamp 9:19, a lil minute error, diff b/w max and min is 7 not 6

CodeMode

Thanks a lot bhaiya ❤❤ Bohot hi pyara explanation tha 🔥

gauravbanerjee

I felt this was hard but man you explain so well.

gui-codes

bro pls add time stamp in future videos. It, saves lot of time.

ArpitDhimaan

Bhaiya pleas leetcode ke contest ke question ke solution bhi explain krdo please apki explanation boht badiya lagti h
waiting for the series where you will do contest problems

rahulnegi

Great explaination!
if its possible please make an explainer on the O(N) approach ie deque approach🙏🙏

arjunprasad

Great Explanation Bhaiya!!! Thank you...

priyanshkumar

Bhaiya weekend aagya..partion dp concept videos

venkatarohitpotnuru

Solved using Multiset as we can get min/max in O(1) . and deletion in O(1) whenever window's absolute difference exceed limit

surekhasonawane

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 :)

userfg

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit | Leetcode 1438 |Detailed

Longest Continuous Subarray with Absolute Diff Less than or Equal to Limit - Leetcode 1438 - Python

Leetcode - Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit | Leetcode 1438

Leetcode 1438 (Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit)

LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

✅ Longest Continuous Subarray With Abs Diff Less Than or Equal to Limit LeetCode - Sliding Window...

LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1438 Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

LeetCode 1438 | Longest Continuous Subarray With Absolute Diff ≤ Limit | ArrayDeque | Debug | Java...

1438 Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Leetcode 1438 Tutorial - Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (Leetcode Medium)

LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit - TS &...

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit [LeetCode]

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit || Easy Sliding Window

🌟 Day 45:Longest Continuous Subarray with Absolute Diff ≤ Limit

Leetcode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Leetcode 1438 - Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit [23/6/24]

Leetcode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit | Easy

Leetcode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit | Jser

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (LeetCode, Java)