334. Increasing Triplet Subsequence - Day 11/31 Leetcode October Challenge

Larry solves and analyzes this Leetcode problem as both an interviewer and an interviewee. This is a live recording of a real engineer solving a problem live - no cuts or edits!

#leetcode #coding #programming

[PulIoFF]

Such a tricky solution. First I thought it’s wrong because we change the first number and leave the second one, so the index order might be wrong.
But then I tried couple of test cases in mind and understood that since we need to return just boolean number, that solution works fine.
Thanks!

[codewithcarter]

Agh! Just had to keep track of the smallest and second smallest numbers..

This helped a lot - thanks Larry! 😄

[incubou]

please don't ever stop recording these daily 🙏❤

[nitz]

This was really helpful, thank you so much!

[mitchellthomas]

Wouldn't this solution fail on an input of [20, 100, 10, 12, 5, 13]? We would be left with the sequence [5, 12, 13] and 5 has a greater index than 12

[mrlectus]

what if it is Increasing 4 Subsequence, how would the algorithm change?

[narolavarshil]

N=len(nums)
arr=[nums[0]]
for i in range(1, N):
x=nums[i]
if x>arr[-1]:
arr.append(x)
else:
index=bisect.bisect_left(arr, x)
arr[index]=x

if len(arr)>2:
return True
return False

#above code using longest increasing subsequence problem with O(N) time and O(1) space