132 Pattern - Leetcode 456 - Python
Vložit
- čas přidán 28. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/132-pat...
0:00 - Read the problem
0:58 - Drawing Explanation
7:49 - Coding Explanation
leetcode 456
#facebook #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
This was a bit tough for me honestly. Thanks for the explanation!!
Hi Harsh, I really don't understand, couldn't we just pick a number and check the left and right index number, if they're less than the current number then we have our subsequence?
@@abrahamowos The description is misleading. The numbers don't need to be consecutive. The order of indices matter though i
same here😃
@@mahnazakbari2504 exactly. this is the key here
This question feels exactly like the kind of Question Google would ask! ie. Something that at a first glance makes you think: "Oh this should be easy!" but in reality, 5 minutes into coding it, you realize how much the Question is kicking your ass.
I got the idea of monotonic stack, but I was confused how to implement this approach, Thanks for such a good explanation as always!
Definitely a problem I’d blank on and was a little confused at first but once you started to code, I understood what you were trying to do. Would love to see more problems where the optimal solution is using a data structure like stack, queues, etc.
What's the key observation that lets you know if you need to use a monostack? And how can you tell if you need an increasing or decreasing one? In this case, you wanted to find any previous larger element so monodecreasing stack. How can you tell that a stack is needed for a problem over a rabbit hole of DP or backtracking?
I agree with you. The explanation is great on how to implement the solution but lacking clarity on why this solution is working. I spend some time to figure this out and commented above with result of my thoughts. If you are interested, take a look and let me know what you think about it.
i think you can recognize that you need a stack if you want to look at the previous elements, so instead of brute-forcing it, you can just look at the previous "valid" elements from the stack. also you can assume that you'll always need a monotonic stack in case of previous/greater next or previous element. it's a pattern
If anyone still hasn't understood why this works, try running through the code once with this example: [3, 5, 0, 3, 4]. It helped me understand the use of the stack better (and the fact that we are trying to store the best possible combination of ( j , i ) in the stack). Great explanation btw!
Yeah the problem description is absolute ASS. They say "subsequence" and made me think (with the examples) that they have to be consecutive...
I must be dumb or something. I am still missing some understanding of this algorithm because I cannot understand why this algorithm works with this example.
@@ivanhu Essentially it's doing a lookback range-search as you go from left to right of array.
1. Push 3, nothing (effectively) to check.
2. Pop 3 (until empty) because 5 is greater, and you need to maintain monotonic stack which is non-increasing. Push 5 w/ min seen is 3 so far. Nothing to check.
3. Push 0 w/ min seen 3. Monotonic maintained.
4. Pop 0 because order not maintained otherwise. Don't pop 5 because 3 is less than top of stack at that point. Check this 3 is strictly in-between (5, 3). It's not, so push 3 w/ min seen 0 so far.
5. Pop (3, 0) because 4 is greater than 3. Stop at, once again, (5, 3) top of stack because 4 is less than 5. Check this 4 is strictly in-between (5,3). It is, so we're done.
In summary, as you can see, whenever you encounter a number larger than the top of your current stack (step-up from a lower number to higher, e.g., 6 -> 8, or -3 -> 1), you perform a "lookback" via your stack to see if you hit a stop as if you're building a tower of Hanoi. If so, you check to see if you have the winning condition; else, you keep stacking.
@@bentley2495 thanks for your explanation! Yet another example of positivity in the leetcode community.
@@bentley2495 Wait, it's NOT consecutive? Now I get it. WTF!
Thank you for such elegant explanation!
Thank you for the explanation, It was quite difficult coming up with a stack approach.
Why is this solution correct?
First thing first, thank you for all the great contents. Very impressed by the amount of effort that you are putting into this.
I'm still trying to grasp how to use the monotonic stack to solve such problems. I wish you could elaborate more on the algorithmic part of the solution. The explanation is great for the implementation part. It wasn't clear to me "why this solution is correct?"
Below are some questions that I wanted to know the answer for. I am also adding the answers that I came up with. (I like to get other's opinions on my thoughts.)
1. Is the current element in the loop "potential nums[j]" or "potential nums[k]"? The latter. (It took me a while to figure this out! ;-) )
2. Meanwhile we are using a decreasing monotonic stack to keep track of **some** intervals. What is the rational behind choosing this data structure? What intervals exactly is this data structure keeping track of? My understanding is that these are the intervals that a valid nums[k] should fall in. That's why I added this condition "if min_left
I've been thinking about this problem in a different way, which is probably equivalent to the explanation in this video
So what we want to do is, for every j index, find the smallest element to it's left , which is i, (we can do this using a min-prefix array) and find the largest value to the right that is still smaller than nums[j] but larger than nums[i]. This will be our k. It's easy to see why we want to do this, and to prove that if we cannot find such i and k for a given j, then j cannot be part of the solution (if it exists).
Everything after this is stuff I gathered from various articles and leetcode duscussions.
I think that the reason we are keeping the stack in decreasing order is to, in constant time, find such a k for every j. From what I gathered, at each point in time, we want the top of the stack to be the largest element to the right of j that satisfies this. If this were true, then the algorithm would make sense.
The intuition goes like this: say our nums array looks like ...4321. Then, we add 1,2 and 3 to our stack, so it looks like [1,2,3]. stack.top() == 3. It's clear that if our j points to 4, because the numbers in the stack are sorted and 4 > 3 then stack.top() is our k (the one we described above). So, as long as the nums array is reverse-sorted, this all makes sense.
Now, what if we come across an element in nums that is less than stack.top()? e.g. ...24321. The stack looks like [1,2,3,4] and our nums[j] is 2. 2 < stack.top() ( == 4). Well, we can just pop the stack until we get to an element that is less than 2, which is 1. After we do this, the stack property is once again maintained - the nums[k] corresponding to the new 2 is also 1.
But how do we know that the elements we popped will not be the greatest smaller elements to the right of some other nums[j]? We don't, and in fact, there are examples where it does just that.
For example, in the array [5,3,4,2,1], our stack goes like this:
[ ], [1], [1,2], [1,2,4], [1,2,3], [1,2,3,5]
So the largest smaller element than 5 to the left of it is 3, according to this algorithm, because it threw away 4 when popping the stack. If this were the suffix after a candidate nums[j], we would be throwing away "the best" k corresponding to this j.
So what I don't understand is, this algorithm throws away perfectly valid "2"-s for a given "3". In fact, it throws away optimal "3"-s. So how in the world does it give the correct answer in the end?
Please correct me if I misunderstood something.
@@Blackfir333 I agree.
It seems to me it will return an accurate true or false, but not pick up every example of the 132 pattern.
Eg [1 3 4 2 6 4 3 0]
picks up 142, 164, 143
But not 163
sheesh this was tricky !! Thanks for the explanation
A way to think about it is that the stack stores a potential j candidate with the best i candidate for that j. Then for each k checks if it is between them and returns True. While checking it removes j candidates that are sub-optimal(nums[candidate]
Protect NeetCode at all costs. This man is a legend.
Thinking it through, this is a great example of solving the bare minimum that the question asks! The question only wants a True or False answer, so we can use this quick solution. If the question wanted all the 1-3-2 pattern examples, this algorithm would fail - it misses cases because it's popped them off the stack.
Eg [1 3 4 2 6 4 3 0]
picks up 142, 164, 143
But not 163
I'd have missed that nuance.
Damn stacks are so difficult. Great video. Thanks a lot!
😭😭 Thank you NeetCode
Shouldn’t we start iterating from 2nd idx if we’re looking for k candidates by iterating through the array?
If this one came up in an interview im finished lmao I opened this question this morning and just couldn’t figure out how to use the stack properly to solve this
which tool do you use for drawing,writing in the video?
Thank you so much Neetcode!!!! Could you please upload a video on Leetcode 2104 next time
"sometimes it's inconsistent on leetcode but who cares" -> lmao
I think, solving for k first instead of i index is the first correct step towards solving this probelm.
Interesting problem, thanks!
Thanks for the explanation. 👍👍
Here is the c# version of it.
public class Solution
{
public bool Find132pattern(int[] nums)
{
Stack st = new ();
int curr_min = nums[0];
for (int i = 1; i < nums.Length; i++)
{
while (st.Any() && nums[i] >= st.Peek().num)
st.Pop();
if (st.Any() && nums[i] > st.Peek().min)
return true;
curr_min = Math.Min(nums[i], curr_min);
st.Push((nums[i], curr_min));
}
return false;
}
}
Thanks, amazing explanation!
Besides learning algorithms what I've also learnt on this channel:
if (faster than 5%) say("It's pretty efficient");
😉
Still got no clue about why exactly your algorithm works. How would you explain that to the interviewer? Interestingly, I solved right away the "suggested similar" "hard" problem of "trapping the rain water" - which was kind of very intuitive and somewhere between easy and medium for me... Maybe you should re-word your explanation in terms of "maximum and minimum from the right" or something like that?
I agree with you. The explanation is great on how to implement the solution but lacking clarity on why this solution is working. I spend some time to figure this out and commented above with the results of my thoughts. If you are interested, take a look and let me know what you think about it.
@@mahnazakbari2504 thanks, interesting thoughts you have there, unfortunately I still don't quite get it))))) So far I guess that's one of those "just because" problems/answers)
When i see the code for a monotonic decreasing stack it makes sense why it works but tbh in an interview i would have a hard time figuring out that we would need to use it.
I once had an idea to look at the array backward, so the problem could become "finding 231 pattern" in an array, but didn't come out a solution........ thanks for the explanation!
That was also a solution. you have to traverse it backwards , push only the values less than the top of the stack and pop whenever found a value grater than or equal to the top of the stack.
Have variable storing the last value popped from the stack. If the last value is grater than the ith value than that means the array has a 231 sequence from the back and 132 sequence from front, so we return true, if not we return false at the end.
I actually though of this . Using 2 stacks. One for finding immadiate max before and one for min but then some of the 132 pairs were getting missed . But from here i get that we just need a true or false return and not print all the pairs
Thank for explanation!
best and easy solution!!
Thank you for your great videos. I'm having a phone screening for one of the FAANG. I'm getting ready with your great drawing explanations. However, I can't use drawing on a phone screening because we don't have whiteboards. I'm just curious that how you managed to explain your solutions effectively in the real interview without drawing tools.
You can ask them to use a drawing app, or use a paper. And good luck for your interview
All the best
For phone only they'll listen to your thought process, what questions you ask (any assumptions, bounds, etc.), how you plan to tackle the solution (loop, stack, etc) and rationale for each.
Amazing solution
I just solved this question by SortedList
Your solution by stack is more efficiency, thanks.
Can you share your solution on how you did using sorted list?
Recruiters dont even reply to my applications but im going to study still as if they were
How come you cannot just keep two variables? The max , and curMin?
Why not just max, but need a decreasing stack
Keeping previous max and min will give the most flexible option already
Because min needs to come left of max. If you only keep track of curMin, it may not be left of max.
curMin keeps track of the minimum number left of the current number, not left of max
@@ericx3woo I mean what if you keep max, and curMin is left of this max?
It's like once we got a max, we pop everything smaller than it from stack anyway, keeping only max
@@hanklin4633 because each max have diff mins.
Consider [6, 8, 2, 4, 5]: there’s no 132 pattern. When 5 is pushed after 2 and 4 are popped, 8 looks like a max with a min of 2, but 8 had a min of 6, not 2. Tracking 3 variables makes sure that the min of 6 for max of 8 is stored.
how come you could come up with a clean solution so fast??!! Mine was quite messy...
“…and as you can see, it’s pretty efficient”. Yet it is only better than 20% 😂
That always makes laugh. But your explanations are still the best regardless. Got my job because of you. So thank you.
in this problem, what It help, is mentions
stack[-1][0] === stack[-1][j] and stack[-1][1] ===stack[-1][i] and n==k, in this way you find a way to store the information of nums[i] < nums[k]< nums[j] ....
I came up with a solution that passed 101/102 cases and TLE'd on the 102nd case. I found it more intuitive to maintain a hashmap, where key is nums[i] & value is a list of all nums[j] greater than nums[i], the values I append would be strictly increasing. If I came across a new nums[i] that is even lesser than my current nums[i], I start forming pairs from this point onwards.
Finally I iterate through the entire hashmap and for every k in the range j+1 --> len(nums), I find out if I can form a 132 pattern.
For whatever reason I thought of a number line, and thought the solution was finding out if a mountain ( /\ ) exists in the array.
A tricky problem, even knowing the answer, it does not seem to be straightfoward.
I added some pythonic comments to make more sense of the solution. Here is the code in Java. (Dang this was hard to understand):
public boolean find132pattern(int[] nums) {
if (nums.length < 3) return false;
// [nums[j], min(nums[:j]) = nums[i]], monotone decreasing in nums[j]
Stack stack = new Stack();
int currMin = nums[0]; // i candidate (min(nums[:j]))
for (int k = 1; k < nums.length; k++) {
// while not (nums[k] < nums[j])
while (!stack.isEmpty() && !(nums[k] < stack.peek()[0])) stack.pop();
// The while loop above ensures that nums[k] < nums[j].
// So only check that nums[i] = min(nums[:j]) < nums[k].
if (!stack.isEmpty() && stack.peek()[1] < nums[k]) return true;
stack.push(new int[]{ nums[k], currMin });
currMin = Math.min(currMin, nums[k]);
}
return false;
}
Couldn't solve even after knowing we need to use stack. I was trying to use Next greater element and Next smaller element kind of solution
What a tough problem - why is this a medium and not hard?
Great soln but no explanation of why we should've thought to use a stack in the first place.
Those who are still not clear about the concept can read this-
// Monotonic decreasing stack
// Lets try to compare with the brute force solution and try to understand this.
// in brute force we start with two variables i,j and try to find k such that nums[i] < nums[k] < nums[j]
// so the idea is while we search for k, we should have the prior knowledge of i and j, and j should be greater than
// both i and k, and k should be greater than i. Hence i is always the min element of the combination.(this is imp observation)
// Now, here we take int[] entry in stack. entry[0] will represent j and entry[1] will represent i, We iterate through the given array and try to find k.
/*
lets take this example - [-1,3,2,0]
DRY RUN--
push() [-1,-1]
pop(), push(). [3,-1]
next element [2,-1]
at this point we check top of stack and see 3>2 and 2>-1. so combo found.
----------------------------------------------------------------------------------------
1. We need to maintain a min element seen so far. We will take first element as min. so min=-1, this is our i so far.
We put [-1.-1] in stack.
2. Now we start looking for j and k, so we start putting elements in our stack along with min so far.
[-1,-1]
3. We need j and k which are greater than i, so we maintain a mono decreasing stack.
4. while(!stk.isEmpty() && nums[i]>=stk.peek()[0]){
pop() [-1,1]
}
5. when the above condition fails, we have two options
-the stack is empty, which means just push the [curr element, min so far]
-curr element is smaller than top element of stack.(it represents j->the middle element of 132 pattern)
Now, we just need to check, if the min_so_far(that is i) represented by stak.peek()[1] is less than curr element or not. if it is then we have found the pattern. return true
else we need to update the min and push in stack again.--> stack at this moment- push [3,-1]
JAVA SOLUTION
class Solution {
public boolean find132pattern(int[] nums) {
int n=nums.length;
int min=nums[0];
Stack stk = new Stack();//int,prev min
for(int i=0;i=stk.peek()[0]){
stk.pop();
}
if(!stk.isEmpty() && nums[i]>stk.peek()[1]){
return true;
}
stk.push(new int[] {nums[i],min});
min=Math.min(min, nums[i]);
}
return false;
}
}
*/
Can this be solved with dynamic programming?
No!
DP is used when sub-problem overlapping is present but in this case not.
I got TLE with dynamic programming. DP would be usefull if we had to find all the 132 patterns, but here we have to find only one
@@sounakbiswas2239 is this always like this? I've just started learning dynamic programming.
@@ilham7555 yes dynamic programming is like maintaining a cache so that you can avoid calculating same problem again and again, I am not an expert either, you will learn more of it eventually.
I was so close to the solution on my own but messed it up.
Great Explaination!
such a good explanation !!!
thanks
I had a hunch it was monotonic stack. But no idea how to implement it. You start the problem with "meh~ ill finish this in 10 minutes" and come out questioning youre programming skills.
What about this solution?
def check(A, i):
return A[i]
Please upload your python code to github, thank you
Hi can anybody explain why the time complexity is O(n) and not O(n²).
Because you are adding the elements on the go the maximum elements you will add in the stack will be n hence the maximum time pop will be called will be n
Now surely, there are 2 loops but the inner loop will run for a maximum of n time. So total complexity boils down to o(2*n) which is o n.
Hope you understood
See we are adding each element only once. And we are also popping elements but we can only pop an element only once.
So each element can be pushed once and popped once so time complexity is n irrespective of number of loops.
I don't see the point of using a stack.
Can't we just use a variable to track the min and max which we iterate through the list.
Can you do “Sum of Subarray Ranges” in O(n) time? If my comment can reach you. Thank you so much
Google prefix sums.
@@arsenypogosov7206 You rock dude
what a legend appreciate it
How are you working at Google and still able to make videos?
weekends and not everyone works 24/7 more like 15/7 but still lol
This is a much harder problem than originally thought
Agree!
super
couldnt this be solved with a 3 pointer sliding window ?
My thoughts exactly, confused is to why it wasn't chosen here.
Wondering the same, have you guys tried coding it?
Villainous Problem
it took 414 ms
Explanation wasn't upto the Neetcode standard I must say :p
Java:
class Solution {
public boolean find132pattern(int[] nums) {
Queue queue = new PriorityQueue( (a,b) -> a[0] - b[0]);
int min = Integer.MAX_VALUE;
for ( int n : nums) {
while ( !queue.isEmpty() && n >= queue.peek()[0] )
queue.poll();
if ( !queue.isEmpty() && queue.peek()[1] < n )
return true;
queue.add(new int[]{n,min});
min = Math.min(n,min);
}
return false;
}
}
Java: Dec stack as we want more options for k num
class Solution {
public boolean find132pattern(int[] nums) {
int prev_min=Integer.MAX_VALUE;
ArrayDeque stk = new ArrayDeque();//int,prev min
for(int n:nums){
while(!stk.isEmpty() && n>=stk.peek()[0]){
stk.pop();
}
if(!stk.isEmpty() && n>stk.peek()[1]){return true;}
stk.push(new int[] {n,prev_min});
prev_min=Math.min(prev_min,n);
}
return false;
}
}
Deceptively difficult ... ⛔
C++ code for brute force approach
class Solution {
public:
bool find132pattern(vector& nums) {
//coding the brute force
int k=2;
while(k
It wasn't clear to me why this solution is correct. You didn't explain why.
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
if len(nums) < 3:
return False
stack=[]
min_array=[-1]*len(nums)
min_array[0]=nums[0]
for i in range(1,len(nums)):
min_array[i]=min(min_array[i-1],nums[i])
for j in range(len(nums)-1,-1,-1):
if(nums[j]
The code fails this test case [3,3,0,3,4]
JAVA CODE :
class Solution {
public boolean find132pattern(int[] nums) {
int two = Integer.MIN_VALUE;
Stack st = new Stack();
for(int i = nums.length - 1; i >= 0; i--){
int one = nums[i];
while(!st.isEmpty() && st.peek() < one) two = st.pop();
if(st.isEmpty()){
st.push(one);
}else{
if(one < two) return true;
else st.push(one);
}
}
return false;
}
}
//dont need of keeping record of prefix. k>-1 means we have find some data like
//nums[j]>nums[k] and we just need to check if with i for nums[k]>nums[i]
//main reason this logic worked because we are moving from right to left
var find132pattern = function(nums) {
let len = nums.length;
if (len < 3) {
return false;
}
let stk = new Stack();
let k = -1;
for (let i = len - 1; i >= 0; i--) {
if (k > -1 && nums[k] > nums[i]) {
return true;
}
while (!stk.isEmpty() && nums[i] > nums[stk.peek()]) {
k = stk.pop();
}
stk.push(i);
}
return false;
};
class Stack {
constructor() {
this.stack = []
}
push(a) {
this.stack.push(a)
}
pop() {
return this.stack.pop()
}
peek() {
return this.stack[this.stack.length - 1]
}
size() {
return this.stack.length
}
isEmpty() {
return this.stack.length == 0
}
}