2021-01 LC Challenge Week 2

Table of Contents

Explore - LeetCode

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

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.

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

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.

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.

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:]

        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


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

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

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

# greedy + 2 pointers
        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.

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

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