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 😅.
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.
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 💀💀💀
But remember when you hear monotonic, it means it is going in only one direction, like only increasing or only decreasing. If both are possible in single array of something, it is not monotonic anymore.
I think using TreeSet it is easy (TreeSet implementation of red black tree) class Solution { public int longestSubarray(int[] nums, int limit) { TreeSet 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; } }
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
Like duh why am I thinking so much about how to move the pointers to get the next smallest and the next largest. When i can just delegate that to a heap
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.
yeah it's not available in many platforms (fyi it should be available on neetcode io) usually people use it in place of treemaps, since python doesnt have that. in most interviews i think it would be acceptable to use it, since languages like Java and C++ have treemaps built in. that said, usually problems involving tree maps can also be solved with heaps, so i prefer the heap solutions since at least i know heaps are always available in python
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, 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 } }
Another Rust user 🫡 yeah I've noticed a lot of time that Rust solutions pass anyways even if they aren't optimal just because it runs too fast to quantify (lots of problems just run in 0ms), but it's more important to learn the correct algorithms even if you can technically cheat the system.
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.
I don't understand why he says Sliding Window doesn't work. After finding the first incorrect window [7,6,3,1] we don't move l++; we set l=r and move l-- while current window is correct. Why is this solution inefficient?
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
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 😅.
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.
You explanation is always the best. Always wait for your video!!!
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 💀💀💀
But remember when you hear monotonic, it means it is going in only one direction, like only increasing or only decreasing. If both are possible in single array of something, it is not monotonic anymore.
Solved it using 2 pqs, but came to see dq version. nlogn to n .. very well explained.
I think using TreeSet it is easy (TreeSet implementation of red black tree)
class Solution {
public int longestSubarray(int[] nums, int limit) {
TreeSet 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;
}
}
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
But the thought process of the second smallest and the second largest kinda led me to the two heaps solution
Like duh why am I thinking so much about how to move the pointers to get the next smallest and the next largest. When i can just delegate that to a heap
@@chaitanyasharma6270you are thinking right
I'm inexperienced with monotonic queues and used a multiset/heap - passed, but was very slow.
Solved it!!
no shot
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.
yeah it's not available in many platforms (fyi it should be available on neetcode io)
usually people use it in place of treemaps, since python doesnt have that. in most interviews i think it would be acceptable to use it, since languages like Java and C++ have treemaps built in.
that said, usually problems involving tree maps can also be solved with heaps, so i prefer the heap solutions since at least i know heaps are always available in python
@@NeetCodeIO Thanks for your response, especially the part about using heap!
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, 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
}
}
Another Rust user 🫡 yeah I've noticed a lot of time that Rust solutions pass anyways even if they aren't optimal just because it runs too fast to quantify (lots of problems just run in 0ms), but it's more important to learn the correct algorithms even if you can technically cheat the system.
i found a brute force and it worked for smaller number but failed at number with big arays
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.
thanks for showing the secret jutsu
🎉🎉🎉
using multiset is alot easier but time is nlogn
I don't understand why he says Sliding Window doesn't work.
After finding the first incorrect window [7,6,3,1] we don't move l++; we set l=r and move l-- while current window is correct.
Why is this solution inefficient?
Finally!!
your voice changed!
yeah i noticed this too, maybe he bought a new mic
Chain of Thought :skull:
queues gotta be the most unintuitive thing ever
why so late today??
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
Late This time.
Hint says use multiset.. Lol so misleading.