# 334. Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

[9 2 7 3 4] -> true [2 3 4] is Increasing subsuence

bruute force

iter all element in arr
[9] -> [2 7 3 4] -> bigger than 9 []
[2] -> [7 3 4] -> bigger than 2 [3] -> bigger than 3 [4]

O(N**3)

-------------

[9 2 7 3 4]

dp [0 0 0 0 0]-> has small number before

from left - > right

[F F T T T] dp
[9 ]
[9 2 ]
[9 2 7 ]
[9 2*7 3 ] +++++ 3 > 7 > 2*
[9 2 7 3*4] -> true

O(N**2)

for i in range(len(arr)):
num = arr[i]
for j in range(i-1, -1, -1):
if arr[j] < num:
dp[i] = True
if dp[j]:
return True
return False

----

[9 2 7 3 4]

stack
9:[9]
2:pop(9) [2]
7:[2 7]
3:[2 3]
4:[2 3 4] -> len(stack) == 3 -> return True

TC O(N)

def findTriplet(arr):
    
    # edge case
    
    stack = []
    
    # [9 2 7 3 4]
    for num in arr:
        
        # 9 2 7 3 4
        
        while stack and stack[-1] > num:
            stack.pop() #p7
        
        stack.append(num)
        #[2 3 4]
        
        if len(stack) == 3:
            return True

    return False

[1 2 3 8 9]

[1 2 3 100 4 5 6]
(1) [1 2 3]
(2) [4 5 6]
-> ans += {[1,2,3]} + {[4,5,6]}

[a a+1 a+2 ... a+i ... a+n]
---------------
len = 1 [a+i]
len = 2 [a+i-1, a+i] [a+i, a+i+1]
len = n
---------------
left : (i+1), right (n-i) -> (a+i) * left * right
a * left * right + a+1 * left * right + ...

[1 2 3] -> [1 2]-> [2 3] -> [1] [2] [3] => 6+3+5+1+2+3
->math

[1 2 3] 6
[2 3] 6-1

[1 2 3] -> [1 2 3 4]
->[2 3] ->[2 3 4]

有一個分配給你的 project 目標不清楚，你會怎麼做
別人和你意見不一致，如何處理
在一個 diverse 的環境，會怎麼做
被分配到到一個新的 team，只有自己是新人，你會怎麼做
大家都有自己背景，如何對 team 有好的方向
如果 team 上來新人，你希望他有什麼特質
原本在做一件事情，中途發現遇到問題，轉變方向的經驗
接上，從這件事情學習到的東西