# 2021-01 LC Challenge Week 1

Created: 2021/01/04 Updated:### Table of Contents

- Day 0 - Palindrome Permutation
- Day 1 - Check array formation through concatenation
- Day 2 - Find a Corresponding Node of a Binary Tree in a Clone of That Tree
- Day 3 - Beautiful Arrangement
- Day 4 - Merge Two Sorted Lists
- Day 5 - Remove Duplicates from Sorted List II
- Day 6 - Kth Missing Positive Number
- Day 7 - Longest Substring Without Repeating Characters

## Day 0 - Palindrome Permutation

#### Brute force

We can calculate all permutation, during that check if any permutation is in form of palindrome, return true if only one matches. Otherwise return false.

- Time: O(n!) * O(n) where n is length of given string
- Space: O(1)

#### Solution: HashMap

Count the appearance number for each character of the string, record in a HashMap or dictionary in Python. Then loop all values and check `if odd count appears maximally once`

. If so return True, otherwise return False.

- Time: O(n) where n is length of given string.
- Space: O(n) where n is length of given string.

```
from collections import Counter
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
# count(key) == count(all words) / 2
# Palindrome: aa or aba -> 1, 2 or 2, 3
# Palindrome: aaaab -> 2, 2
counter = Counter(s)
countOdd = False
for k, v in counter.items():
if v % 2 == 1 and not countOdd:
countOdd = True
elif v % 2 == 1 and countOdd:
return False
return True
```

## Day 1 - Check array formation through concatenation

#### Solution: Brute force

Since we cannot reorder arr, we can check one by one between arr and pieces by searching the one from arr in pieces

- Time: O (n^2)
- Space: O(1)

#### Solution: HashMap

Use a hashMap to store start num to piece, then iterate each number from left arr.

- Time: O(n) where n is length of arr
- Space: O(n) where n is length of arr

```
class Solution:
def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
startToPieceMap = dict()
for piece in pieces:
startToPieceMap[piece[0]] = piece
i = 0
while i < len(arr):
if arr[i] not in startToPieceMap:
return False
piece = startToPieceMap[arr[i]]
for item in piece:
if arr[i] != item:
return False
i += 1
return True
```

## Day 2 - Find a Corresponding Node of a Binary Tree in a Clone of That Tree

#### Solution: BFS

Breath First Search all nodes

- Time: O(n) where n is node amount, since it needs to traverse mostly all nodes.
- Space: up to O(n) each level will need up to N/2 nodes for storing in FIFO queue.

```
from collections import deque
class Solution:
def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
q = deque()
q.append(cloned)
while len(q) > 0:
#
cur = q.popleft()
if cur.val == target.val:
return cur
if cur.left: q.append(cur.left)
if cur.right: q.append(cur.right)
```

## Day 3 - Beautiful Arrangement

#### Solution: DFS bracktracking + Fixed visited array

Check each permutation. Since given constraints the n is limited, we can use an array to mark if each i is visited/used or not. With backtracking we mark it unvisited after dfs for current i.

- Time: up to O(N!) and O(P) where p is count of qualified permutation.
- Space: O(1) since it s fixed size

```
class Solution:
def countArrangement(self, n: int) -> int:
self.res = 0
visited = [False for i in range(16)]
def dfs(index, visited):
if index == n + 1:
self.res += 1
return
for i in range(1, n + 1):
# print(visited)
if not visited[i] and (i % index == 0 or index % i == 0):
visited[i] = True
dfs(index + 1, visited)
# revert value after visit
visited[i] = False
dfs(1, visited)
return self.res
```

## Day 4 - Merge Two Sorted Lists

#### Solution: Iteration

Create a new node to be the one in the front, then iterate nodes from two linked list, if only add smaller to the next of new node and move to next. Finally append only non-null list if another list reaches tail.

- Time: O(m + n) where m and n are length of two linked list.
- Space: O(1)

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head = ListNode(0)
res = head
while l1 and l2:
if l1.val < l2.val:
res.next = l1
l1 = l1.next
else:
res.next = l2
l2 = l2.next
res = res.next
if l1:
res.next = l1
else:
res.next = l2
return head.next
```

## Day 5 - Remove Duplicates from Sorted List II

#### Solution: HashMap + Sentinel Node

By comparing current value with pre value, if not equal then check if previous value is of count once, then add to result linked list.

- Time: O(N) where N is length of linked list.
- Space: O(N) can be improved to O(1) by using fix size of array [-100, 100].

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head:
return None
res = ListNode(-1)
cur = res
curValue = -101
counted = dict()
counted[-101] = 1
while head:
if head.val != curValue:
if counted[curValue] == 1:
cur.next = ListNode(curValue)
cur = cur.next
curValue = head.val
counted[head.val] = 1
else:
counted[head.val] += 1
head = head.next
if counted[curValue] == 1:
cur.next = ListNode(curValue)
return res.next.next
```

#### Solution: Sentinel Node + Predecessor

Skip duplicates by comparing the current val with next node value. This way the code looks much simpler and clean.

- Time: O(N) where N is length of linked list.
- Space: O(1)

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
res = ListNode(0, head)
pre = res
while head:
# skip duplicates
if head.next and head.val == head.next.val:
while head.next and head.val == head.next.val:
head = head.next
pre.next = head.next
# otherwise move to pred
else:
pre = pre.next
head = head.next
return res.next
```

## Day 6 - Kth Missing Positive Number

#### Solution: binary search

To calculate the middle value of l and r, and compare with expected value, that gives us the missing number is on the left or right of the middle

- Time: O(log(n)) where n is length of the array
- Space: O(1)

```
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
# Binary search: log(n)
l = 0
r = len(arr) - 1
while l <= r:
m = l + (r-l) // 2 # this can avoid overflow
# arr[m] - (m + 1) means the missing numbers before arr[m]
# if it is greater than k, then the k's missing number is on the right side
if arr[m] - (m + 1) < k:
l = m + 1
else:
r = m - 1
return l + k
```

## Day 7 - Longest Substring Without Repeating Characters

#### Solution: Sliding Window

Right pointer to expand and left pointer to extract. Use a set to count what is visited between left and right. compare `r - l + 1`

with `len(set)`

to know whether there is duplicates or not. if there is duplicate `r - l + 1 > len(set)`

use left to extract, otherwise use right to expand.

- Time: O(n) since l and r will only move forwards
- Space: O(n)

```
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# sliding window
# right pointer to expand,
# when r - l + 1 == len(set)
# left one to extract
res = 0
l = 0
words = set()
for r in range(len(s)):
words.add(s[r])
while r - l + 1 > len(words):
words.remove(s[l])
# if l and r are same character, prevent delete it.
words.add(s[r])
l += 1
res = max(res, r - l + 1)
return res
```