# Array ## Basic Knowledge ```python # list to tuple tp = tuple(ls) ``` 763. Partition Labels ``` letter_range = {} for i in reversed(range(len(S))): if S[i] not in letter_range: letter_range[S[i]] = i ans = [] left = 0 while left < len(S): right = letter_range.pop(S[left]) i = left + 1 while i < right: if S[i] in letter_range: right = max(right, letter_range.pop(S[i])) i += 1 ans.append(right - left + 1) left = right + 1 return ans ``` ``` last = {c: i for i, c in enumerate(S)} j = anchor = 0 ans = [] for i, c in enumerate(S): j = max(j, last[c]) if i == j: ans.append(i - anchor + 1) anchor = i + 1 return ans ``` - Learn how to use emurate make code clean and short - Access to hashmap is O(1), does not increase complexity - Total complxity is O(n) 406. Queue Reconstruction by Height ``` people = [x + [x[1]] for x in people] people = sorted(people, key = lambda x: (x[0], -x[1])) i = 0 ans = [] while i < len(people): if people[i][2] == 0: ans.append(people.pop(i)[:2]) i = 0 else: people[i][2] -= 1 i += 1 return ans ``` ``` people = sorted(people, key = lambda x: (-x[0], x[1])) res = [] for p in people: res.insert(p[1], p) return res ``` - insert according to height and index 739. Daily Temperatures - stack from first to last ``` ans = [0] * len(T) stack = [] for i, t in enumerate(T): while stack and stack[-1][0] < t: j = stack[-1][1] ans[j] = i - j stack.pop(-1) stack.append((t, i)) return ans ``` - stack from last to first ``` ans = [0] * len(T) stack = [] for i in range(len(T)-1, -1, -1): while stack and T[stack[-1]] <= T[i]: stack.pop() if stack: ans[i] = stack[-1] - i stack.append(i) return ans ``` No difference in logic. There is no need to use tuple in the first solution, access temperature use T[stack[-1]] 309. Best Time to Buy and Sell Stock with Cooldown - straight forward solution ``` d = len(prices) if d <= 1: return 0 buy = [0] * d sell = [0] * d buy[0], buy[1] = -prices[0], max(-prices[0], -prices[1]) sell[0], sell[1] = 0, max(prices[1] + buy[0], sell[0]) # buy: the max money in my pocket with having one share # sell: the max money in my pocket without any share for i in range(2, len(prices)): buy[i] = max(sell[i-2] - prices[i], buy[i-1]) sell[i] = max(prices[i] + buy[i-1], sell[i-1]) return max(buy[-1], sell[-1]) ``` 380. Insert Delete GetRandom O(1) - Set is not suitable for GetRandom function, because it is not indexable - Use a dict to record the index of each element and a list to store the current vales. - Always use the last element to fill in the slot left after removal 381. Insert Delete GetRandom O(1) - Duplicates allowed - Use set instead of list for storing index of a particular val (remove is O(1) opeartion) - Python set: - **discard** remove an element if it exists in the set, else **do nothing** - **remove** remove an element if it exists in the set, else **raise an error** - Python list: - **pop** remove the **last** element in the last, instead of first 716. Max Stack - To be concluded 39. Combination Sum - Typical DP problem - Do not use mix up the global variable and variable in helper function --> the main source of "max recursive depth reached" 957. Prison Cells After N Days - The ideas are super simple, but always take care the **index** problem. Index is everything. Please make it clear whether it starts from 0 or 1! - Why would you make this mistake? - Start is definitely 1 since everything comes back to the very first one? No, it is like # Graph Algorthm 399. Evaluate Division - Good Problem. It is very similiar to shortest path search algorithm and therefore can be solved with simliar ideas. - BFS/DFS (BFS is prefered probably), floyd & warshall (compute all pair shortest distance) - There if few things new. Just reduce the problem to some basic ones -