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