2021-01 LC Challenge Week 2
Created: 2021/01/09 Updated: 2021/01/23 16:36 JSTTable of Contents
- Day 0 - Find Root of N-Ary Tree
- Day 1 - Check If Two String Arrays are Equivalent
- Day 2 - Word Ladder
- Day 3 - Create Sorted Array through Instructions
- Day 4 = Merge Sorted Array
- Day 5 - Add Two Numbers
- Day 6 - Boats to Save People
- Day 7 - Minimun Operations to Reduce X to Zero
Day 0 - Find Root of N-Ary Tree
Solution 1 - HashMap
The description of this problem is bad which makes you feel you need to contruct the tree from given array of nodes, then return the root node.
However it is much simplier question. We also need to traverse all nodes to find nodes which node is not visited when traversing children
- Time: O(n) where n is node number
- Space: O(n) where n is node number
Solution 2 - Sum up
Since each node has unique value, we can sum all values up when visiting each node then minus value when traversing them in children. The the value remains will be the value of root node.
Then in the last loop of visiting all nodes, we can which node has the equal value.
- Time: O(n)
- Space: O(1)
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children if children is not None else []
"""
from collections import deque
class Solution:
def findRoot(self, tree: List['Node']) -> 'Node':
sumValue = 0
for node in tree:
if node:
sumValue += node.val
if node.children:
for child in node.children:
sumValue -= child.val
for node in tree:
if node and node.val == sumValue:
return node
return None
Day 1 - Check If Two String Arrays are Equivalent
Solution - Compare using index of word and index of characters
To avoid using extra space which needs to concatenate words , use two pointers, one for character and one for word.
- Time: O(N) where N is minimum of length of word1 and word2.
- Space: O(1) pointers only take constant space
class Solution:
def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
# Simple comparing each character
# index of word
wc1 = wc2 = 0
# index of character in single word
i = j = 0
while wc1 < len(word1) and wc2 < len(word2):
if i < len(word1[wc1]) and j < len(word2[wc2]):
if word1[wc1][i] != word2[wc2][j]:
return False
i += 1
j += 1
if i == len(word1[wc1]):
wc1 += 1
i = 0
if j == len(word2[wc2]):
wc2 += 1
j = 0
if wc1 == len(word1) and wc2 == len(word2):
return True
return False
Day 2 - Word Ladder
Solution 1 - HashMap and BFS
The key idea to form a hashMap which maps generic word to specific word. Then travese from beginWord by BFS (deque to track next to process words) using a set to track visited word. Using a hashMap instead of set to track both visited word and level count will help a lot.
- Time: O(N) where N is the word count since each word will be maximally visited once.
- Space: O(N) where N is word count.
Solution 2 - HashMap and Bidirectional BFS
Based on the first solution, we can use DFS in bidirection way, from beginWord and endWord. This will slightly improve time complexity.
- Time: O(N) where N is the word count since each word will be maximally visited once.
- Space: O(N) where N is word count.
from collections import defaultdict, deque
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
# x*x -> xxx
if endWord not in wordList:
return 0
dictionary = defaultdict(list)
for word in wordList:
for i in range(len(word)):
generic = word[:i] + "*" + word[i+1:]
dictionary[generic].append(word)
def visit(q, visited, visited_other):
(word, level) = q.popleft()
for i in range(len(word)):
generic = word[:i] + "*" + word[i+1:]
if generic in dictionary:
for nextWord in dictionary[generic]:
if nextWord not in visited:
if nextWord in visited_other:
return level + visited_other[nextWord]
visited[nextWord] = level + 1
q.append((nextWord, level + 1))
return None
# Bi-directional BFS
q1 = deque()
q1.append((beginWord, 1))
q2 = deque()
q2.append((endWord, 1))
visited1 = { beginWord: 1 }
visited2 = { endWord: 1 }
while len(q1) > 0 and len(q2) > 0:
ans1 = visit(q1, visited1, visited2)
if ans1: return ans1
ans2 = visit(q2, visited2, visited1)
if ans2: return ans2
return 0
Day 3 - Create Sorted Array through Instructions
Solution - Binary Indexed Tree
TODO
- Time: O()
- Space: O()
# Your code
Day 4 = Merge Sorted Array
Solution - bruteforce
The first bruteforce method comes to mind is to compare from left to right, once number in nums1 will be modified by number from nums2, we move every number after it in nums1 which take nearly n! at the worst case.
Solution - Compare from right
To avoid moving numbers in nums1, we can start comparison from right. Having two pointers to track last number in both arrays, and put the greater value in according place in nums1 until any of the arrays reaches head. Finally place all rest numbers to remaining places.
- Time: O(N) where N is the m + n
- Space: O(1) since we use
nums1
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1 = m - 1
p2 = n - 1
p = m + n - 1
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
while p2 >= 0:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
Day 5 - Add Two Numbers
Solution - Traverse by Predcedent node
Use a flag/number to track if previous compuation is greater than 10, then just visit all nodes. Predcedent node is helpful for starting visiation from both node and never losing the first node.
- Time: O(N) where N is node count of l1 and l2
- Space: O(N) where N is the node count of result
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
pred = ListNode(0)
head = pred
addOne = False
while l1 and l2:
cur = l1.val + l2.val
if addOne: cur += 1
if cur >= 10:
addOne = True
else:
addOne = False
newNode = ListNode(cur % 10)
head.next = newNode
head = head.next
l1 = l1.next
l2 = l2.next
def addRest(head, node, addOne):
while node:
cur = node.val
if addOne: cur += 1
if cur >= 10:
addOne = True
else:
addOne = False
newNode = ListNode(cur % 10)
head.next = newNode
head = head.next
node = node.next
return head, addOne
if l1:
head, addOne = addRest(head, l1, addOne)
if l2:
head, addOne = addRest(head, l2, addOne)
if addOne:
head.next = ListNode(1)
return pred.next
Day 6 - Boats to Save People
Solution - Greedy and Two Pointers
The keyword is each boat at most two people which informs us that considering sum of min and max is within limit or not, if so put them on single boat, otherwise, put put max one on single both.
- Time: O(Nlog(N)) where sorting is required
- Space: O(1) no extra space needed
# greedy + 2 pointers
people.sort()
i, j = 0, len(people) - 1
ans = 0
while i <= j:
ans += 1
if people[i] + people[j] <= limit:
i += 1
j -= 1
return ans
Day 7 - Minimun Operations to Reduce X to Zero
Solution 1 - Prefix sum + two pointers
Think it as the problem to find substring sum equals to total sum minus given X.
Precaclute prefix sum, then use right pointer to expand the window and left pointer to extract the window. Since two pointer will only move forward, the time complexity will be O(N). Minimum operations means to get longest substring.
- Time: O(N) where N is length of nums
- Space: O(N) where N is length of nums, for prefix sum.
# Your code
Solution 2 - Two pointers
We can have a sum of all numbers, then minus the value left just moved away from, plus the value right just moved in.
- Time: O(N) where N is length of nums
- Space: O(N) where N is length of nums, for prefix sum.
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
# Represent the variable for reaching X value
cur = sum(nums)
l = 0
res = float("inf")
for r in range(len(nums)):
# minus the value that current r moved
cur -= nums[r]
while cur < x and l <= r:
cur += nums[l]
l += 1
if cur == x:
res = min(res, len(nums) - r + l - 1)
return res if res != float("inf") else -1