# Path In Zigzag Labelled Binary Tree

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the `label` of a node in this tree, return the labels in the path from the root of the tree to the node with that `label`.

Example 1:

```Input: label = 14
Output: [1,3,4,14]
```

Example 2:

```Input: label = 26
Output: [1,2,6,10,26]```
```from math import log

class Solution:
def pathInZigZagTree(self, label: int) -> List[int]:
ans = [label]

def findParent(label):
level =  math.floor(math.log(label,2))
diff = math.ceil((label - 2**level + 1) / 2)
parent = 2**(level) - diff
return parent

while label != 1:
label = findParent(label)
ans.append(label)

return ans[::-1]```

# Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

```Given nums = [1,1,2],

Your function should return length = `2`, with the first two elements of `nums` being `1` and `2` respectively.

It doesn't matter what you leave beyond the returned length.```

Example 2:

```Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = `5`, with the first five elements of `nums` being modified to `0`, `1`, `2`, `3`, and `4` respectively.

It doesn't matter what values are set beyond the returned length.```
```class Solution:
def removeDuplicates(self, nums: List[int]):
if not nums:
return 0

newTail = 0

for i in range(1, len(nums)):
if nums[i] != nums[newTail]:
newTail += 1
nums[newTail] = nums[i]

return newTail + 1```

# Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

```Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]```
```class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
self.result = []

def perm(data, begin, end):
if begin == end:
self.result += [[item for item in data]]
else:
i = begin
for j in range(begin, end):
data[i], data[j] = data[j], data[i]
perm(data, begin + 1, end)
data[i], data[j] = data[j], data[i]

perm(nums, 0, len(nums))

return self.result```

# Permutation Sequence

The set `[1,2,3,...,n]` contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

1. `"123"`
2. `"132"`
3. `"213"`
4. `"231"`
5. `"312"`
6. `"321"`

Given n and k, return the kth permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

```Input: n = 3, k = 3
Output: "213"
```

Example 2:

```Input: n = 4, k = 9
Output: "2314"```
```class Solution:
def getPermutation(self, n: int, k: int) -> str:
res, nums = "", list(range(1, n + 1))

k -= 1

for n in range(n, 0, -1):
index, k = divmod(k, math.factorial(n-1))
res += str(nums.pop(index))

return res```

# Lowest Common Ancestor with N nodes

Similar with finding lowest common ancestor of two nodes, we can extend this function to N nodes.

The method buildTree in the solution is in order to building a tree instantly by given strings.

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

class Solution:
def buildTree(self, inorder, postorder):
if not inorder or not postorder:
return None

while postorder:
if postorder[-1] not in inorder:
postorder.pop()
else:
break

if len(postorder) == 1:
return TreeNode(postorder)

else:
node = TreeNode(postorder[-1])
in_index = inorder.index(postorder[-1])
node.left = self.buildTree(inorder[:in_index], postorder[:-1])
node.right = self.buildTree(inorder[in_index + 1:], postorder[:-1])
return node

def find(self, root, nodes):
if not root:
return None
else:
if root.val in nodes:
return root

left = self.find(root.left, nodes)
right = self.find(root.right, nodes)

if left and right:
return root

return right if not left else left

if __name__ == "__main__":
obj = Solution()
root = obj.buildTree([6, 5, 7, 2, 4, 3, 0, 1, 8], [6, 7, 4, 2, 5, 0, 8, 1, 3])
nodes = [0, 1, 8]
result = obj.find(root, nodes)
print(result.val)
```

# House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

`Input: [3,2,3,null,3,null,1]        3      / \    2   3      \   \         3   1 Output: 7  Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.`

Example 2:

`Input: [3,4,5,1,3,null,1]            3          / \        4   5      / \   \     1   3   1 Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.`
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def rob(self, root: TreeNode) -> int:
def superrob(node):
# returns tuple of size two (now, later)
# now: max money earned if input node is robbed
# later: max money earned if input node is not robbed

# base case
if not node: return (0, 0)

# get values
left, right = superrob(node.left), superrob(node.right)

# rob now
now = node.val + left + right

# rob later
later = max(left) + max(right)

return (now, later)

return max(superrob(root))```

# Next Permutation﻿

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

`1,2,3` → `1,3,2`
`3,2,1` → `1,2,3`
`1,1,5` → `1,5,1`

# Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

# Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!