Increasing Triplet Subsequence | Live Coding with Explanation | Leetcode #334

To support us you can donate

Check out our other popular playlists:

If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful.

#coding #leetcode #programminglife #programmingisfun #programmer #tech #software #codinglife #leetcode

[deeksha]

The logic for this problem is wrong. It will not satisfy the condition i < j < k for the test case [1, 2, -1, 7, 5]

[MultiRaviji]

Intuitively what this solution does is keep track of lower the bounds for the first and second element of the subsequence. Instead of small and big I will call it first and second initially we have first = INF and second = INF. Also, I will simplify the edge test case : [1, 0, 2, 0, -1, 3]

Iteration One
first = 1 second = INF
Iteration Two
first = 0 second = INF
Iteration Three
first = 0 second = 2
Iteration Four (Nothing Changes)
first = 0 second = 2
Iteration Five (Confusing Part)
first = -1 second = 2
Iteration Six
return true; Since 3 > 2 && 3 > -1
Setting first = -1 is important, yet doesn't change the answer in this case since second = 2 implies that their existed a value that was previously smaller than 2. Now if you find any value greater that 2 we know their exist in an increasing triplet sub sequence. But notice if we had a test case like this [1, 0, 2, 0, -1, 0, 1] we now could see the importance of the updated lower bound for first = -1, so we we can have a correct lower bound for second = 0. And also note this answer ask for existence, and not to construct the triplet, as this solution wouldn't be able to in its current form.

PS. Copy paste from leetcode.

[narasimhakamath]

Should have gone through the test case until the end for the sample dataset you had taken into consideration.

[rohanagrawal]

This code will fail for a lot of testcases. For example - Consider the following case - {48, 43, 60, 2, 100}
Initially, i = j = k = INT_MAX
Lets iterate through the array
1st iteration: arr[0] < i, i.e., 48 < INT_MAX. Therefore, i = 48
i = 48, j = INT_MAX, k= INT_MAX
2nd iteration: arr[1] < i, i.e., 43 < 48. Therefore, i = 43
i = 43, j = INT_MAX, k= INT_MAX
3rd iteration: arr[2] < j, i.e., 60 < INT_MAX. Therefore, j = 60
i = 43, j = 60, k = INT_MAX
So far, things look good. However, everything goes wrong in the next iteration.
4th iteration: arr[3] < i, i.e., 2 < 43. Therefore, i = 2
i = 2, j = 60, k = INT_MAX
Note that after the 4th iteration, even though i < j < k but it fails the condition where the indices need to be in order.
To be more clear, lets denote the indices as x, y, z for the variables i, j, k respectively. Hence, x = 3, y = 2 and z = unassigned.
The basic condition of x < y < z fails here.
Continuing through the iterations,
5th iteration: arr[4] < k, i.e., 100 < INT_MAX. Therefore, k = 100
i = 2, j = 60, k= 100 and x = 3, y = 2, z = 4
The subsequence calculated is - {2, 60, 100} which doesn't exist as it fails x < y < z.
Furthermore, by observing the array, it is evident that the correct subsequence is - {43, 60, 100}

Please share a different approach for solving the same.
Thank you for your hard work.

[undeadredemption_]

Awesome explanation and easy to understand. Thanks

[devvarshney]

Kindly check your solution on the arr = {2, 1, 5, 0, 6} because the subsequence that your code return is (0, 5, 6) and the correct ans is (1, 5, 6) . So please clear that doubt

[BrunoPillare]

I Dont think that the solution is correct. Because we cannot always update the minimum elements. It do not ensure that the sequence is strictly increasing. Eg. is 20, 100, 10, 12, 5, 13. Here the sequence formed according to above logic is 5, 12, 13 which is not strictly increasing. So I feel the solution is wrong.

[movieswatchify]

[20, 100, 10, 12, 5, 13] for this input, above code returns triplet as 5 12, 13 and TRUE as answer, BUT indices i<j<k is not satisfied. Can someone please explain?

[bharathkammari]

The algorithm is fine but, please tell why you are doing what you are doing, so that we can understand better

[mikehan]

This is incorrect, you didn't check the order

[ganeshnidigonda]

very good explanation with the diagrams.

[edwardteach]

Python Solution:

class Solution(object):
def increasingTriplet(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums) <= 2:
return False

i = j = k = float('inf')
for idx, val in enumerate(nums):
if val <= i:
i = val
elif val <= j:
j = val
else:
return True

return False

[oneall]

code is working fine but the explanation is ambiguous .
Suppose testcase = [12, 11, 15, 2, 16, 18]
then what will be the triplet sequence. - 11, 15, 16 or 2, 16, 18.

with your approach it is coming out to be 2, 15, 16 which seems to be not correct.
It is possible that I am not understanding correctly but if you would have taken such type of example and showed us what will be the TRIPLET SEQUENCE as well then it would have been awesome.

THANKS for this code though

[gago]

every greedy algo sound like magic forvme, hard to prove but it works!

[kumarutkarsh]

DId via LIS, came for o(n) ... Thanks

[varshithbunny]

Mam i think code fails for some testcases example 48 43 60 2 75

[sahilsaxena]

Ma'am this code will fails
I tried on gfg
Ex- 48, 43, 60, 2, 93
Your output true
But actual false.

[sagarpotnis]

really nice visualization. thank you very much

[siobhanmarshall]

Hey umm this is amazing and it works, but then what if the numbers were [2, 1, 5, 0.6.8]? It'll still return true, but the question isn't getting answered the way it should. Or maybe I understood it wrong? Feel free to correct me if I am.

[thepinkcodon]

What a cute and brilliant solution, thanks!