Increasing Triplet Subsequence - LeetCode 334 - Python [O(n) time and O(1) space]
HTML-код
- Опубликовано: 1 окт 2024
- If you found this helpful, check out my channel for even **MORE VIDEOS**!!:)) www.youtube.co...
Explaining how to solve Increasing Triplet Subsequence in Python
Code: github.com/dee...
@1:23 Example walkthrough
@6:14 Code
@8:27 Code run-through + final example
Music: Bensound
Lemme know if you have any comments or questions!:)))
Consider the following array to be our input: [20, 100, 10, 12, 5, 13]
i will be 5
j will be 12
and k will be 13
and it will return True. however this is not a correct subsequence because j come before i not the opposite
I can't understand why is this a correct solution (I understand we don't return the indexes so our solution is correct because it returns true because 10 can be i 12 can be j 13 can be k)
I found this solution is widely used and i would appropriate it if someone explain to me why is it correct
I understand your question very well, because when I just went on my own, I also thought that if that was the case, it would be return False. But then I tried to find an example that was actually False, but returned True, and realized that it would not exist that way. I am trying to find a pattern. If we stop at j < i < k, num[i] < num[j] < num[k], and then return True, can we assume that there will be a number in front of j (the predecessor of i) that is less than j, so that is the sequence we want to be True.
Thanks for asking this question. Even I was not able to understand this. This solution is being used by most people in leetcode solutions. But it doesn't meet the i
I had a hard time understanding this at first, too. If you add three print statements under each of the conditions: "stage 1", "stage 2", and "stage 3" you'll see that at one point all the requirements of the problem statement were satisfied. Greedy algorithms solve problems in stages, so as long as we satisfy the requirements we've found a solution. This solution does not, however, tell you which indices make up the triplet, just that a triplet is present in the array.
Hey Ahmed! So you are absolutely correct on what the i, j, and k index values would be once we finish traversing the list ([20, 100, 10, 12, 5, 13])! And you are right again in saying that we would be returning True:) However, the reason we are returning True is due to the fact that as we are going through the list, we are trying to find what values i j and k can hold. Since a few people have the same questions, let's do a very complete and thorough walk-through and take a look at the input you provided together ☺
At index 0, we have value 20. At this point we set our i to be 20. (i and j were initialized to `inf` and 20 is less than i's curr value). At index 0, i=20, j=inf and there is no k.
At index 1, we have value 100. Here, we are greater than i's curr value so we set j=100. So curr state is: i=20, j=100, k is not present. And as we go through our next couple of indices we want to be on the lookout for a number greater than j ( > 100) in order to find the increasing triplet subsequence. If we don't find that, and say we find a number that is *not less than our current i, but it is less than our current j*, we would update j. Say the next number hypothetically was 80. In this case, we would update j to be 80 and this would allow us to look for a k that is now only greater than 80 rather than it being greater than 100. So looking at the next index...
At index 2, we have value 10. This is less than our i, so we will update i to be 10 instead of 20. Curr state: i=10, j=100, no k. Now it is important to note that we are not saying that [10,100] form the first 2 numbers of a valid increasing triplet. All we're saying right now is if we find a number > 100, we can return True. 10, 100 cannot be correct because 10 came after 100. What we get by updating 10, is allowing a potentially smaller number to take j's place (it no longer has to be greater than 20 it only has to be greater than 10). And this in turn allows more possibilities for k. If we never find that, then we would not be able to return True, but we are setting ourselves up in case we do find a number > 12. (At this moment though we are still looking for a number > 100 for k as our current valid increasing subsequence is [20,100] - this will never change until j is updated).
So when we get to index 3 valued at 12. We see that the new number is not < i (10) but it is < k (100) so we can update k to be 12. Curr state: i=10, j=12. No k. What this means is that now, we are looking for a k that is > 12 in order to return True. We don't care about being greater than 100 since there is another possible subsequence that could be made starting at [10,12] as long as we find a number greater than 12. The subsequence no longer needs to start with [20,100].
At index 4, we have value 5. This is < i (10) so we update i=5. But j is unchanged at 12 so we still need to find k > 12 as our current valid subsequence is still [10,12]. By updating i, we are decreasing the cutoff for j. It no longer needs to be 10. Any number greater than 5 that we see in the array from this point on, could be a valid j.
At index 5, value 13, we see that we are not < i ( 5) we are not < j (10). This means we are greater than our subsequence numbers and return True. Our valid subsequence is [10,12,13]. But our i,j,k values are 5,10,13 because in case we didn't find 13, we would still be traversing and the only thing we did is set us up for finding smaller j's, and k's. But we were still using [10,12] as our base subsequence since we never actually found a new number > 5 to set to for j.
It can def be a bit confusing if not gone through in detail so I hope this helps! And if you want to visualize this better, I def recommend looking at the code walk-through with the example at the end! (Timestamp @8:27)
Hope this helps Ahmed and let me know if you have any questions at allll!!:)))))
Addicted to ur way of solving
Love this Aryan!! Thx:)
One of the finest explanations you'll find on the internet.
thx Chittilla☺️
Its works for this problem but what if similar kind of problems like return first three numbers of those pair.For example[2,1,3,0,4,6] in this i want to return those first pair as 1,4,6 how can we solve these type of questions
can try this, if the middle was set and low was set after that, keep track of old low
public boolean increasingTriplet(int[] nums) {
int ans[] = new int [2];
int prevI = Integer.MAX_VALUE;
Arrays.fill(ans,Integer.MAX_VALUE);
boolean midSet = false;
for(int i= 0;i
You're the first person to make this easy to understand! Thank you!
Ofc!! Glad it was helpful☺️
Thanks so much!!! Super helpful!!!!!
☺️☺️
thank u so much
Great video. This makes sense after watching this video about 3 times. Sad, I don't think I would have come up with this solution.
Hey Deepti... your videos are really amazing... can you please do a video on this problem..
Input: [”long”, “very”, ”jump”, ”verylongjump”, “longjump”, ”iconstar”, ”star”, ”icon”, ”icons”, ”tar”, ”stars, ”iconstars”]
output:
“verylongjump”: [“very”, ”long”, ”jump”]
“verylongjump”: [“very”,”longjump”]
“iconstar”: [“icon”,””star”]
“iconstar”:[“icons”, ”tar”]
“iconstars”:[“icon”,”stars”]
Hey John for sure! Just let me know what this question is haha and I'll add it to my list:)
Thanks for this video. I don't know why I was stuck at j < i case.
loved your explanation
Thanks 🙏🏽
Epic
☺️
Nice explanation Thanks
That was helpful, thank you!
❤
Excellent explanation !
Top tier explanation !
Thank you
super helpful as always !!!!!
Ma'am can i know what we call this approach,is this greedy?IF yes plz,could u say how
Thanks a lot Deepti. Explanation was great !
Thanks sm Ankit!:)
Best and simplest solution with a neat explanation. Thanks Deepti
Great explanation! thanks!
Glad it was helpful Dhruva!:))
Thank you for saving me hours of headache!
good very good explanation~
Thx Leo!!:))
Thanks so so much
Of course!!!:)))
Thank you for the explain, but I still don't understand at the end if you change 6 to 4, it will return False.
Ofc! So if we change that last element to be 4, our new array is [2,1,5,0,4,4] instead of [2,1,5,0,4,6]. In the initial array we had a subsequence of [0,4,6] that formed our increasing triplet. However if we change it to be 4, we no longer have an increasing triple subsequence because then we would have [0,4,4] which is not strictly increasing (has to be greater than, not greater than equal to). So since we never find any strictly increasing subsequence in our new array, we would have to return False. Hope that helps Carina!
Thanks
:))
for the last array [2, 1, 5, 0 , 4, 6] my understanding is that [1, 4, 6] is the first triplet that is acceptable. So there are two triplets. Can any one explain how the code written here handles this? The reason I ask is if you write code that looks for only contiguous triplets this test case will pass, but fail for test cases that only have 1 triplet that is discontiguous.
Hey! Yes you're correct, there are two possible triplets here [0,4,6] and [1,4,6] both of which are perfectly acceptable enabling us to return True! As for the triples being continuous or not, since we are looking for a and not a being continuous is not really relevant. As long as we are in strictly increasing order for both indices and values we are good!:)) Hope this helps clarify and let me know if you have any other questions!
We are keeping in mind the indices and solving the question pointers i j k above the numbers does not mean they are in that order It mean that we could find a triplet like that this is what I understood.
Awsome 😇, but plz change the outro music next time😅
😂😂 HAHA alright I’ll see wat I do for my next vlog
@@DEEPTITALESRA Please don't change it!! I love this music so much! It seems like I achieved something. 😂😂😂
@@linxili6036 Hahaha sgg, kept it the same Linxi!!😂