# 2021-01 LC Challenge Week 1

### Table of Contents

Explore - LeetCode

## Day 0 - Palindrome Permutation

LC266

#### 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

LC1640

#### 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] = 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

LC1379

#### 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

LC526

#### 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

LC21

#### 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

LC82

#### 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

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
``````