---
# System prepended metadata

title: Array

---

# 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
- 
