# Mock Interview - Willy & Tristina

# Sep 1
## Willy [680. Valid Palindrome II](https://leetcode.com/problems/valid-palindrome-ii/)
https://leetcode.com/problems/valid-palindrome-ii/discuss/107751/C%2B%2B-clean-solution-O(n)

https://leetcode.com/problems/valid-palindrome-ii/discuss/404606/C%2B%2B-Easy-to-understand
:::info
s = 'aba'
output = True

s = 'abca'
'aca', 'aba'
output = True

s = 'abcda'
output = False

s = "abcdedca"
1 2
already_remove = flase;
if (s[index1] != s[index2]) {
if (s[index1] == s[index2-1]) {
index2--
already_remove = true
}
else if (s[index1+1] == s[index2])
index1++
already_remove = true
else
return false;
}
end condition: index1 >= index2

Palindrome (回文)
2
abcdedca
1
2
ebcbbececabbacecbbcbe
1

:::

    bool temp_string(string s) {
        int index1 = 0, index2 = s.size()-1;
        int diff = -1;
        bool remove = false;
        
        while(index1 < index2) {
            if (s[index1] != s[index2]) {
            
                if (remove == true && diff != 0 ) {
                    index1 = diff;
                    index2 = s.size() - 1 - diff;
                    diff = 0;
                    remove = false;
                }
            
                if (diff > -1) {
                    if (remove == false && s[index1+1] == s[index2]) {
                        index1++;
                        remove = true;
                    } else if (remove == false && s[index1] == s[index2-1]) {
                        index2--;
                        remove = true;
                    } 
                    else
                        return false;
                }
            
                if (remove == false && s[index1] == s[index2-1]) {
                    index2--;
                    remove = true;
                    diff = index1;
                }
                else if (remove == false && s[index1+1] == s[index2]) {
                    index1++;
                    remove = true;
                    diff = index2;
                }
                else
                    return false;
            }
            index1++;
            index2--;
        }
        return true;
    }
    
    

-------------------------
## Tristina [746. Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)
:::info
cost= [10, 30, 40, 10] ""
mincost
1. every step min number
2. sum minize

4,3
4-> (3,2)#10
3-> (2,1)#10
2-> (1,0)#10
3-> (2,1)#10
2-> (1,0)#10
1 -> cost[1]#30
0 -> cost[0]#10
1-> cost[1]#30

#give sub array
#return minSum

:::

#cost= "" [10, 30, 40, 10] ""
#           [10, 30, 50, 40]
#           first = 10 
#           second = 30
#           n ==2
#           temp = cost[n] + min (first, second)
#           first = second
#           second = temp;
#013        
#01234
#

def minSum(self, cost: List[int]):
    dp = [0 for i in range(len(cost))]
    
    
    return subminSum(cost, len(cost))#cost, 4

def subminSum(cost, sub_index):
    
    if sub_index<=1:
        # do something       
        return cost[sub_index]
    return min(subminSum(cost, sub_index-1)+cost[sub_index-1],subminSum(cost, sub_index-2)+cost[sub_index-2])

    return 

def minSum(self, cost: array):
    tmpSum = 0
    i == 0
    while (i < len(cost)):
        if (cost[i]<cost[i+1]):
            tmpSum = tmpSum + cost[i]
            i = i+1
        else:
            tmpSum = tmpSum + cost[i+1]
            i=i+2
    return tmpSum #10+30+10 =50 / 30+10 = 40

# Sep 8
## Willy [1629. Slowest Key](https://leetcode.com/problems/slowest-key/)

:::info
releaseTimes = [9,29,49,50], keysPressed = "cbcd"
output = "c"

c->9
b->20
c->20
d->1
time = 0
{'', -1} =>{'c', 9} =>{'b', 20}=>{'c', 20}...
ret(max_time) = 20
:::

  
    char slowestKey(vector<int>& releaseTimes, string keysPressed) {
        if (keysPressed.empty())
            return '';
        int time = 0;
        char cur_ch = keysPressed[0]; //c
        int cur_max_time = releaseTimes[0]; // 9
        
        for(int i = 1; i < keysPressed.size(); i++) {
            if (releaseTimes[i] - releaseTimes[i-1] > cur_max_time) { //20 > 9 
                cur_max_time = releaseTimes[i] - releaseTimes[i-1]; // 20
                cur_ch = keysPressed[i]; // b
            }
            else if (releaseTimes[i] - releaseTimes[i-1] == cur_max_time && keysPressed[i] > cur_ch) //20 , c>b
                cur_ch = keysPressed[i]; //c
        }
        return cur_ch;
    }
    
    

-------------------------
## Tristina [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)
:::info
1->8->5->4->null
=>
4->5->8->1->null

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

list = []
list.append()
list.pop()

#remain_list =[8 5 4 null]
node = head
while node !=None:
# do things
node = node.next
8.next = new_list
ListNode -> 4->5->8-> 1->null

:::
:::warning
名稱定義
:::

class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
#1->8->5->4->null

    node = head.next#8
    result = head#1
    result.next = None#? #1-> none
    while node:#8/ 5/4/none
        node.next = result#8->1->none/ 5->8->1->none/ 4->5->8->1->none
        
        result = node#8->1->none/5->8->1->none/4->5->8->1->none
        node = node.next#5 /4/none
    
    return result#4->5->8->1->none
        
'''
def reverseList(self, head):
    prev = None
    curr = head

    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    
    return prev
'''

# Sep 18
## Willy [917. Reverse Only Letters](https://leetcode.com/problems/reverse-only-letters/)

:::info
Input1 = "ab-cd"
Output1 = "dc-ba"

Input2 = "a-bC-dEf-ghIj"
Output2 = "j-Ih-gfE-dCba"

i
ab-cd
j
i
ab-cd
j
i
db-ca
j
i
dc-ba
j
end condition i >= j
:::
i
j-Ih-gfE-dCba
j

    bool isAlpha(char s) {
        if (s - 'a' >= 0 && s - 'a' <= 25) // a to z
            return true;
        if (s - 'A' >= 0 && s - 'A' <= 25) // A to Z 
            return true;
        retur false;
    }

    string reverseStr(String &str) {
        int i = 0, j = str.size() - 1;
    
        while(i < j) {
            while(str[i] == false) {
                i++;
            }
            while(str[j] == false) {
                j--;
            }
            swap(str[i], str[j]);
            i++;
            j--;
        }
        return str;
    }
    
    

-------------------------
## Tristina [53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)
:::info
nums = [-2,1,-3,4,-1,2,1,-5,4]
4,-1,2,1 => 6
nums = [5,4,-1,7,8]
23
[-2, 1, -3]
-2 + 1 = -1
-10^5 <= nums[i] <= 10^5

1. for loop
2. check add new item > tmpMax

sum = 1
tmpMax = -2+1

:::

'''
[5,4,-1,7,8]
[-2,1,-3,4,-1,2,1,-5,4]
tmpSum = 23
tmpMax = 15
[2, 3]

'''
 def maxSubArray(self, nums: List[int]) -> int:
    tmpSum = nums[0]
    tmpMax = nums[0]
    for n in nums[1:]:
    
        tmpSum = max(tmpSum + n, n) #23
        
        if (tmpMax < tmpSum)&& (n < tmpSum):
            tmpMax = tmpSum#23
            
        #check 
        if n > tmpSum:#
            tmpSum = n
            tmpMax = tmpSum

            
    
    return tmpMax#23
        

# Sep 18
## Willy [350. Intersection of Two Arrays II](https://leetcode.com/problems/intersection-of-two-arrays-ii/)

:::info
nums1 = [1,2,2,1], nums2 = [2,2]
-> [2,2]

nums1 = [4,9,5], nums2 = [9,4,9,8,4]
-> [4,9]

[4,5,9]

map[4] = 0
map[5] = 1
map[9] = 0
[9, 4]

:::

vector<int> common_num(vector<int> nums1, vector<int> nums2) {
    unordered_map<int, int> map;
    int m = nums1.size();
    int n = nums2.size();
    vector<int> common;
    for (int i = 0; i < m; i++)
        map[nums1[i]]++;

    for (int j = 0; j < n; j++) {
        if (map.find(nums2[j]) != map.end() && map[nums2[j]]> 0) {
            map[nums2[j]]--;
            common.push_back(nums2[j]);
        }
    }
    return common;
}
    

-------------------------
## Tristina [101. Symmetric Tree](https://leetcode.com/problems/symmetric-tree/)
:::info
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
1
/ \
2 2
/ \ / \
3 4 4 3
/ \ / \ / \ / \
None 4 3 4 43 4 None

root.left.val = root.right.val
root.left.left.val = root.right.right.val
root.left.right.val = root.right.left.val

root.left.right.left.val = root.right.left.right.val

cur1 = root.left
cur2 = root.right

if cur1.val == cur2.val:
if checkEqual(cur1, cur2):

if cur1.right.val == cur2.left.val:

def checkEqual(cur1, cur2):#input nodes

if cur1.val != cur2.val:
return False
elif cur1.val == None:
return True
else:
checkEqual(cur1.left, cur2.right)
checkEqual(cur1.right, cur2.left)
1
/ \
2 2
/ \ /\
n n n n

:::

class Solution:
 def isSymmetric(self, root: Optional[TreeNode]) -> bool:
       
    if root == None:
        return True
        
    def checkEqual(cur1, cur2):#input nodes (2,2) #(None,None)
        if cur1 == None or cur2 == None:
            return (cur1 == cur2)? True: False
        elif cur1.val != cur2.val:
            return False
        

        return checkEqual(cur1.left, cur2.right) && checkEqual(cur1.right, cur2.left)
            
    return checkEqual(root.left, root.right)#2,2

--------------------------
# Oct 1
## Willy [252. Meeting Rooms](https://leetcode.com/problems/meeting-rooms/)

:::info
Input: [[0,30],[5,10],[15,20]]
Output:->false

[[7,10],[2,4]]
->true

[[2,4],[7,10]]
[[2,4],[7,10],[15,20]]
[[2,4],[7,16],[15,20]]
:::

    bool meeting(vector<vector<int>> &list) {
            
        sort(list.begin(), list.end());
        
        for (int i = 0; i < list.size() - 1; i++) {
            if (list[i][1] > list[i+1][0])
                return false;
        }
        return true;
    }
    



-------------------------
## Tristina [203. Remove Linked List Elements](https://leetcode.com/problems/remove-linked-list-elements/)
:::info

head = [1,2,6,3,4,5,6] val = 6
[1,2,3,4,5]

[1,2,6,3,4,5,6]
curr
tmp

curr
tmp : 1,2,3
head: Optional[ListNode], val: int
:::

#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def removeTarget(self, head: Optional[ListNode, val:int]):

'''
prev -> [Null,1,2,6,3,4,5,6]
                     tmp
curr ->      [1,2,6,3,4,5,6]
                       curr
dummy             
'''

#prev = ListNode(0)
#prev.next = head

[]
tmp = None# ListNode(0)
#tmp = prev
curr = head

while curr:
    
    if (curr.val == val):
        if tmp:
            tmp.next = curr.next
        else:
            head = curr.next
    else:
        tmp = curr
   
    curr = curr.next
return head

--------------------------
# 10/10
## Willy []()

## Willy [11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)

:::info
**Example1**
height = [1,8,6,2,5,4,8,3,7]
Output: 49

**Example2**
height = [1,8]
Output: 1

**Example3**
height = [1,1,1]
| | |
Output: 2
[1,8,12,2,5,4,8,3,7]
i
j
max = 49
[1,1]
:::

int max_water(vector<int> w) {
    int i = 0;
    int j = w.size() - 1; // 1
    int max_w = 0;
    while(i < j) {
        max_w = max(max_w, min(w[i],w[j])*(j-i));
        if (w[i] > w[j])
            j--;
        else
            i++;
    }
    
    return max_w;
}
    

-------------------------
## Tristina [100. Same Tree](https://leetcode.com/problems/same-tree/)
:::info
1 1
/ \ / \
2 3 3 3

Output: false
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
:::

def TreesAreSame(self, p:Optional[TreeNode],q:Optional[TreeNode]):
    
    def isSame(node1, node2):

        if node1 == None and node2 == None:
            return True
        elif node1 == None or node2 == None:
            return False
        else:
            '''
            1. if the node1 == node2
            2. isSame(node1.left,node2.left)
            '''
            return node1.val == node2.val and isSame(node1.left,node2.left) and isSame(node1.right, node2.right)
            
        return isSame(p,q)#
        '''
        isSame(1,1)/F->isSame(2,3)/F->isSame(2.left,3.left)/T
                                ->isSame(2.right,3.right)/T

                ->isSame(3,3)/T->isSame(3.left,3.left)/T
                                ->isSame(3.right,3.right)/T

                False

        '''      
        

:::success
**建議：**
1. 面試時可以跟面試官互動，問他到目前都看得懂嗎等等。
2. 講解英文的流暢度
3. 最後寫好的時候可以說：I think it works.
:::

--------------------------
# 10/15
## Willy [1041. Robot Bounded In Circle](https://leetcode.com/problems/robot-bounded-in-circle/)

:::info
G
L
R
(0,0)
**Example1**
"GGLLGG","GGLLGG","GGLLGG","GGLLGG"
(0,0)->(0,2)->(0,0)
Output: True

**Example2**
"GG","GG","GG"
Output:False

"LLLG","LLLG","LLLG","LLLG"
"LGRGG"
R(+) L(-)
rotate = 0
if (retate == 0) return false;
else return true;

**Example3**
"GLGLGGLGL"
:::

    bool rebot(string m) {
        int rotate = 0;
        // if (m.empty())
        
        for (int i = 0; i < m.size(); i++) {
            if (m[i] == 'R')
                rotate++;
            else if (m[i] == 'L')
                rotate--;
        }
        return abs(rotate)%4 == 0? false: true;
    }

:::success

:::

-------------------------
## Tristina [160. Intersection of Two Linked Lists](https://leetcode.com/problems/intersection-of-two-linked-lists/)

:::info
listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]

head1: 4 1 \
^ 8 4 5
head2: 8 6 1 /
^

head1:8

head2:8

listA = [4,1,8,4,5]
^
listB = [5,6,1,8,4,5]
^
for (5)
[1, 2][3, 4, 5]
[3, 4, 5][1, 2]

[4,1,8,4,5][5,6,1,8,4,5]
^
[5,6,1,8,4,5][4,1,8,4,5]
^

4 2 3 5 - 6 7 4 9
5 3 1 2 /

4 2 4 5 6 1 2 7 8 9
5 3 4 5 6 3 4 7 8 9

:::

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

'''
[4,1,8,4,5]None[5,6,1,8,4,5]None
                            ^                 
[5,6,1,8,4,5]None[4,1,8,4,5]None
                            ^
nA = [4,1,8,4,5]
nB = [5,6,1,8,4,5]
'''
def getsameNode(self, headA: ListNode, headB: ListNode) -> ListNode:

    nA, nB = headA, headB
    
    while nA != nB:
        if nA is not None:
            nA = nA.next
        else:
            nA = headB
        
        if nB is not None:
            nB = nB.next
        else:
            nB = headA
            
    return nA

--------------------------
# 10/23
## Willy [1209. Remove All Adjacent Duplicates in String II](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/)

:::info
s = "abcd", k = 2
Output: "abcd"

s = "deeedbbcccbdaa", k = 3
Output:"aa"
s = "fdeeedbbcccbdaaff" k = 3

Output: "faa"
int pop;
count = 0
stack |
temp = fddbbbdaa
fddbbbdaa

:::

//s: aa
//st: 
//temp: aa
//count: 0
//pop: 0
string removesfcchar(string &s, int k) {
    do {
        int pop = 0;
        int count = 0;
        string temp;
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (st.empty()) {
                count++;
                st.push(s[i]);
                continue;
            }
            if (st.top()!=s[i]) {
                for (int j = 0; j < st.size(); j++) {
                    char c = st.top();
                    st.pop();
                    temp.push_back(c);
                }
                st.push(s[i]);
                count = 1;
            } else {
                count++;
                if (count == k) {
                    for (int j = 0; j < st.size(); j++)
                        st.pop();
                    count = 0;
                    pop++;
                } else
                    st.push(s[i]);
            }
            
        }
        if (!st.empty()) {
            for (int j = 0; j < st.size(); j++) {
                char c = st.top();
                st.pop();
                temp.push_back(c);
            }  
        }
        s = temp;
    } while(pop!=0);
    return s;
}

:::success


:::

-------------------------
## Tristina [876. Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)

:::info
1->2->3->4->5 return 3

S ^
F N ^

1->2->3->4->5->6 return 4

S ^
F ^
:::

def midNode(self, head: Linkedlist[ListNode]):
    slow  = fast = head

    
    while fast and fast.next :#5, null
    #fast.next odes, ex1
    #fast evens, ex2
    #fast = 5
        slow = slow.next

        fast = fast.next.next #5

    return slow

--------------------------
# 11/6
## Willy [977. Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/)

:::info
nums = [-4,-1,0,3,10]
ans = [0,1,9,16,100]

temp =
res = [0,1,9,16,100]
i
[-4,0,2,3,10,11,12]
j
search -> 2

ans = [1,4,9,16,100,121,144]
0,1,2,3
i
[-6,-5,-4,-1,0,3]

res: 0, 1, 9, 16, 25, 36
stack:
:::

vector<int> squresort(vector<int> &nums) {
   stack<int> temp;
   vector<int> res;
   
   while(i < nums.size()) {
        if (nums[i] < 0) {
           temp.push(sqrt(nums[i]));
           i++;
           continue;
        }
        if (!temp.empty() && temp.top() < sqrt(nums[i])) {
            int val = temp.top();
            res.push_back(val);
            temp.pop();
        } else {
            res.push_back(sqrt(nums[i]);
            i++;
        }
   }
   while(!temp.empty()) {
       int val = temp.top();
        res.push_back(val);
        temp.pop();
   }
   return res;
}

:::success

:::

-------------------------
## Tristina [1382. Balance a Binary Search Tree](https://leetcode.com/problems/balance-a-binary-search-tree/)

:::info
[1,null,2,null,3,null,4,null,null]
1
\
2
\
3
\
4

2
/ \
1 3
\
4
# 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

dfs(root)
values = [1,2,3,4]
id = 0,1,2,3

0+3//2 ->1 values[1] ->2

ans = TreeNode(values[1])
[1,2,3,4]
[1][2][3,4]
[3][4]

2
/ \
1 3
\
4

2
/ \
1 4
/
3

:::

def sol(self, root: TreeNode):
    #[1,null,2,null,3,null,4,null,null]
'''
values = [1,2,3,4]
buildTree(0,3)
lid = 0
rid = 3
mid = 1
ans = 2
ans.left = 1
lid = 0
rid = 0
mid = 0
ans.right = 3
lid = 2
rid = 3
mid = 2
ans.right = 3
lid = 2
rid = 3
mid = 2

   2
  / \
 1   3
      \
       4
       
'''
    values = []
    
    def dfs(root):
        # dfs
        if not root: return
        dfs(root.left)
        values.append(root.val)
        dfs(root.right)
        #return values
    
    dfs(root)
    
    def buildTree(lid,rid):
        if lid > rid: return None
        mid = (lid+rid)//2
        ans = TreeNode(values[mid])
        ans.left = buildTree(lid,mid-1)#2,1
        ans.right = buildTree(mid+1,rid)#3,3
        return ans
    
    return buildTree(0,len(values)-1)
        
    

--------------------------
# 11/19
## Willy [526. Beautiful Arrangement](https://leetcode.com/problems/beautiful-arrangement/)
[1144. Decrease Elements To Make Array Zigzag](https://leetcode.com/problems/decrease-elements-to-make-array-zigzag/)
:::info

n = 2 (1,2,3,....100)
output = 2 ([1,2],[2,1])[1,2,3,...100],[]

1~n
[1,2]

perm[i]%i == 0 || i % perm[i]
[1,2]
-perm[1] = 1 i = 1 -> 1/1
-perm[2] = 2 i=2 -> 2/2

[2,1]
perm[1] =2 2/1
i = 2 perm[2] = 1

fun (index, count, visit)

:::

void perm(int index, int &count, vector<bool> &visit, int n) {
    
    for (int i = 1; i < n+1; i++) {
        if (visit[i])
            continue;
        if (index == n && (i % index == 0 || index % i == 0))
            count++;
        else if (i % index == 0 || index % i == 0) {
            visit[i] = true;
            perm (index+1, count, visit, n);
            visit[i] = false;
        }
    }
}

int perm_count (int n) {
    int count = 0;
    vector<bool> visit(false, n);
    perm (1, count, visit, n);
    return count;
}

:::success

:::

-------------------------
## Tristina [103. Binary Tree Zigzag Level Order Traversal](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/)

:::info
root = [3,9,20,null,null,15,7]

3 -> L0
/ \
9 20 <- L1
/ \
15 7 ->L 2
Levels = [[L1],[L2],...]

if L%2 ==1: -> right to left
f(node.right,L)
f(node.left, L)
else: -> left to right
f(node.left, L)
f(node.right, L)

Output: [[3],[20,9],[15,7]]

:::

"""
root = [3,9,20,null,null,15,7]
Levels = [[3],[20,9],[15,7]]
addLevels(15,2)
root = [1,2,3,4,null,null,5]

    1  L0
   2 3 L1  <-
  4   5 L2 ->
Levels = [[1],[3,2],[4, 5,6]]

addLevels(5,2)

   [1,2,3]
"""
def getLevels(self, root: Tree[TreeNode])-> List[List[int]]:
    
    Levels = []
    
    
    def addLevel(node, L):
        
        if node:

            if len(Levels) == L:
                Levels.append([]) #new level

            Levels[L].append(node.val)

            # right to left
            if (L+1 )%2 == 1: #odd L1,L3,...
                addLevel(node.right,L+1)

                addLevel(node.left, L+1)
            else:#left to right
                addLevel(node.left, L+1)

                addLevel(node.right,L+1)
    
    if root:
        addLevel(root, 0)
        
    return Levels
    

--------------------------
# 12/4
## Willy [435. Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/)

:::info
https://leetcode.com/problems/non-overlapping-intervals/discuss/1181973/C%2B%2B-greedy

https://leetcode.com/problems/non-overlapping-intervals/discuss/1283600/C%2B%2B-or-Explained-or-Greedy-and-DP-or

https://leetcode.com/problems/non-overlapping-intervals/discuss/792726/C%2B%2B-Simple-O(NlogN)-solution-with-explanation

intervals = [[1,2],[1,3],[2,4],[3,4]]
-> [[1,2],[2,3],[3,4]]
output =1
[1,3]

intervals = [[1,2],[1,2],[1,2]]
-> [[1,2]]
output = 2

intervals = [[1,2],[2,3]]
output = 0

[1,2][1,2]
[1,2][1,3]
[2,4][3,4][4,5]
int count = 0;
sort(nums);
while(i < nums.size()-1)
if(nums[i][0] < nums[i-1][1] || nums[i][1] > nums[i+1][0])
count++;
return count;

[[1,2],[2,3],[3,4],[1,3]]
[[1,2],[1,3],[2,3],[3,4]]
count = 1
[[1,4],[1,5],[2,3],[3,4]]
[[2,3],[1,4],[3,4],[1,5]]
^ i
count = 1
[[1,4],[2,4],[3,4],[1,5]]
:::

bool static comp(pair<int, int> a, pair<int, int>b) {
        return a.second < b.second;
    }
    
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    int count = 0;
    int i = 1;
    int pre = i - 1;
    sort(intervals.begin(), intervals.end(), comp);
    while(i < intervals.size()-1) {
        if (intervals[i][0] < intervals[pre][1]) {
            count++;
        } else {
            pre = i;
        }
        i++;
    }
    return count;
}
|| 

:::
:::

-------------------------
## Tristina [75. Sort Colors](https://leetcode.com/problems/sort-colors/)

:::info
[2,0,2,1,1,0]
nums = [0,0,1,1,2,2]
nums = [0,0,2,1,1,2]
^ ^ ^
l
m
left side < m < right side
r

if l > m -> swap(l,m)
if m > r -> swap (m,r)

if l is 0 -> i++
if m is 1 -> m++
if r is 2 -> r--

if(nums[mid] == 0)
else if(nums[mid] == 1)
else #mid ==2

output = [0,0,1,1,2,2]
Space complexity: O(1)
def sortColors(self, nums: List[int]) -> None:
:::

def sortColors(self, nums: List[int]) -> None:
    """
    [0,1,2]
      l
      m 
         r
    """
    """
    [0,0,1,1,2,2]
         l
           m 
             r
    """
    l = m = 0
    r = len(nums)-1
    
    while m <= r:
        # check left side
        if nums[m] ==0:
            #compare with l
            
            nums[l], nums[m] = nums[m], nums[l]
            m += 1
            l += 1
            # check right side
        elif nums[m] == 2:
            nums[r], nums[m] = nums[m], nums[r]
            r -=1
         #else (when the m is 1, then only move on)
        else: # m ==1
            m +=1

--------------------------
# 12/19
## Willy [647. Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/)

:::info
s = "abc"
palindromic substrings
output:3

"a","b","c"

Input: s = "aaa"
Output: 6
Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

|
cbbc
^
^
4*4
4*3*2*1 = n!
:::

int fun(string &s){
    int count = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            count+= palindromic(s, i, j);
        }
    }
    return count;
}
int palindromic(string &s, int i, int j) {
    if (i >= j)
        return 1;
    return s[i] == s[j]? palindromic(s, i+1, j-1) : 0;
}

Manacher's algorithm

class Solution:
    #https://leetcode.com/problems/palindromic-substrings/discuss/392119/Solution-in-Python-3-(beats-~94)-(six-lines)-(With-Detaiiled-Explanation)
    def countSubstrings(self, s: str) -> int:
        L, r = len(s), 0
        for i in range(L):
            for a,b in [(i,i),(i,i+1)]:
                while a >= 0 and b < L and s[a] == s[b]: 
                    a -= 1; b += 1
                
                r += (b-a)//2
        
        return r

:::

:::

-------------------------
## Tristina [739. Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)

:::info
temperatures = [73,74,75,71,69,72,76,73]
0. 1, 2, 3,4, 5

cur
while the temp of the stack[-1] day < cur temp:
pop the day in the stack
and to check the distance ( cur day - prev day)

stack = [2,5]
cur = 5
prev = 3 # stack[-1].pop()
cur-prev
ans = [1,1,0,2,1,0,0,0]

Output: [1,1,4,2,1,1,0,0]

[73,73]

[0,0]
:::

#temperatures = [69,72,76,73]
'''


cur_day = 3
cur_tmp = 73
prev_day = 1
stack = [2]
ans = [1,1,0,0]
'''
def checkTemp(self, temperatures: List[int])-> List[int]:
    
    ans = [0]*len(temperatures)
    stack = []
    for cur_day, cur_tmp enumerate(temperatures):
        # while loop to compare the temperatures between prev day and cur day
        while stack and temperatrues[stack[-1]] < cur_tmp:
            prev_day = stack.pop()
            ans[prev_day] = cur_day-prev_day
        # append the cur day inside to the stack
        stack.append(cur_day)
    
    return ans
        

--------------------------
# Dec 24
## Willy [199. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)
:::info

1
2 3
5 4

root = [1,2,3,null,5,null,4]
Output: [1,3,4]

queue: store nodes of current level
cur_nums:record the number of current nodes
//queue: store nodes of chilren of current level
vector<Node*> res: output
q:
nums: 0
temp: 4
//when nums become zero
res: 1, 3, 4


:::

vector<Node*> rightnodes(Node* root) {
    queue<Node*> q;
    int cur_nums = 0;
    vector<Node*> res;
    
    q.push(root);
    cur_nums = 1;
    
    while (!q.empty()) {
        Node* temp;
        temp = q.front();
        if (temp->left) {
            q.push(temp->left);
        }
        if (temp->right) {
            q.push(temp->right);
        }
        q.pop();
        --cur_nums;
        if (cur_nums == 0) {
            res.push_back(temp);
            cur_nums = q.size();
        }
    }
    return res;
}

-------------------------
## Tristina [1020. Number of Enclaves](https://leetcode.com/problems/number-of-enclaves/)

:::info
{{0,0,0,0}}
{{0,0,0,0}}
{{0,0,0,0}}
{{0,0,0,0}}
enclave
3
Matrix
#dfs()
#go through the rest of the element
#change the Matrix[i][j] = 0

#check each element
for loop for the cols
for loop for rows:
#1.if the element is not enclave (4 edges)
#2.if the element ==1:
dfs()#check the island

#the rest would be ennclave island
for
for
#count the elements
:::

class solution:
    def enclave(self, Matrix: List[List[int]])->int:
        
        def dfs(Matrix,i, j):
            #edge case
            if  i <0 or j<0 or i> len(Matrix)-1 or j > len(Matrix[0])-1 or Matrix[i][j]==0:
                return
            #change the element
            #if Matrix[i][j]==1:
            Matrix[i][j]=0
                
            dfs(Matrix,i-1,j)
            dfs(Matrix,i+1,j)
            dfs(Matrix,i,j-1)
            dfs(Matrix,i,j+1)
            

        #check clave
        for i in range(len(Matrix)):
            for j in range(len(Matrix[0])):
                #check 4 edges and Matrix[i][j] ==1
                if i ==0 or j ==0 or i == len(Matrix)-1 or j == len(Matrix[0])-1:
                    #if Matrix[i][j] ==1:
                    dfs(Matrix, i, j)
                        
        #count numbers
        count = 0
        for i in range(len(Matrix)):
            for j in range(len(Matrix[0])):
                if Matrix[i][j]==1:
                    count +=1
        return count

--------------------------
# 1/9
## Willy [448. Find All Numbers Disappeared in an Array](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/)

:::info

nums = [-4,-3,-2,-7,8,2,-3,-1] #1~8

[5,6]
nums = [1,1]#1~2
[2]

size = nums.size()
arr[size]
arr[nums[i]-1]++;
res;
for (i = 0; i < size; i++)
if (arr[i] == 0)
res.push_back(i+1)
:::

vector<int> fun(vector<int> in) {
    int size = nums.size();
    vector<int> arr(size, 0); // state
    vector<int> res;
    
    for (int num: in)
        arr[num-1]++;
    for (int i = 0; i < size; i++)
        if (arr[i] == 0)
            res.push_back(i+1);
    return res;
}

:::

:::

-------------------------
## Tristina [653. Two Sum IV - Input is a BST](https://leetcode.com/problems/two-sum-iv-input-is-a-bst/)

:::info
root = [5,3,6,2,4,null,7], k = 9
5
/ \
3 6
/ \ \
2 4 7

true

class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:

hashmap ={}
k - a = b
b in hashmap
-> True

:::

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        hashmap = {}#{5:1,3:1,2:1}
        
        return findNext(root)#5

        
        def findNext(root):#6
            num = k - root.val#3
            if root is None:
                return False
            if num in hashmap:
                return True
            hashmap[root.val] = 1 # 2
            
            return findNext(root.left) or findNext(root.right)
            
            

--------------------------
# 1/9
## Willy [448. Find All Numbers Disappeared in an Array](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/)

:::info

nums = [-4,-3,-2,-7,8,2,-3,-1] #1~8

[5,6]
nums = [1,1]#1~2
[2]

size = nums.size()
arr[size]
arr[nums[i]-1]++;
res;
for (i = 0; i < size; i++)
if (arr[i] == 0)
res.push_back(i+1)
:::

vector<int> fun(vector<int> in) {
    int size = nums.size();
    vector<int> arr(size, 0); // state
    vector<int> res;
    
    for (int num: in)
        arr[num-1]++;
    for (int i = 0; i < size; i++)
        if (arr[i] == 0)
            res.push_back(i+1);
    return res;
}

--------------------------
# 1/13
## Willy [1877. Minimize Maximum Pair Sum in Array](https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/)

:::info

[2,5,6,8] -> 11
(2,8)(5,6)

sort-> two pointers from first and last -> global sum
sum = 11
nums = [3,5,2,3]

(3,3)(5,2) -> 7
6,7

(3,5)(2,3) -> 8

Output: 7

nums = [3,5,4,2,4,6]

(3,5)(4,4)(2,6) -> 8
(5,4)(4,3)(4,6) -> 9
Output: 8

[3,5,4,2,4,6]
[2,3,4,4,5,6]

:::

int fun(vector<int> nums) {
    if (nums.empty())
        return 0;
    sort(nums, nums.begin(), nums.end());
    int i = 0, j = nums.size()-1;
    int sum = 0;
    
    while ( i < j) {
        if (sum < nums[i] + nums[j])
            sum = nums[i] + nums[j];
        ++i;
        --j;
    }
    return sum;
}

:::

:::

-------------------------
## Tristina [1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold](https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/)

:::info
arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
^ ^ ^
[5,5,8] ->6 > 4

arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
:::

'''
[11,13,17,23,29,31,7,5,2,3]
                         i
 i = 2
 
 TOTAL = 15
 reuslt = 6
 tmp_sum = 5+2+3

'''

def findBigger(self, arr:List[int], k:int, threshold:int)-> int:
    
    TOTAL = k*threshold
    reuslt = 0
    tmp_sum = 0
    for i in range(len(arr)):
        tmp_sum += arr[i]
        if i >= k:#3
            tmp_sum -= arr[i-k]
        
        if i+1 >=k and tmp_sum >= TOTAL:
            reuslt +=1
    
    return result
            

--------------------------
# 1/22
## Willy [153. Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)

:::info
nums = [3,4,5,1,2]
output:1
[1,2,3,4,5] rotated 3 times

nums = [4,5,6,7,0,1,2]
output:0
[0,1,2,4,5,6,7]

[11,13,15,17]
output: 11
[11,13,15,17]

return nums min

time complexity < O(logn)
[4,5,6,7,0,1,2] mid > l and mid > r => l and r smaller? l = mid
[0,1,2,4,5,6,7] mid > l and mid < r => l and r smaller? r = mid
[5,6,7,0,1,2,4] mid < l and mid < r

[4,5,6,7,0,1,2] mid < l and mid > r // X

mid > mid + 1 -> return mid + 1 # 7
mid -1 > mid -> return mid #0
4 5 6 7 8 1 2
1 2 4 5 6 7 8
l < r => r = mid
l > r => l = mid
[11,13,15,17]
l = 11
r = 17
m = 13

:::

int fun(vector<int> nums) {
    int l = 0;
    int r = nums.size() - 1;
    int m = l + (r - l)/2;
    while (l < r) {
        if (nums[m] > nums[m+1])
            return nums[m+1];
        else if (nums[m-1] > nums[m])
            return nums[m];
        else if (nums[l] < nums[r])
            r = m-1;
        else
            l = m;
    }
    return nums[l];
}

-------------------------
## Tristina [621. Task Scheduler](https://leetcode.com/problems/task-scheduler/)

:::info
tasks = ["A","A","A","B","B","B"], n = 2
output=8
A -> B -> idle -> A -> B -> idle -> A -> B

["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

["A","A","A","B","B","D","D","C","C"]
A->B->D->A->B->D->A->
A->B->C->A->B->D->A->C->D = size() = 9
empty :0
empty + len(tasks)
(max_freq - 1) * (n+1) + 1

[2,2]

empty. = 4

["A","A","A","B","B","B"]
[3,3]
A -> B ->i ->A ->B ->i ->A -> B
2 * 3 = 6
if (task_freq == max_freq )
add A and B
(max_freq - 1) * (n+1) +

1. get the freq
2. sort freq
3. max_freq = freq.pop()
4. empty = (max_freq-1)*n
5. empty -
6. result = len(tasks)+empty

["A","A","A","B","B","D","D","C","C"]

map ={"A":3}
3
max_nums = 1
2*3+1

:::

def getMinTime(self, tasks:List[str],n: int)-> int:
    

    map = {}
    max_freq = 0
    max_nums = 0
    for t in tasks:
        
        map[t]+=1
        max_freq = max(max_freq, map[t])
    
    for v in map.values():
        if v ==max_freq:
            max_nums +=1

    
    return max(len(task),(max_freq - 1)*(n+1)+ max_nums)

--------------------------
# 2/12
## Willy [697. Degree of an Array](https://leetcode.com/problems/degree-of-an-array/)

:::info

nums = [1,2,2,3,1]

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

output = 2

nums = [1,2,2,3,1,4,2]<-degree =3
[2,2,3,1,4,2]
max = 2
max_degree = 1
res = [2,2]

output = 6
hashmap ->
max_degree = 0
res = [2,2,3,1,4,2]
:::

vector<int> fun (vector<int> arr) {
    int max_degree = 0;
    int max;
    unordered_map<int, int> map;
    vector<int> res;
    for (int num: arr) {
        map[num]++;
        if (map[num] > max_degree) {
            max_degree = map[num];
            max = num;
        }
    }
    
    for (int num: arr) {
        if (num != max && res.empty())
            continue;
        res.push_back(num);
        if (num == max)
            max_degree--;
    }
    return res;
}

:::

:::

-------------------------
## Tristina [1221. Split a String in Balanced Strings](https://leetcode.com/problems/split-a-string-in-balanced-strings/)

:::info
s = "RLRRLLRLRL"
^
RL RRLL RL RL
output = 4

count =0
output = 4

:::

def countRL(self, s:str)->int:
    count = 0
    output = 0
    for v in s:
        if v =="R":
            count +=1
        else:
            count -=1
        
        if count ==0:
            output +=1
            
    return output
        
            

--------------------------
# 2/20
## Willy [560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/)

:::info

nums = [-1,-1,1,1,1,1], k = 2
i j
[1,1,1,-1][1,1,1,-1][1,1,1,1,-1,-1][1,1][1,1]
output =2

nums = [1,2,3], k = 3
0 1 3 6

[1,2] [3]
output = 2

[1,2,3,2,1] k = 3
0 1 3 6 8 9
j
3-3 = 0
HashTable = {sums:count}
{0:1,1:1,3:1,6:1...}

HashTable[6]
Sum - preSum = k
prefixSum = sum -k
[1,-1,0]
1, 0, 0
k = 0

0:3
1:1

:::

int subarr(vector<int> nums, int k) {
    unordered_map<int, int> map;
    int res = 0;
    int sum = 0;
    map[0]++;
    
    for (int i = 0; i < nums.size(); i++) {
        sum+= nums[i];
        if (map[sum - k])
            res++;
        map[sum]++;
    }
    return res;
}

:::

:::

-------------------------
## Tristina [1029. Two City Scheduling](https://leetcode.com/problems/two-city-scheduling/)

:::info
costs = [[10,20],[30,200],[400,50],[30,20]] =>2n = 4 (2~100)
first person [10,20] => [Acost, Bcost]
first pick A => 10
2 => 30
3 =>50
4 => 20
cost = 110

p1 -> 10 20. -> -10
p2 -> 30 200 -> -170
p3 -> 400 50 -> 350
p4 -> 30 20 -> 10

the cost of picking the Acity

pickA = [-170, -10,10, 350]

:::

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        pickA_cost = []
        #costs sorted by picking A's difference
        costs.sorted(key = lambda x: x[0]-x[1])
        
        n = len(costs)//2
        res = 0
        
        for i in range(n):
            res += costs[i][0]+costs[i+n][1]
        
        return res
            
        

--------------------------
# 3/13
## Willy [974. Subarray Sums Divisible by K](https://leetcode.com/problems/subarray-sums-divisible-by-k/)

:::info

nums = [4,5,0,-2,-3,1],k =5
output = 7

[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

nums = [5], k = 9

output = 0
[4, 5, 0, -2,-3,1]
[4, 4, 4, 2, 4, 0]

res = 1 + 2 + 3 + 1
{"4":3}
{"2":1}
{"0":1}
count += dict['4']
dict['4']+=1

:::

int fun (vector<int> nums, int k) {
    unordered_map<int, int> record;
    int res = 0;
    int remain = 0;
    for (int num: nums) {
        remain = (remain + num) % k;
        if (remain % k == 0)
            res++;
        if (record.find(remain) != record.end()) {
            res += record[num];
            record[num]++;
        }
        else
            record[num] = 1;
    }
    
    return res;
}

:::

:::

-------------------------
## Tristina [82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

:::info
head =
[1,2,5]
head = [1,1,1,2,3]
[2,3]

1. sorted linkedlist
2. 0<len(linkedlist)<300

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

head = [1,2,3,3,3,4,4,5]
p c n
c
p.next = n
c = p.next #4

# go through each element set it as prev
# check if the cur and the next is the same
c = prev.next
next
while c.value == n.value:
change the next to the next one

else:
c = c.next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
:::

0 [1,2,3,3,4,4,5]
p
   c
           n
2-> 4 
c 
 

def removeDuplicates(self, head: LinkNode):
    
    # prev 
    newList = ListNode(0,head)
    
    prev = newList
    cur = prev.next
    
    #go through 
    while cur and cur.next:
        
#         cur = prev.next
#         next_node = cur.next
        
#         if cur.value != next_node.value:
#             prev = prev.next
#             break
        
#         #check if cur and next is Equal 
#         while cur.value == next_node.value:
#             next_node = next_node.next
        
#         prev.next = None
#         prev.next = next_node
#         #cur = prev.next
    
#         prev = prev.next
        if cur.value != cur.next.value:#cur.value != cur.next.value
             prev = prev.next
        else: 
            while cur and cur.next and cur.value == cur.next.value:
                cur = cur.next
        
            prev.next = cur.next

        cur = cur.next
    return newList.next

--------------------------
# 3/27
## Willy [18. 4Sum](https://leetcode.com/problems/4sum/)

:::info
nums = [2,7,11,15], target = 9
output = [0,1]
hashmap <int(number), int(index)>

2 -> [target - 2] if exist , push index to res
if not , [2] = 0
7 -> [2] exist, push 2's index and push current index

Input: nums = [1,0,-1,0,-2,2], target = 0, k = 4
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Input: nums = [2,2,2,2,2], target = 8, k = 4
Output: [[2,2,2,2]]

[-2, -1 0, 0, 1, 2]
def kSum(nums,target,k):
k ==2:
twoSum(nums,target)
for i in range(len(nums)):
for subset in kSum(nums[i+1:],target-nums[1],k-1):
res.append([nums[i]]+ subset)

vector<vector<int>> kSum(vector<int>& nums, int target, int start, int k) {

for (vector<int>& subset : kSum(nums, static_cast<long>(target) - nums[i], i + 1, k - 1)) {

#

}

:::

vector<int> twosum(vector<int> nums, int target) {
    vector<int> res;
    int i = 0; //index
    unordered_map<int, int> map;
    
    while(i < nums.size()) {
        if (map.find(target - nums[i])!=map.end()) {
            res.push_back(map[target - nums[i]]);
            res.push_back(i);
            break;
        } else
            map[nums[i]] = i;
        i++;
    }
    
    return res;
}

vector<int> ksum2(vector<int> nums, int target, int k, int index) {
    vector<int> res;
    for (int i = index; i < nums.size(); i++) {
        ksum
    }
    return res;
}

vector<vector<int>> ksum(vector<int> nums, int target, int k) {
    vector<vector<int>> res;
    vector<int> temp;
    sort(nums);
    for (int i = 0; i < nums.size(); i++) {
        temp = ksum2(nums, target, k , i);
        if (temp.size() == k)
            res.push_back(temp);
    }
    return res;
}

:::

:::
-------------------------
## Tristina [991. Broken Calculator](https://leetcode.com/problems/broken-calculator/)

:::info
*2 or -1
startValue -> target
2 -> *2 -> -1 -> 3 =>2
5 -> -1 -> *2 -> 8 =>2
1 <= x, y <= 10^9

startVale < target
x<y

(x+a)*2^n+b = y

5 6
5 4 3 6

// +
1. target //2

6//2
3< startValue# when we find the closest smaller value
-> count the distance (3-5)

2. target cannot divide by 2->
2-> 5
2 4 3 6 5
5+1
6//2
3+1
4//2
2

:::

5 -> -1 -> *2 -> 8 

5 -> 5
target = 3
startValue = 5
count = 2

 50 52
    26

 50 26 52 51

O(n/2)
    

def countStepToTarget(startValue:int, target:int)-> int:
    
    count =0
    
    while startValue != target:
        
        if target%2==0 and target > startValue: # target can divided by 2
            
            target = target//2
            
        else:
            target +=1
        
        count +=1
    return count

--------------------------
# 4/9
## Willy [1293. Shortest Path in a Grid with Obstacles Elimination](https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/)

:::info

[2115. Find All Possible Recipes from Given Supplies](https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/)
Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Output: ["bread"]

Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich"]

Input: grid = [ [0,0,0],
[1,1,0],
[0,0,0],
[0,1,1],
[0,0,0]], k = 1
Output: 6 (length)

visited = (position,len,k)
:::

    
    
int bfs(vector<vector<int>> grid, int k, int i, int j, int x_size, int y_size) {
    queue<vector<int>> record;
    vector<int> root;
    //record: x, y, count, k
    root.push_back(i);
    root.push_back(j);
    root.push_back(0);
    root.push_back(k);
    record.push_back(root);

    while (!record.empty()) {
        vector<int> cur = record.front();
        vector<int> next_right;
        vector<int> next_left;
        vector<int> next_up;
        vector<int> next_down;
        if (x_size - 1 == cur[0] && y_size - 1 == cur[1])
            break;
        if (cur[0] + 1 < x_size) {
            if (grid[cur[0]][cur[1]] == 1 && cur[3] > 0) {
                cur[3]--;
                next_right.push_back(cur[0] + 1);
                next_right.push_back(cur[1]);
                next_right.push_back(cur[2] + 1);
                next_right.push_back(cur[3]);
                record.push(next_right);
            } else (grid[cur[0]][cur[1]] == 0) {
                next_right.push_back(cur[0] + 1);
                next_right.push_back(cur[1]);
                next_right.push_back(cur[2] + 1);
                next_right.push_back(cur[3]);
                record.push(next_right);
            }
        }
        if (cur[0] - 1 >= 0) {
            if (grid[cur[0]][cur[1]] == 1 && cur[3] > 0) {
                cur[3]--;
                next_left.push_back(cur[0] - 1);
                next_left.push_back(cur[1]);
                next_left.push_back(cur[2] + 1);
                next_left.push_back(cur[3]);
                record.push(next_left);
            } else (grid[cur[0]][cur[1]] == 0) {
                next_left.push_back(cur[0] - 1);
                next_left.push_back(cur[1]);
                next_left.push_back(cur[2] + 1);
                next_left.push_back(cur[3]);
                record.push(next_left);
            }
        }
        if (cur[1] + 1 < y_size) {
            if (grid[cur[0]][cur[1]] == 1 && cur[3] > 0) {
                cur[3]--;
                next_down.push_back(cur[0]);
                next_down.push_back(cur[1] + 1);
                next_down.push_back(cur[2] + 1);
                next_down.push_back(cur[3]);
                record.push(next_down);
            } else (grid[cur[0]][cur[1]] == 0) {
                next_down.push_back(cur[0]);
                next_down.push_back(cur[1] + 1);
                next_down.push_back(cur[2] + 1);
                next_down.push_back(cur[3]);
                record.push(next_down);
            }
        }
        if (cur[1] - 1 >= 0) {
            if (grid[cur[0]][cur[1]] == 1 && cur[3] > 0) {
                cur[3]--;
                next_up.push_back(cur[0]);
                next_up.push_back(cur[1] - 1);
                next_up.push_back(cur[2] + 1);
                next_up.push_back(cur[3]);
                record.push(next_up);
            } else (grid[cur[0]][cur[1]] == 0) {
                next_up.push_back(cur[0]);
                next_up.push_back(cur[1] - 1);
                next_up.push_back(cur[2] + 1);
                next_up.push_back(cur[3]);
                record.push(next_up);
            }
        }
        record.pop();

    }
    return cur[2];
}
    
int findshortpath(vector<vector<int>> grid, int k) {
    int length = INT_MAX;
    
    
}

-------------------------
## Tristina [287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)
:::info
Floyd Cycle

size = 5 (n + 1)
1 ~ n
nums = [1,3,4,2,2]
^ ^

[1,3,4,2,2]
f
s

nums[0] : 1
nums[1] : 3
nums[3] : 2
nums[2] : 4
nums[4] : 2

1 -> 3 -> 2 -> 4
| <- \
[1,2,3,4,2]

Output: 2

O(n)/O(1)

for loop go through every num
if num not in set:
set.add(num)
else:
return num

:::

nums = [1,3,3,2,2]
num = 3
tmp_num = 4
def returnDuplicate(nums: List[int])-> int:
    
    #for i, num in enumerate(nums):
    N = len(nums)
    i = 0
    tmp_num = 0
    while i < len(N) or tmp_num != 0: tmp_num ==0 
        num = nums[i]   
        if tmp_num ==0:
        tmp_num = nums[num-1]
        if tmp_num == num and num-1 != i:
            return num
        else:
            nums[num-1] = num
    

--------------------------
# Template
## Willy []()

:::info

:::

:::

:::

-------------------------
## Tristina []()

:::info

:::