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

0:00 - Read the problem
3:09 - Drawing Explanation
10:29 - Coding Explanation

leetcode 1438

#neetcode #leetcode #python

[akash-kumar]

Slinding Window Max is probably very easy in comparison to this.

Important lesson form such problem is that don't waste more than 30 minutes on one problem and quickly look for solution 😅.

[kthtei]

got to point where I had to use sliding window with min, max value captured. I also tried using a deque before that, just couldn't sum these ideas together, it was close though. Pretty complicated one, wouldn't say hard but mid-hard ish.

[tirasjeffrey]

today i found out theres something called monotonic queues (increasing and decreasing queues), , , you know a question is tough as fu** when you're learning a new data structure 💀💀💀

[zz-yy-xx]

You explanation is always the best. Always wait for your video!!!

[amol_]

I think using TreeSet it is easy (TreeSet implementation of red black tree)

class Solution {
public int longestSubarray(int[] nums, int limit) {
TreeSet<Integer> set = new TreeSet<>((a, b) -> nums[a] == nums[b] ? a - b : nums[a] - nums[b]);

int left = 0;
int res = 1;

set.add(0);
for(int right = 1; right < nums.length; right++) {
set.add(right);
while(nums[set.last()] - nums[set.first()] > limit) {
set.remove(left++);
}

res = Math.max(res, right - left + 1);


}

return res;

}
}

[chaitanyasharma]

After yesterdays question i thought i could be smart and just use 4 pointers for the second smallest and the second largest elements as well. But i am not smart enough to implement it just used two heaps instead

[muffincodingchannel]

I'm inexperienced with monotonic queues and used a multiset/heap - passed, but was very slow.

[nirmalgurjar]

Solved it using 2 pqs, but came to see dq version. nlogn to n .. very well explained.

[thunderstorm-dc]

Hi neetcode,
Really appreciate your excellent video!
I have a question about the editorial in leetocde. In their python solution 2, SortedDict from sortedcontainers is used. However, sortedcontainers is not a bulid in package in python. So, are we allowed to used it in common OA platforms(eg codesignal)? I tried it in a random question in hackerrank and had an import error. I also tried to look it up online, but did not find an exact answer.

[bhavyajainnd]

I was able to solve it using a TreeMap. Basically I keep inserting (nums[right], count) to map. So min element is always map.first and max element is always map.last. The rest of the logic is the same. I did get a much slower time though but it passed unfortunately.

[meemee]

queues gotta be the most unintuitive thing ever

[oii]

i found a brute force and it worked for smaller number but failed at number with big arays

[EduarteBDO]

I think this question is medium because you can solve it in O^2, with a little trick:

impl Solution {
pub fn longest_subarray(nums: Vec<i32>, limit: i32) -> i32 {
let limit = limit as u32;
let mut res = 0;
for l in 0..nums.len() {
let mut min_val = i32::MAX;
let mut max_val = i32::MIN;
for r in l..nums.len() {
min_val = min_val.min(nums[r]);
max_val = max_val.max(nums[r]);

if min_val.abs_diff(max_val) > limit {
break;
}
res = res.max((r - l) as i32 + 1);
}
if res >= (nums.len() - l) as i32 {
break;
}
}

res
}
}

[akashverma]

using multiset is alot easier but time is nlogn

[CuriousAnonDev]

If someone is not that new to leetcode and dsa, this question is not that hard
Once you realise you need max and min
You try heap, then you realise there might be elements from out of the window in the heap, so you think of queue