## LeetCode 442 – Python 3 (Week 4 – 03)

Solution 1

```class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
res = []
for num in nums:
index = abs(num) - 1
if nums[index] > 0:
nums[index] = - nums[index]
else:
res.append(index+1)

return res

```

Time complexity is O(n). Space complexity is O(1).

## LeetCode 448 – Python 3 (Week 4 – 02)

Solution 1

```class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
for i in range(0, len(nums)):
index = abs(nums[i]) - 1
nums[index] = -abs(nums[index])

return [i + 1 for i in range(len(nums)) if nums[i] > 0]
```

Time complexity is O(n). Space complexity is O(1).

## *LeetCode 437 – Python 3 (Week 4 – 01)

Solution 1

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

class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
#go through reach node. count the paths when the start node is that node.

self.numOfPaths = 0

self.dfs(root, sum)

return self.numOfPaths

def dfs(self, node, sum):
if node is None:
return
self.count(node, sum)
self.dfs(node.left, sum)
self.dfs(node.right, sum)

def count(self, node, sum):
if node is None:
return
if node.val == sum:
self.numOfPaths += 1
self.count(node.left, sum-node.val)
self.count(node.right, sum-node.val)
```

Both time complexity and space complexity are O(n*n) to O(nlogn).

Solution 2

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

class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
self.result = 0
presum = {0:1}
currentsum = 0

self.dfs(root, sum, 0, presum)

return self.result

def dfs(self, root, sum, currentsum, presum):

if root is None:
return

currentsum += root.val
needpresum = currentsum - sum

self.result += presum.get(needpresum, 0)
presum[currentsum] = presum.get(currentsum, 0) + 1

self.dfs(root.left, sum, currentsum, presum)
self.dfs(root.right, sum, currentsum, presum)
# *********
presum[currentsum] -= 1
```

Both time complexity and space complexity are O(n).

## LeetCode 283 – Python 3 (Week 3 – 08)

Solution 1

```class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
zero = 0 #position of 0
for i in range(len(nums)):
#if the num is not 0, move the num to the position of last zero
if nums[i] != 0:
nums[zero] = nums[i]
zero += 1

for i in range(zero, len(nums)):
nums[i] = 0
```

Time complexity is O(n). Space complexity is O(1).

Solution 2

```class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums.sort(key=bool, reverse=True)
```

Time complexity is O(n log n). Space complexity is O(n).

Solution 3

```class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
zero = 0

#swap current first 0 and next non-zero elements
for i in range(len(nums)):
if nums[i] != 0:
nums[i], nums[zero] = 0, nums[i]
zero += 1
```

Time complexity is O(n). Space complexity is O(1).

## LeetCode 234 – Python 3 (Week 3 – 07)

Solution 1

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

class Solution:
def isPalindrome(self, head: ListNode) -> bool:

#if head == None: return False
#if[], output should be true

#fist-find the middle node, second-reverse half of the list, third-compare
pre = None
while fast and fast.next: #make sure fast is the last one or None.
fast = fast.next.next
slow = slow.next

#1-2-3-4, now slow is 3, fast is null, pre is 2
#1-2-3-4-5, slow is 3, fast is 5, pre is 2
if fast: slow = slow.next #slow is 4

#compare
while pre and slow:
if pre.val != slow.val:
return False
else:
pre = pre.next
slow = slow.next

return True
```

Time complexity is O(n). Space complexity is O(1).

## LeetCode 226 – Python 3 (Week 3 – 06)

Solution 1

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

class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:

#Recusive
if not root: return None
right = self.invertTree(root.left)
left = self.invertTree(root.right)
root.right = right
root.left = left
return root
```

Time complexity is O(n). Space complexity is O(n).

Solution 2

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

class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:

#Iterative
if not root: return None
current = root
stack = []
while stack or current:
if current:
stack.append(current)
current = current.left
else:
current = stack.pop()
current.right, current.left = current.left, current.right
current = current.left

return root
```

Time complexity is O(n). Space complexity is O(n).

## LeetCode 206 – Python 3 (Week 3 – 05)

Solution 1: Iterative

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

class Solution:
def reverseList(self, head: ListNode) -> ListNode:
#Iterative
dummy = ListNode(float('-inf'))

return dummy.next

```

Time complexity is O(n). Space complexity is O(1).

Solution 2: Recursive

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

class Solution:
def reverseList(self, head: ListNode) -> ListNode:
#Recursive

return left
```

Time complexity is O(n). Space complexity is O(n).

## LeetCode 155 – Python 3 (Week 3 – 04)

Solution 1

```class MinStack:

def __init__(self):
"""
"""
self.array = []

def push(self, x: int) -> None:
cur_min = self.getMin()
if cur_min == None or x < cur_min: cur_min = x #here we can not use if not cur_min. Because if cur_min is 0, it will be considered as not cur_min is true!
self.array.append((x, cur_min))

def pop(self) -> None:
self.array.pop()

def top(self) -> int:
if not self.array: return None
return self.array[-1]

def getMin(self) -> int:
if not self.array: return None
return self.array[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
```

Time complexity and space complexity are O(1).

Warning: Do not use ” if not x”, if “x” is a number!

## LeetCode 198 – Python 3 (Week 3 – 03)

Solution 1

```class Solution:
def rob(self, nums: List[int]) -> int:

# for house 0, we have to choose: rob or not. If we rob, the max total amount we can get is the max amount at point house -2 + amount in house 0. If not, the max total amount we can get is the max amount at point house -1.Thus, the largest amount is max( amount at house -2 + house 0, amount at house -1)

dp_last, dp_now = 0, 0
for num in nums:
dp_last, dp_now = dp_now, max(dp_last + num, dp_now)

return dp_now
```

Time complexity is O(n). Space complexity is O(1).

## LeetCode 169 – Python 3 (Week 3 – 02)

Solution 1:

```class Solution:
def majorityElement(self, nums: List[int]) -> int:
dic = {}

for num in nums:
if num in dic:
dic[num] += 1
else:
dic[num] = 1

for v,k in dic.items():
if k > len(nums)/2:
return v
```

Time complexity is O(n). Space complexity is O(n).

Solution 2

```class Solution:
def majorityElement(self, nums: List[int]) -> int:

#The number of majority element is more than n/2. Set the first number as the majority number. Count this number and not this number. When equal, delete this part. Go on...
index, cnt = 0, 1

for i in range(1,len(nums)):
if nums[i] == nums[index]:
cnt += 1
else:
cnt -= 1
if cnt == -1:
index = i
cnt = 1

return nums[index]

```

Time complexity is O(n). Space complexity is O(1).

Solution 3

```class Solution:
def majorityElement(self, nums):
nums.sort()
return nums[len(nums)//2]
```

Time complexity is O(nlgn). It is the time to sort array in Python. Space complexity is O(n). Timsort is used.