Increasing Triplet Subsequence | leetcode 334 | followup On Time O1 Space

#Array #Triplet #Increasing #December #Leetcode #Medium #Algorithm #DataStructure #Java #Preparation #NG #nickode #CookCodeTravel #CCTt

[codelite]

Pre-compute left min and right max really opened my brain. Just WOW

[Account-ficu]

I'm reading the comments and most people who complain probably didn't listen till the end of the video or paid any attention.
You covered all important steps to tackle this problem, giving us 3 approaches from least efficient all the way to the optimized, preferred solution, THANK YOU !

[Guoview]

That was very detailed and precise! Absolutely loved your explanation sir: from O(n) space reducing to O(1) space complexity. Really appreciate the help

[akshaychavan]

The idea is brilliant, but kind of slow.
Here are two approaches -
approach 1 -
def increasingTriplet(self, nums: List[int]) -> bool:
num1 = num2 = float('inf')
for n in nums:
if n <= num1:
num1 = n
elif n <= num2:
num2 = n
else:
return True
return False

approach 2 - the one explained in this video [Note that, I am using only 1 pass to find both leftMin array and rightMax array]
def increasingTriplet(self, nums: List[int]) -> bool:
leftMin, rightMax = [], []
n = len(nums)
j = n-1
minVal, maxVal = float('inf'), float('-inf')
for i in range(0, n):
minVal = min(minVal, nums[i])
maxVal = max(maxVal, nums[j])
leftMin.append(minVal)
rightMax.append(maxVal)
j-=1
for i in range(n):
if nums[i]>leftMin[i] and nums[i]<rightMax[n-i-1]: return True
return False

[NikhilKumar-odqh]

I think the test case [5, 1, 4, 2, 0, 3] fails with the third approach because it gives true by considering triplet (0, 2, 3) while the actual triplet needed to be considered is (1, 2, 3)

[anirudhatalmale]

nailed it .... awesome explanation from brute force to optimal

[guptapaaras]

Really poor explanation for the third approach. At least try to explain the intution rather than pre-compiled algorithm from leetcode.

[aayushpagare]

I tried it using Longest Increasing Subsequence and got TLE 😂

[adityan]

Nailed it !!! Loved your explanation !! :)

[bhagavanprasad]

Great solution,
Definitely become awesome if handwriting slightly better

[DonTaldo]

Thanks for sharing! The content is pretty good but the sound isn't the greatest, I'd consider doing some investment over there since the content is very valuable

[prasadm]

That second solution is wrong.... It fails for this kinda input 2, 1, 5, 4, 0, 6

[tanvishinde]

how to come up with this line of thinking !

[KundanKumar-imgs]

but when i am trying to dry run the example that you have given....the value of first came out to be 2, second 6 and third 7, which will return true...but the order in question is not according to ans....how??

[adarshnegi]

[20, 100, 10, 12, 5, 13]
for test case. value of f finally becomes 5, value of s beomes 12, how it still returning true. i am stuck with this, even a little help will be appreiciated.

[sharuk]

this is not O(1) SC bcz you take 2 extra arrays and its size depends on n there is no chance that we can say its O(1) SC

[Ammar]

your solution is wrong because your space complexity is O(N) and the required in question is O(1)

[sahilsaxena]

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

[gunjanagrawal]

really POOR explanation for 3rd approach