# 2021-01 LC Challenge Week 2

Created: 2021/01/09 Updated: 2021/01/23 16:36 JST### Table 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
```