---
# System prepended metadata

title: RN x LULU

---

# RN x LULU


## 494. Target Sum

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

Example 2:

Input: nums = [1], target = 1
Output: 1

if target not reachable return 0

Sol1. backtracking

all_sum = sum(nums)

back-tracking -> pick idx as neg -> all_sum -= 2 * num

if all_sum < target -> skip
if all_sum = target -> res += 1
if all_sum > target -> dfs next idx

```python

def get_all_combinations(nums, target):
    all_sum = sum(nums)  # target 

    res = [0]
    visited = set()

    def dfs(idx, all_sum, bismask):
        if all_sum < target or idx >= len(nums):
            return

        if all_sum == target and bismask not in visited:
            res[0] += 1
            visited.add(bismask)

        # treat idx as neg
        dfs(idx + 1, all_sum - 2* nums[idx], bismask | (1<<idx))

        # treat idx as positive
        dfs(idx + 1, all_sum, bismask)
        
    dfs(0, all_sum, 0)
    return res[0]

# time: O(2 ** N) # len(num)
# space: O(2 ** N)
```
    
        
```python
def target_sum(nums, target):
    def dfs(index, remain):
    
        if (index, remain) in dp:
            return dp[(index, remain)]

        if index == len(nums) :
            if remain != 0:
                return 0
            else:
                return 1

        ways = 0
        # select +1
        ways += dfs(index + 1, remain - nums[index])
        # select -1
        ways += dfs(index + 1, remain + nums[index])
        
        dp[(index, remain)] = ways
        
        return ways
    
    return dfs(0, target)
```




Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

 

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

i < j < k
nums[i] < nums[k] < nums[j]


for x :
    find prev_larger y, smallest before y as z
    x > z
    
    y > x, comapre x > z ? => z < x < y
    

monotone decresing
[3,1,4,2]

[3]
[3, 1]
[4]
[4, 2], 2 : 4 is pre_larger 2, min before 4 is 1
        becasue 2 > 1 => 132 pattern 
        

[4, 3, 1,2]

[(6, _), (5, _)]    <- pop increase upper bound lower bound


```python
def find_pattern(nums):
    
    if len(nums) <= 2:
        return Fasle
    
    if nums[1] > nums[2]:
        stack = [(nums[1], nums[0])] # monotone decreasing stack
    else :
        stack = []
    
    min_before = min(nums[1], nums[0])
    for num in nums[2:] :
        
        while not stack and num >= stack[-1]:
            tmp = stack.pop()
        if stack and num > stack[-1][1]:
            return True
        stack.append((num, min_before))
        min_before = min(min_before, num)
        
    return False
        
            
                
```

## 334. Increasing Triplet Subsequence

1 <= nums.length <= 5 * 105
-2^31 <= nums[i] <= 2^31 - 1

Example 1:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.

Example 2:

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

Example 3:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.


[2,1,5,0,4,6]
[6] (5, 1)

[(2, 0)]
[(2, 0), (1, 0)]
[(5, 1)]  
[(5, 1), (0, 0)]  
[(5, 1), (4, 1)]  
[(6, 2)]   (5, 1), (4, 1)
     ^   = max(poped_item_count) + 1
val >= 2 -> 123 pattern exits

[54321]
[1523] -> can't


- sol1, 3N
[1523]
[1, 1, 1, 1]  # from start min val
[5, 5, 3, 3]  # from end max val
[1, 5, 2, 3]
       ^

- sol2, one pass, segment tree nlog n xxx



[1, 5, 2, 3]
          ^
? element <= 3

- sol3

[1, 5, 2, 3]

main a minimum queue with size two
[1, 5]
    ^
[1, 2]

-> true

```python
from heapq import heappush, heappop

def check_ott_pattern(nums):
    
    min_queue = []
    for i in nums:
        if not min_queue:
            min_queue.append(i)
        else:
            min_queue.append(min(min_queue[-1], i))
        
    max_queue = []
    for i in nums[::-1]:
        if not max_queue:
            max_queue.append(i)
        else:
            max_queue.append(max(max_queue[-1], i))
    
    for i, min_, max_ in zip(nums, min_queue, max_queue[::-1]):
        if i > min_ and i < max_:
            return True
    
    return False
        
```

https://leetcode.cn/problems/increasing-triplet-subsequence/solution/c-xian-xing-shi-jian-fu-za-du-xiang-xi-jie-xi-da-b/

```python=
def increasingTriplet(self, nums: List[int]) -> bool:
    if len(nums) <= 2:
        return False

    small = nums[0]
    mid = float("inf")

    for num in nums[1:]:
        if num > mid :
            #print("{}, {}, {}".format(small, mid, num))
            return True
        elif num > small : # small < num <= mid
            mid = num
        elif num <= small: # num <= small
            small = num

    return False
```


![](https://i.imgur.com/XDRenhN.png)
![](https://i.imgur.com/S0rJdA7.png)


fine LCA of start node & dest node 
find path of LCA to start & dest node

result 1 = reverse (LCA to start)
result 2 = LCA to dest node

result = result_1 + result_2


if LCA == start => result_2 

if LCA == dest => result_1

```python
def find_step(root, startValue, destValue):
    
    def findLCA(root, p, q):
        if root is None :
            return None
        if p == root.val or q == root.val :
            return root
        left = self.findLCA(root.left, p, q)
        right = self.findLCA(root.right, p, q)
        
        if left is None and right is None:
            return None
        if left is None:
            return right
        if right is None:
            return left
        return root
    
    lca = findLCA(root, startValue, destValue)
    
    # find path of lca to startNode

    def dfs(root, direction, target):
        if root is None :
            return
        if root.val == target:
            result[0] = cur_path.copy()
            return
        cur_path.append(direction)
        
        dfs(root.left, "L")
        dfs(root.right, "R")
        
        cur_path.pop()
        
        return
    
    result_lca_to_start = []
    cur_path = []
    dfs(lca, None, startValue)
    
    result_lca_to_end = []
    cur_path = []
    dfs(lca, None, endValue)
    
    result_up = "U"*len(result_lca_to_start[1:])
    result_down = "".join(result_lca_to_end[1:])
    
    if lca.val == startValue:
        return result_down
    elif lca.val == destValue:
        return result_up
    else :
        return result_down + result_up

```

![](https://i.imgur.com/mI4pmNQ.png)
![](https://i.imgur.com/FFTOZCi.png)

Constraints:

1 <= s.length <= 100
s contains only digits and may contain leading zero(s).


sol1. backtracking

226
 ^
^
res +=1

< O(2 ** N)

sol2. dp + backtracking


f(22665555) = f(22) * f(66) * f(55) * f(55)
    ^
    
f(123412341234) = f(1) * f(23412341234) + f(12) * (3412341234)

f(23412341234) = f(2) * f(3412341234) <-

f(idx) = f(idx + 1) + f(idx + 2)
f(idx+1) = f(idx + 2) + f(idx + 3)
f(idx+2) = f(idx + 3) + f(idx + 4)

N len of string
time: O(N) 
space: O(N)

```python
def decodeways(s):
    valid_strings = set(str(i) for i in range(10, 27))
    @cache
    def f(idx):        
        if s[idx] == 0:
            return 0
        else:
            if idx + 1 < len(s):
                res = f(idx+1)
            else:
                res = 1
                
            if idx + 2 < len(s) and s[idx:idx+2] in valid_strings:
                res += f(idx+2)
            return res
        
    return f(0)
```



## 2007. Find Original Array From Doubled Array

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

 

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].

Example 2:
Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:
Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

x = [a, b, c]
-> intput [b, a,  2*a, 2*b, 2*c, c]
-> output original x


[1,1,1,2,2,2]
[1,3,4,2,6,8]

sol : 

result = []
trace 1st ; put in set
trace 2nd ; 


[6,2,2,1,1,3]
result = [1,1,3]


sol1:

sort ; increasing; 
[1,1,2,2,2,2,3,6]

[4,4, 2, 2]







result = []
[1,1,3]

dict = {1 : 2 }

time : o(nlogn)
space : o(n)

```python
def find_ori(nums):
    
    if len(nums) % 2 :
        return []
    
    counter = collections.Counter(nums)
    # {1 : 2, 2 : 3, 4 : 1}
    unique_values = list(counter.keys())
    unique_values.sort()
    
    result = []
    for key in unique_values:
        count = counter[key]
        result = result + [key] * count
        
        if key * 2 not in counter :
            return []
        counter[key * 2] -= count
        if counter[key * 2] < 0 :
            return False
        
    return result
    
    
    
    
    
    
    
    Counter(nums)
    
    # 1, 1, 2, 2, 2
    # [1,1,2]
    # 1:2, 2:3, 4:0
    #      2:1  4:0
    
    
    nums.sort()
    count = {}
    result = []
    
    for num in nums:

        if num not in count :
            result.append(num)
            count[num] += 1
        
        
        
        
        
        if num % 2 :        
            if num not in count :
                count[num] = 1
            else:
                count[num] += 1
            result.append(num)
        else:
            half = num // 2 
            if half not in count :
                result.append(num)
                count[half] += 1
            else:
                
        
    
```





2,2,4,4,6,12




## 802. Find Eventual Safe States

802. Find Eventual Safe States

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

![](https://i.imgur.com/UNbEekx.png)


![](https://i.imgur.com/cu8r3Bb.png)



f(0) = f(1) & f(2)

f(1) = f(2) & f(3)

f(2) = f(5)


f
- with circle -> False
- all(f(path) for path in paths)


f(0) -> return f(1) & f(2)


```python
    def eventualSafeNodes(self, paths: List[List[int]]) -> List[int]:
        visited = set()
        dp = {}
        for idx, path in enumerate(paths):
            if not path:
                dp[idx] = True

        def check_safe(node, visited):
            if node in dp:
                return dp[node]
            
            for path in paths[node]:
                if visited & 1 << path or not check_safe(path, visited | 1 << path):
                    dp[node] = False
                    dp[path] = False
                    return False

            dp[node] = True
            return True

        res = []
        for i in range(len(paths)):
            visited = 0
            if check_safe(i, visited << i):
                res.append(i)

        return res
    
```



![](https://i.imgur.com/RT704me.png)

1 -> < i + 3

[1,0, 0, 0, 999]
[1,0, 0, 0, 999]
 ^          ^
 1          1  1

[1, 2, 5]
[3, 2, 1]

0 +1
3 -1

1 +2
3 -2

2 +5
3 -1

(0, +1), (1, +2), (2, +5), (3, -1), (3, -3), (3, -1)
max apples

day 0 : (0, 1) -> eat -> (0, 0)
day 1 : (1, 2) -> eat -> (1, 1)
day 2 : (2, 7) -> eat


[6,4]
[2,2]

day 0 : (0, 6) -> eat -> (0, 5)
day 1 : (0, 9) -> eat -> (0, 8)
day 2 : ()

[6, 4]
[2, 2]

[(2, 6), (3, 4)]

0 -> eat smallest 
[(2, 5), (3, 4)]

1 -> eat smallest 
[(2, 4), (3, 4)]
2 ->eat smallest 
[(3, 3)]

3 -> xx


[1, 2, 5] appls
[3, 3, 4] days

every day 1 

[4]
[3]

(3, 1)
(2, 2)
(1, 5)

sortedDict logn -> 

for i in sorted_dict:
    pass
    

## 337. House Robber III

![](https://i.imgur.com/iQI0y8t.png)

![](https://i.imgur.com/USI1EUt.png)

![](https://i.imgur.com/7o7xqkS.png)

      5
     /
    1
   /
  2 
 /
7


val2 = f(root, should_skip=True) 
     = f(root.left, should_skip=False) + f(root.right, should_skip=False)

val1 = f(root, should_skip=False)
     = max(f(root.left, should_skip=False) + f(root.right, should_skip=False)
     , root.val + f(root.left, should_skip=True) + f(root.right, should_skip=True) )


return f(root, should_skip=False)

```python

def get_score(root, should_skip):
    if root is None:
        return 0
    
    if should_skip:
        if hasattr(root, 'skip_val'):
            return root.skip_val
        res = get_score(root.left, should_skip=False) + f(root.right, should_skip=False)
        root.skip_val = res
        return root.skip_val
    else:
        if hasattr(root, 'not_skip_val'):
            return root.not_skip_val
        
        val1 = get_score(root.left, should_skip=False) + f(root.right, should_skip=False)
        val2 = root.val + get_score(root.left, should_skip=True) + f(root.right, should_skip=True)
        root.not_skip_val = max(val1, val2)
        return max(val1, val2)
    
return get_score(root, should_skip=False)
```

![](https://i.imgur.com/1VV9oHV.png)

score('abc') = count_start('a') + count_start('ab') + count_start('abc')



Input: words = ["abc","ab","bc","b"]
Output:        [5,4,3,2]

score('abc') = count_start('a') + 
               count_start('ab') + 
               count_start('abc')
               
               
sol :-1: 

```python
def count_appearence(words):
    counter = collections.defaultdict(int)
    for word in words:
         for i in len(word):
             sub_word = word[:(i+1)]
             counter[sub_word] += 1
                     
            
    momo = {}
    result = []
    for word in words:
        if word in memo :
            result.append(momo[word])
        else:
            score_word = 0
            for i in len(word):
                score += counter[word[:(i+1)]]
            momo[word] = score
            result.append(score)
            
    return result
                     
    
        
        
        
    memo = {}
    result = []
    for word in words:
     
        if word in memo:
            memo[word]
    
        for i in len(word):
             score('abc') = count_start('a') + 
                   count_start('ab') + 
                   count_start('abc')
        memo[word] = socre      
        
               
n * s (max length of word)
```

## 1268. Search Suggestions System


Example 1:

Input: 
products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"

Output: 

[["mobile","moneypot","monitor"],
 ["mobile","moneypot","monitor"],
 ["mouse","mousepad"],
 ["mouse","mousepad"],
 ["mouse","mousepad"]]
 
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].
After typing mou, mous and mouse the system suggests ["mouse","mousepad"].

Example 2:

Input: 
products = ["havana"], 
searchWord = "havana"
Output: 

[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Explanation: The only word "havana" will be always suggested while typing the search word.

m -> [m, m, m]
mou -> [mo, mo, mo]
mouse -> [mouse ... ]



m -> products -> O(n)
mo -> products -> O(2n)
mouse -> proudcts -> O(kn)  n (k) * (k+1)


Trie
m -> {'recomends': []}

len(searchWord) = k

n * k * logn

k 

```python
root = {'m': {
            'o': {
                l:{
                    
                    'recs': ["mobile"]
                }
                'recs': ["mobile"]
            },
            'recs': ["mobile"]}
        }
```


```python
class Trie():    
    def __init__(self, root):
        self.root = {}
        
    def insert(self, word):
        root = self.root
        for s in word:
            if s not in root:
                root[s] = {}
            root = root[s]
```


```python!
from heapq import heappushpop

class Trie():    
    def __init__(self, root, k):
        self.root = {}
        self.k = k
        
    def insert(self, word):
        root = self.root
        for s in word[:self.k]:
            if s not in root:
                root[s] = {}
            
            if len(root[s]['recs']) >= 3:
                heappushpop(root[s]['recs'], word)
            
            root = root[s]
    
    def lookup(self, word):
        root = self.root
        for s in word:
            if s in root:
                root = root[s]
            else:
                return []
        
        return root['recs']
        

trie = Trie()
for word in words:
    trie.insert(word)
    
res = []
stop = False
for k in range(len(search_word)):
    out = trie.lookup(k)
    if out and not stop:
        res.append(out)
    else:
        stop = True
        res.append([])
return res
        
```

```python
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
    res = []
    products.sort()
    print(products)

    l, r = 0, len(products) - 1
    for i in range(len(searchWord)):
        c = searchWord[i]

        # 當 i = 2 時(index= 0, 1, 2), 表示product字長至少要 3個字, 少於等於兩個字都刪除
        while l <= r and (len(products[l]) <= i or products[l][i] != c):
            l += 1
        while l <= r and (len(products[r]) <= i or products[r][i] != c):
            r -= 1

        res.append([])
        remain = r - l + 1
        for j in range(min(3, remain)):
            res[-1].append(products[l + j])

    return res
```

![](https://i.imgur.com/vkqn7zf.png)


```python!

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def insert_node(root, val);
    
    def dfs(root):
        
        if root is None:
            return TreeNode(val)
                
        if val > root.val:
            root.right = dfs(root.right)
        else :
            root.left = dfs(root.left)
            
        return root
            
    return dfs(root)
            
        
            
    
```

## 1110. Delete Nodes And Return Forest

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

![](https://i.imgur.com/2rANPgB.png)

```python

def del_values(root, to_delete):
    res = []
    dele = set(to_delete)
    if not dele:
        return root

    def dfs(root):
        if not root:
            return None

        if (root.val in dele):
            
            node = dfs(root.left)
            if node is not None:
                res.append(node)
            node = dfs(root.right)
            if node is not None:
                res.append(node)
                
            root.left = None
            root.right = None
            return None
        else:
            dfs(root.left)
            dfs(root.right)
        return root

    dfs(root)
    if root.val not in dele:
        res.append(root)

    retrun res


```e


## 809
![](https://i.imgur.com/jVXihma.png)

Input: s = "heeellooo", words = ["hello", "hi", "helo"]
Output: 1
Explanation: 
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.

     s = "heeellooo", 
words = ["hello", "hi", "helo"]


s =>       [(h:1), (e:3), (l : 2),   (o:3)] => stack

"hello" => [(h:1), (e:1), (l:  2),   (o:1)] => stack

compare same index
if char are diff => return False
if diff_count == 1=> return Fasle

return True

```python=

def check_extend(s, words):
    
    def char_count(s):
        stack = []
        for c in s :
            if not stack :
                stack.append([c, 1])
            else:
                if stack[-1][0] == c:
                    stack[-1][1] += 1
                else:
                    stack.append([c, 1])
        return stack
    
    
    result = 0
    stack_s = char_count(s)
    for word in words:
        stack_word = char_count(word)
        if len(stack_s) != len(stack_word):
            continue
        flag = True
        for i in range(len(stack_s)):
            if stack_s[i][0] != stack_word[i][0] or \
               stack_s[i][1] - stack_word[i][1] == 1:
                flag = False
                break
        if not flag:
            continue
        result += 1
        
    return result
    
    


```







counter(word) =>


1. different chars
2. 


heeellooo
hello

eeee
eee

count() - count() == 1 => (x) 





eeeeeeeeee
e



s =>       [(h:1), (e:3), (l : 2),   (o:3)]

"hello" => [(h:1), (e:1), (l:  2),   (o:1)]

e = 5
e = 2
eeeee
ee---



eeeee => e : 5
eee   => e : 3


s = "ooo"
word = "oo"

## 1834. Single-Threaded CPU

![](https://i.imgur.com/5toQVVH.png)

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows: 
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.
Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation: The events go as follows:
- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
- At time = 40, the CPU finishes task 1 and becomes idle.


sol1

priority queue

[(1,2), (2, 4), (3, 2) , ..]

1 + 2 -> 3

while queue[0][1] <= current_time 
    -> pop, .... pick minimum nlog
    -> push back others nlog

n^2 * logn
    
    
sol2

[(1,2), (2, 4), (3, 2) , ..]
  ^
available_queue = []

while queue[0][1] <= current_time:
    -> push back available_queue

if not available_queue:
    jump to next idx
elif available_queue[0] >= current_time and idx the end:
    jump to next idx
else:
    
    




O(nlogn)

O(n)

```python!
import heapq import heappush, heappop

from collections import dequeue
def get_the_execute_order(tasks):
    
    tasks = dequeue(sorted(((start, end), idx) for idx, (start, end) in enumerate(tasks)))
    
    current_time = -float(inf)

    available_queue = []
    res = []
    
    while tasks or available_queue:
        if tasks and tasks[0][1] <= current_time:
            idx, (start, period) = tasks.popleft()
            heappush(available_queue, (period, idx))
        elif available_queue:
            period, idx = heappop(available_queue)
            current_time += period
            res.append(idx)
        else:
            idx, (start, period) = tasks.popleft()
            current_time = start + period 
            res.append(idx)
            
    return res

```
            
```python=

def getOrder(self, tasks: List[List[int]]) -> List[int]:
    for i, t in enumerate(tasks):
        t.append(i)
    tasks.sort(key = lambda t : t[0])
    #print('tasks : {}'.format(tasks))

    minheap = []

    i = 0
    cur_time = 0
    result = []
    # minheap 裡面有東西 或 所有課程都還沒放入heap中時都要繼續看
    while minheap or i < len(tasks):
        #print(minheap)

        # minheap 裡面沒東西, 直接拉快時間到第一個可以處理的時間
        if not minheap :
            # 有時候, heap之前有東西, 剛被pop出來處理完, 
            # cur time反而比當前第一個task可進入queue的時間大(可能前依task處理太久)
            # 所以需要兩著取最大值
            cur_time = max(cur_time, tasks[i][0])

        # 把目前可以處理的任務加入;
        # 多加上 i < len(task) 確保後面index不會出問題
        # 如果已經都加入 heap過那就不用再加了
        while i < len(tasks) and cur_time >= tasks[i][0]:
            heapq.heappush(minheap, [tasks[i][1], tasks[i][2]])
            i += 1

        process_time, index = heapq.heappop(minheap)
        cur_time += process_time

        result.append(index)

    return result
```
        
    
## 1310 RN 
![](https://i.imgur.com/M0r1N2z.png)

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8] 


Explanation: 
The binary representation of the elements in the array are:

1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 

The XOR values for queries are:
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

xor => 1, 1 => 0
       1, 0 => 1
       0, 1 => 1
       0, 0 => 0
       
[0, 3] => 

1, 3, 4, 8
[0, 1] = > 2

0 xor 1
 3, 4, 8
 
 1 xor 3 xor 4 xor 8 
 
 range [i, j] = (0 xor ... xor j) xor (0 xor 1 xor .. xor (i -1))
 
 dict = {index : xor(0~index)}
 range [i, j] = dict[j] xor dict[i-1]
 
```python=
def xor_query(arr, queries):
    map_index_xorsum = {}
    xor_sum = 0
    for i, num in enumerate(arr):
        xor_sum ^= num
        map_index_xorsum[i] = xor_sum
    
    result = []
    for query in queries
        if query[0] == 0:
            result.append(map_index_xorsum[query[1]])
        else:
            result.append(map_index_xorsum[query[1]] ^ map_index_xorsum[query[0]-1]) 
            
    return result
        
```
 
## 698. Partition to K Equal Sum Subsets

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

Input: nums = [1,2,3,4], k = 3
Output: false
 

Constraints:

1 <= k <= nums.length <= 16
1 <= nums[i] <= 104
The frequency of each element is in the range [1, 4].



num_sum = sum([4,3,2,3,5,2,1]) 
num_sum % k != 0 -> false

elemnts = num_sum / k

k -> len(partitions) = k

nums= sorted(nums, reverse=True)
def dp(partitions, idx):
    pass
    
(0, 0, 0, 0), 0

(4, 0, 0, 0), 1

4,3,2,3,5
(4, 5, 5, 3), 5

limit -> each partition <= 5 -> put elements

stop -> (x, x, x, x)  == x

O(K ** N)

N * 2 ** N

```python!

num_sum = sum(nums)
if num_sum % k != 0:
    return False
else:
    goal = num_sum // k
    
if max(num_sum) > goal:
    return False

@cache
def dfs(partitions, idx):
    if all(j == goal for j in partitions):
        return True
    if idx >= len(nums):
        return False
    
    next_ = list(partitions)
    for i in range(k):
        if next_[i] + nums[idx] <= goal:
            next_[i] += nums[idx]
            next_ = tuple(sorted(next_))
            if dfs(next_, idx+1):
                return True
            next_[i] -= nums[k]
    return False
            
return dfs(tuple([0] * k), 0)

```

https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solution/hua-fen-wei-kge-xiang-deng-de-zi-ji-by-l-v66o/

(k ** N) * (klogk + N)



## RN 2178
![](https://i.imgur.com/K2E9Dhw.png)

2 + 4 + 6 + ... + ? <= final_sum

final_sum = 1000
2 + 4 + .. + k-2 + k = 996 
4 / 2 = 2 => 

k => k+2
k-2 => k

ex : final_sum = 16
2 + 4 + 6 = 12
2 + 4 + 10 = 16


2 + 4 + ... + 2k <= finalSum
(2 + 2k) * (k) / 2 = (1+k) * k <= finalSum
find max k
binay search => 
l = 1
r = finalSum

```python=
def max_split_even(finalSum):
 
    if finalSum % 2 : return []
    
    def get_sum(k):
        return (1+k) * k

    # find max k
    l = 1
    r = finalSum
    max_k = l
    while l <= r :
        mid = (l + r) // 2
        if get_sum(mid) <= finalSum:
            max_k = max(max_k, mid)
            l = mid + 1
        else :
            r = mid - 1
            
    # 2 + 4 + ... + 2k <= finalSum
    result = [2*x for x in range(1, mak_k+1)]
    diff = finalSum - sum(result)
    result[-1] += diff
    
    return result
    
```

## 

![](https://i.imgur.com/a5WgTlf.png)

![](https://i.imgur.com/V49oGJn.png)

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n2
Each value grid[i][j] is unique.


dp[i, j] = min(dp[i + i_diff, j + j_diff] for i_diff, j_diff in 4 direction)


bfs

dp[i, j] = min(dp[i, j], current_time)


dij

bfs -> (v, i, j) 

nearest path to (i, j) until visit (n-1, n-1)

n * n * 3
- > 4 step 
n ** 2 * 3 <-

(0, 0) -> (1, 1), (0, 2), (1,1) -> ()


```python
from heapq import heappush, heappop
# until meet n-1, n-1 -> return current_max
def get_max_wait_time(grids):
    init_value = grids[0][0]
    queue = [(grids[0][0], 0, 0)]
    n = len(grids)
    visited = set()
    def bfs():
        curren_max = None
        while queue:
            current_val, i, j  = heappop(queue)
            if curren_max is None or current_val > curren_max:
                curren_max = current_val
                
            if i == n-1 and j == n-1:
                return current_max - init_value
                
            for i_diff, j_diff in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                i_next = i + i_diff
                j_next = j + j_diff
                if i_next >= n or i_next < 0:
                    continue
                if j_next >= n or j_next < 0:
                    continue
                if i_next, j_next not in visited:
                    heappush((grids[i_next][j_next], i_next, j_next), queue)
                    visited.add((i_next, j_next))
    return bfs()
            
```


## 990 RN


![](https://i.imgur.com/F3my3Ql.png)


a==b

{a : [b, 1]}
{b : [a, 1]}

{b : [a, 0]}
{a : [b, 0]}


a != c

{c : }
{a : [c, 0]}

c == a

a == b => {a : [set(b), set(), 
           b : [set(a), set(),}
b != a => 

{a : [set(b), set(), 
 b : [set(a), set(),}
 
{a : [set(b), set(), 
 b : [set(a), set(),}
 
a == b
c == a
c != b

{a : [set(b, c), set(), 
 b : [set(a), set(),
 c : [set(a), set(),}

== => x, y is same => y par is x
== => x, z is same => z par is x
      y. z is same ? => union(y, z) is true. 
      
      


same_set = set()
for equa in equalation:
    if union(x, y) :
        same_set.add(x)
        same_set.add(y)
    
 
def find_par():
    return
    
def union(v1, v2):
 
 
 union(a, b)
 
 
 set(a, b, c)
 




 time :o(n)
 space o()
 
 
 
 
           
           
{a : [set(), set()]}

1


https://leetcode.com/contest/weekly-contest-312/problems/number-of-good-paths/

## 713. Subarray Product Less Than K

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

 

Example 1:

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Example 2:

Input: nums = [1,2,3], k = 0
Output: 0
 

Constraints:

1 <= nums.length <= 3 * 10^4
1 <= nums[i] <= 1000
0 <= k <= 10^6



[10,5,2,6], k = 100
 ^  ^  
 l  r
    l   r
      l-r

each l -> find first r such that prod() < 100

n^2

[10, 5, 2, 6]
queue = [], 
[10, 5]  -> 10, [10, 5]  res += 2
 ^
[5, 2, 6],  5, [5,2] [526], 2, [26], 6  res+= 6
 ^

if current >= k:
    res += len(queue)
    queue.pop(0)

if right == len(n) - 1:
   res += (n * n+ 1)  / 2

return res
```python

def get_valid_subarrays(nums, k):
    if k <= 1:
        return 0
    
    queue = []
    current_val = 1
    left = 0
    
    res = 0
    for right, num in enumerate(nums):
        queue.append(num)
        # current_val *= num
        # [10, 5, 2]
        # 0   1  2
        if current_val * num >= k:
            res += (right - left)
            
        current_val *= num
        while current_val >= k:
            out = queue.pop(0)
            current_val /= out
            left += 1
            
    n_ = len(queue)
    
    res += n_ * (n_ + 1) / 2
    return res

[10, 5, 2, 6]

left, right, queue, current_val, res
0   , 0    ,  10,  10
0   , 1    ,  10-5, 50
0   , 2,   ,  10-5-2, 100, 2
1   , 2,   ,  5-2, 10, 2
1   , 3,   ,  5-2-6, 60, 2

2 + 3 * 4 / 2 = 8
    
```

https://leetcode.cn/problems/subarray-product-less-than-k/solution/by-programmercoding-hqm4/


## 1395 RN

![](https://i.imgur.com/nNxAklK.png)



Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 

[2,5,3,4,1] => [2,3,4]

   123 pattern => 
       smaller <= 5 => larger; exist => count : count(smaller) * cont(larger)
       larger 

[2,5,3,4,1] => count of larget at right  => 
            => count of larget at left   =>  

=> count of larget at right

```python=
def count_pattern(nums):

    '''
    # count larger at right
    larger_right = []
    for i in range(len(nums)):
        count = 0
        for j in range(i+1, len(nums)):
            if nums[j] > nums[i]:
                count +=1
        larger_left.append(count)
        
    # count smaller at left
    smaller_left = []
    for i in range(len(nums)):
        count = 0
        for j in range(i-1):
            if nums[j] < nums[i]:
                count += 1
        smaller_left.append(count)
    '''

    def count_fun(direction, compare):
        result = []
        for i in range(len(nums)):
            count = 0
            if compare == "larger":
                for j in range(i+1, len(nums)):
                    if direction == "right"
                        if nums[j] > nums[i]:
                            count +=1
                    else:
                        if nums[j] < nums[i]:
                            count += 1
            elif compare == "smaller":
                    if direction == "right"
                        if nums[j] > nums[i]:
                            count +=1
                    else:
                        if nums[j] < nums[i]:
                            count += 1
            result.append(count)
        return result
        
    larger_right = count_fun("right", "larger")
    larger_left = count_fun("left", "larger")
    smaller_right = count_fun("right", "smaller")
    smaller_left = count_fun("left", "smaller")
    
    result = 0
    for i in range(1, len(nums)-1) :
        result +=  (larger_right[i] * smaller_left[i] + larger_left[i] * smaller_right[i])
        
    return result
    

    
```


## google 

1,2,3,2,1,1, k = 1

          ^
          
O(n)
```python

def get_len(nums, k):
    max_len = 0

    res = 0
    for num in nums:
        if num != k:
            res = 0
        else:
            res += 1
            max_len = max(max_len, res)

    return max_len

```

k = 1
num, res, max_len, 
1, 1, 1
2, 0, 1,
3, 0, 1,
2, 0, 1
1, 1, 1,
1, 2, 2

return max_len -> 2

1,2,3,2,1,1, every_likes


valid_nums <- [k1, k2, ... kn]

```python

def get_len(nums, every_likes):
    prev =  None
    res = defaultdict(int)
    valid_nums = set(every_likes)
    
    # 1| 2|3|2|1,1| 2,2| 3
        # ^
    
    for num in nums:
        if prev is None or num != prev:
            current_len = 1
            prev = num
        else:
            current_len += 1
        if num in valid_nums:
            res[num] = max(res[num], current_len)
     
    return [res[i] for i in every_likes]        
```

1,2,3,2,1,1
every_like = [1,2,3,4]

prev = None
res = {}

num, current_len, prev, res
1, 1, 1, {1: 1}
2, 1, 2, {1:1, 2:1},
3, 1, 3, {1:1, 2:1, 3:1},
2, 1, 2, {1:1, 2:1, 3:1},
1, 1, 1, {1:1, 2:1, 3:1},
1, 2, 1, {1:2, 2:1, 3:1},

{1:2, 2:1, 3:1}
return [2, 1, 1, 0]

