[LeetCode] 179. Largest Number

Problem : https://leetcode.com/problems/largest-number/

Time Complexity : O ( N Log N )

from functools import cmp_to_key
from functools import reduce

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # a + b > b + a means (a+b) is larger than (b+a) in dictionary order
        dictionaryOrder = cmp_to_key(lambda a, b : 1 if int(a + b) > int(b + a) else -1)
        
        # sort nums in dictionary ascending order
        # concat all numbers from the largest to the smallest. 
        # return 0 if the first digit of final result is '0'
        result = reduce(lambda accumulate, n : accumulate + n, \
                        reversed(sorted(map(str, nums), key = dictionaryOrder)), \
                        '')
           
        return result if result[0] != '0' else '0'

[LeetCode] 174. Dungeon Game

Problem : https://leetcode.com/problems/dungeon-game/

Memorization Solution:

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        row = len(dungeon)
        col = len(dungeon[0])
        
        @lru_cache(maxsize = None)
        def helper(y, x):
            if y >= row or x >= col:
                return 2 ** 31 - 1
            
            if y == row -1 and x == col - 1:
                return max(1, 1 - dungeon[y][x])
            
            # only need to have 1 health point to survive 
            return max(1, min(helper(y,x+1), helper(y+1, x)) - dungeon[y][x])

        return helper(0, 0)

DP Solution:

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        row = len(dungeon)
        col = len(dungeon[0])
        
        max_int = 2 ** 31 - 1
        
        dp = [[max_int] * (col+1) for _ in range(row + 1)]
        
        dp[row][col-1] = 1
        dp[row-1][col] = 1
        
        for y in reversed(range(row)):
            for x in reversed(range(col)):
                dp[y][x] = max(1, min(dp[y+1][x], dp[y][x+1]) - dungeon[y][x])
        
        return dp[0][0]

[LeetCode] 173. Binary Search Tree Iterator

Problem : https://leetcode.com/problems/binary-search-tree-iterator/

Because in-order traverse BST can generate a ascending sequence.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: TreeNode):
        
        def inorder(node):
            if node:
                yield from inorder(node.right)
                yield node.val
                yield from inorder(node.left)
        
        self.nodes = list(inorder(root))

    def next(self) -> int:
        return self.nodes.pop()

    def hasNext(self) -> bool:
        return self.nodes


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

A stack based iterative solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: TreeNode):
        self.stack = [root] if root else []
        

    def next(self) -> int:
        node = self.stack[-1]
        
        while node.left:
            self.stack.append(node.left)
            tmp = node.left
            node.left = None
            node = tmp
        
        # pop the parent node
        self.stack.pop()
        
        if node.right:
            self.stack.append(node.right)
            node.right = None
        
        return node.val
        

    def hasNext(self) -> bool:
        return self.stack
        


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

Edited on 04/22/2021. Refactor the recursive and iterative solution.

[LeetCode] 172. Factorial Trailing Zeroes

Problem : https://leetcode.com/problems/factorial-trailing-zeroes/

number of trailing zero = number of 10 

Because 2 * 5 = 10 and number of 5 is less than the number of 2.

This problem equals how many 5 in the given number.

class Solution:
    def trailingZeroes(self, n: int) -> int:
        return n // 5 + self.trailingZeroes(n // 5) if n > 0 else 0

[LeetCode] 171. Excel Sheet Column Number

Problem : https://leetcode.com/problems/excel-sheet-column-number/

This problem equals to convert 27 based number to 10 based number.

from functools import reduce

class Solution:
    def titleToNumber(self, s: str) -> int:
        return reduce(lambda x, y: x * 26 + ord(y) - ord('A') + 1, s, 0)

[LeetCode] 169. Majority Element

Problem : https://leetcode.com/problems/majority-element/

Since majority element appears more than n/2 times, number[n/2] in the sorted array must be the majority element.

Time Complexity = O ( N * Log N )

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)
        return sorted(nums)[n // 2]

Use counter to filter out minority element.

Time Complexity = O ( N )

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        result = nums[0]
        count = 1
        
        for i in range(1, len(nums)):
            if nums[i] == result:
                count += 1
            else:
                count -= 1
            
            if count == 0:
                result = nums[i]
                count = 1
        
        return result

[LeetCode] 168. Excel Sheet Column Title

Problem : https://leetcode.com/problems/excel-sheet-column-title/

Time Complexity = O ( Log N )

class Solution:
    def convertToTitle(self, n: int) -> str:
        letters = [chr(i) for i in range(ord('A'),ord('Z')+1)]
        
        result = ""
        
        while n > 0:
            # use n - 1 because letters is zero-based array
            i = (n-1) % 26
            
            result += letters[i]
            n = (n-1) // 26
        
        return result[::-1]

[LeetCode] 167. Two Sum II - Input array is sorted

Problem : https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Time Complexity = O ( Log N )

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        
        while left < right:
            tmp = numbers[left] + numbers[right]
            
            if tmp < target:
                left += 1
            elif tmp > target:
                right -= 1
            else:
                return [left+1, right+1]

[LeetCode] 166. Fraction to Recurring Decimal

Problem : https://leetcode.com/problems/fraction-to-recurring-decimal/

Simulator long division process to calculate fraction result.

Because the same numerator always leads to the same fraction result. 

Use hash table to save numerator encountered to avoid repeating fractional part.

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        negative = (numerator < 0) ^ (denominator < 0)
        
        numerator = abs(numerator)
        denominator = abs(denominator)
        
        result = str(numerator // denominator)
        
        if numerator % denominator == 0:
            return "-" + result if negative and numerator != 0  else result
        
        numerator = numerator % denominator
        numerator *= 10
        
        visited = {}
        
        result += "."
        
        while numerator > 0:
            
            if numerator not in visited:
                visited[numerator] = len(result)
            else:
                prefix = result[:visited[numerator]] + '('
                appendix = result[visited[numerator]:] + ')'
                result = prefix + appendix
                break
            
            if numerator > denominator:
                result += str(numerator // denominator)
                numerator = numerator % denominator
            else:
                result += '0'
            
            numerator *= 10
        
        return "-" + result if negative else result

Edited on 03/04/2021. A simpler implementation.

[LeetCode] 165. Compare Version Numbers

Problem : https://leetcode.com/problems/compare-version-numbers/

Step 1, split version string by '.' to get integer on each level

Step 2, recursively compare integer on each level.  By default, integer on each level = 0

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        v1 = list(map(int, version1.split('.')))
        v2 = list(map(int, version2.split('.')))
        
        def compare(level):
            left = v1[level] if level < len(v1) else 0
            right = v2[level] if level < len(v2) else 0
            
            if left < right:
                return -1
            
            if left > right:
                return 1
            
            return 0 if level >= len(v1) and level >= len(v2) else compare(level+1)
                
        return compare(0)

[LeetCode] 164. Maximum Gap

Problem : https://leetcode.com/problems/maximum-gap/

The input array must be sorted first to find the maximum gap.

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0
        
        nums.sort()
        
        result = 0
        for i in range(len(nums) - 1):
            result = max(result, nums[i+1] - nums[i])
        
        return result

[LeetCode] 162. Find Peak Element

Problem :  https://leetcode.com/problems/find-peak-element/

Time Complexity : O ( Log N )

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        if len(nums) <= 1:
            return 0
        
        if nums[left] > nums[left+1]:
            return left
        
        if nums[right] > nums[right-1]:
            return right
        
        while left < right:
            mid = left + (right - left)
            
            if nums[mid-1] < nums[mid] > nums[mid+1]:
                return mid
            elif nums[mid-1] < nums[mid] < num[mid+1]:
                # peak exists on the end of the ascending sequence
                left = mid + 1
            else:
                # peak exists on the begining of descending sequence
                right = mid - 1
        
        return right

[LeetCode] 160. Intersection of Two Linked Lists

Problem : https://leetcode.com/problems/intersection-of-two-linked-lists/

Hash table based solution:

Time Complexity = O ( M + N )

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        
        memo = set()

        p1 = headA
        p2 = headB

        while p1:
            memo.add(p1)
            p1 = p1.next

        while p2:
            if p2 in memo:
                return p2

            p2 = p2.next

        return None

[LeetCode] 155. Min Stack

Problem : https://leetcode.com/problems/min-stack/

Should save current minimum value in stack for O(1) time complexity.

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, x: int) -> None:
        if len(self.stack) == 0:
            self.stack.append({'value': x, 'min': x})
        else:
            self.stack.append({'value': x, 'min': min(x, self.stack[-1]['min'])})
        
    def pop(self) -> None:
        del self.stack[-1]

    def top(self) -> int:
        return self.stack[-1]['value']
        

    def getMin(self) -> int:
        return self.stack[-1]['min']


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

[LeetCode] 154. Find Minimum in Rotated Sorted Array II

Problem : https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

Time Complexity = O( Log N )

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            elif nums[mid] == nums[right]:
                while right > mid and nums[mid] == nums[right]:
                    right -= 1
        
        return nums[right]

[LeetCode] 153. Find Minimum in Rotated Sorted Array

Problem : https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Binary search solution:

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        
        return nums[right]

Divide and conquer solution:

class Solution:
    def findMin(self, nums: List[int]) -> int:
        
        def helper(left, right):
            if nums[left] <= nums[right]:
                return nums[left]
            
            mid = left + (right - left) // 2
            
            return min(helper(left, mid), helper(mid+1, right))
        
        return helper(0, len(nums) - 1)

[LeetCode] 152. Maximum Product Subarray

Problem : https://leetcode.com/problems/maximum-product-subarray/

Brute Force ( Time Limit Exceeded )

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        result = nums[0]
        for i in range(len(nums)):
            tmp = nums[i]
            result = max(result, tmp)
            
            for j in range(i+1, len(nums)):
                tmp *= nums[j]
                result = max(result, tmp)
        
        return result

DP Solution:

class Solution {
    public int maxProduct(int[] nums) {
        int miSoFar = nums[0];
        int mxSoFar = nums[0];
        
        int result = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            int preMiSoFar = miSoFar;
    
            miSoFar = Math.min(mxSoFar * nums[i], Math.min(miSoFar * nums[i], nums[i]));
            mxSoFar = Math.max(preMiSoFar * nums[i], Math.max(mxSoFar * nums[i], nums[i]));
            
            result = Math.max(result, mxSoFar);
        }
        
        return result;
    }
}

Edited on 12/02/2021. Update the DP solution

[LeetCode] 151. Reverse Words in a String

Problem : https://leetcode.com/problems/reverse-words-in-a-string/

A lazy solution:

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(s.split()[::-1])

[LeetCode] 150. Evaluate Reverse Polish Notation

Problem : https://leetcode.com/problems/evaluate-reverse-polish-notation/

Use stack to cache operand and operator.

In python,  6 / -132 = -1.  To get the same result as C division operator, use int( 6 / -132 ) instead.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        
        operators = { '+' : lambda a, b: a + b,    \
                      '-' : lambda a, b: a - b,    \
                      '*' : lambda a, b: a * b,    \
                      '/' : lambda a, b: int(a/b) }
        
        for t in tokens:
            opt = operators.get(t)
            if opt:
                b = stack.pop()
                a = stack.pop()
                
                c = opt(a, b)
                stack.append(c)
            else:
                stack.append(int(t))
    
        return stack.pop()

Edited on 05/25/2021. Simplify condition checks.

[LeetCode] 149. Max Points on a Line

Problem : https://leetcode.com/problems/max-points-on-a-line/

A line is formed by 2 points. Points with same slops are on the same line.

Slop of  P1 and P2 =  ( P1. x - P2.x ) / (P1.y - P1. y).

Use (P1.x - P2.x),  (P1.y - P1.y) as key to save the counter of points with same slop.

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        @lru_cache(maxsize = None)
        def gcd(a, b):
            return a if b == 0 else gcd(b, a % b)
        
        result = 0

        for i in range(len(points)):
            # init duplicated = 1 for counting the point itself
            duplicated = 1
                
            # count of pointer with same slop
            slops = defaultdict(int)
            
            for j in range(i+1, len(points)):
                
                if points[i][0] == points[j][0] and points[i][1] == points[j][1]:
                    duplicated += 1
                else:
                    dx = points[j][0] - points[i][0]
                    dy = points[j][1] - points[i][1]
                    
                    d = gcd(dx, dy)
                    
                    slops[(dx/d, dy/d)] += 1
            
            result = max(result, duplicated)
            
            for _, count in slops.items():
                result = max(result, count + duplicated)
        
        return result

[LeetCode] 148. Sort List

Problem : https://leetcode.com/problems/sort-list/

Use merge sort to get O( n log n ) time complexity.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
              
        # divide into 2 parts
        fast, slow = head, head
        
        while fast and fast.next:
            fast = fast.next.next
            if fast:
                slow = slow.next
            
        tmp = slow.next
        slow.next = None

        left = self.sortList(head)
        right = self.sortList(tmp)

        return self.merge(left, right)
    
    def merge(self, left, right):
        dummy = ListNode(0)
        p = dummy
        
        while left and right:
            if left.val <= right.val:
                p.next = left
                p = p.next
                left = left.next
            else:
                p.next = right
                p = p.next
                right = right.next
        
        while left:
            p.next = left
            p = p.next
            left = left.next
        
        while right:
            p.next = right
            p = p.next
            right = right.next
        
        p.next = None
        
        return dummy.next

[LeetCode] 147. Insertion Sort List

Problem : https://leetcode.com/problems/insertion-sort-list/

Time Complexity = O ( N ** 2 ),  N = length of input list.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode();
        
        ListNode p = head;
        ListNode pre;
        ListNode cur;
        
        while (p != null) {
            pre = dummy;
            cur = dummy.next;
            
            while (cur != null && cur.val <= p.val) {
                pre = cur;
                cur = cur.next;
            }
            
            ListNode tmp = p.next;
            
            pre.next = p;
            p.next = cur;
            p = tmp;
        }
        
        return dummy.next;
    }
}

Edited on 12/14/2021. Replace with Java implementation.

[LeetCode] 146. LRU Cache

Problem : https://leetcode.com/problems/lru-cache/

Use doubly linked list to save order of inserted value node.

Most recently used node is on the tail of the doubly linked list.

Least recently used node is no the head of the doubly linked list.

Use dictionary to save the added value and its related linked list node.

Time complexity  = O ( 1 )

class Node:
    def __init__(self, key):
        self.pre = None
        self.next = None
        self.key = key

class LRUCache:
    def __init__(self, capacity: int):
        self.memo = {}
        self.queue = Node(-1)
        self.tail = self.queue
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key in self.memo:
            val, node = self.memo[key]
            
            self._remove(node)
            self._append(node)

            return val
        
        return -1
        
    def put(self, key: int, value: int) -> None:
        if key in self.memo:
            _, node = self.memo[key]
         
            self.memo[key] = (value, node)
            self._remove(node)
            self._append(node)
        elif len(self.memo) < self.capacity:
            node = Node(key)
            self.memo[key] = (value, node)
            self._append(node)
        else:
            removed = self._popleft()
            del self.memo[removed.key]
            
            node = Node(key)
            self.memo[key] = (value, node)
            self._append(node)
    
    def _remove(self, node):
        if node == self.tail:
            self.tail = node.pre
        
        pre_node = node.pre
        next_node = node.next
        
        pre_node.next = next_node
        if next_node:
            next_node.pre = pre_node
            
    def _append(self, node):
        self.tail.next = node
        node.pre = self.tail
        node.next = None
        
        self.tail = node
    
    def _popleft(self):
        node = self.queue.next
        if node:
            self.queue.next = node.next
            if node.next:
                node.next.pre = self.queue
            
            if self.tail == node:
                self.tail = node.pre
        
        return node


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

[LeetCode] 145. Binary Tree Postorder Traversal

Problem : https://leetcode.com/problems/binary-tree-postorder-traversal/

Recursive solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        
        def postorder(node):
            if node:
                yield from postorder(node.left)
                yield from postorder(node.right)
                yield node.val
        
        return list(postorder(root))

Iterative solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        stack = [root] if root else []
        
        while stack:
            node = stack[-1]
            
            if not node.left and not node.right:
                result.append(node.val)
                stack.pop()
            else:
                if node.right:
                    stack.append(node.right)
                    node.right = None

                if node.left:
                    stack.append(node.left)
                    node.left = None

        return result

Edited on 04/20/2021. Add the recursive approach.

Edited on 04/20/2021. Update the stack based iterative approach.

[LeetCode] 144. Binary Tree Preorder Traversal

Problem : https://leetcode.com/problems/binary-tree-preorder-traversal/

Recursive solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def preorder(node):
            if node:
                yield node.val
                yield from preorder(node.left)
                yield from preorder(node.right)

        return list(preorder(root))

Iterative solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        stack = [root] if root else []
        
        while stack:
            node = stack.pop()
            
            result.append(node.val)
            
            for child in filter(None, [node.right, node.left]):
                stack.append(child)
        
        return result

Edited on 04/20/2021. Update iterative solution. Same approach can apply to N-array tree too.

Edited on 04/20/2021. Update recursive solution. Use 'yield' and 'yield from'.

[LeetCode] 143. Reorder List

Problem : https://leetcode.com/problems/reorder-list/

Construct the needed list by doing preorder and postorder traversal at the same time.

Time Complexity = O ( N )

Space Complexity =  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 reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        
        self.dummy = ListNode()
        self.p = self.dummy
        
        self.preorder = head
        self.seen = set()
        
        def postorder(node):
            if node:
                postorder(node.next)
                
                # add node by preorder traversal
                if self.preorder not in self.seen:
                    self.seen.add(self.preorder)
                    
                    self.p.next = self.preorder
                    self.preorder = self.preorder.next

                    self.p = self.p.next
                
                # add node by postorder traversal
                if node not in self.seen:
                    self.seen.add(node)
                    
                    self.p.next = node
                    self.p = self.p.next
        
        postorder(head)
        
		# end the list
        self.p.next = None

A stack based solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head: return
        
        stack = []
        
        p = head
        total = 0
        
        while p:
            stack.append(p)
            p = p.next
            total += 1
        
        total = total // 2
        
        p = head
        while total > 0:
            tmp = p.next
            p.next = stack.pop()
            total -= 1
            
            p = p.next
            p.next = tmp
            p = p.next
            
        
        p.next = None

An iterative solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        ListNode p1 = head;  // slow
        ListNode p2 = head;  // fast
        
        // find the middle node
        while (p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        
        ListNode mid = p1.next;
        p1.next = null;
        
        // return directly if the second half list is empty
        if (mid == null) {
            return;
        }
        
        // reverse the second half list
        ListNode pre = null;
        ListNode cur = mid;
        
        while (cur.next != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        cur.next = pre;
        
        // reorder the list
        p1 = head;
        p2 = cur;
        
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        
        while (p1 != null || p2 != null) {
            
            if (p1 != null) {
                p.next = p1;
                p1 = p1.next;
                p = p.next;
            }
            
            if (p2 != null) {
                p.next = p2;
                p2 = p2.next;
                p = p.next;
            }
        }
    }
}

Edited on 12/21/2021. Add the iterative solution.

[LeetCode] 142. Linked List Cycle II

Problem : https://leetcode.com/problems/linked-list-cycle-ii/

Hash table based solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        memo = set()
        
        while head:
            if head in memo:
                return head
            
            memo.add(head)
            head = head.next
            
        return head

Fast and slow pointer solution:

Space complexity = O ( 1 )

Firstly, pointer P1 moves 2 times faster than P2. The linked list has cycle if P1 meets P2

Assume P1 and P2 meet at node P. Because P1 moves 2 times faster P2, A + B + C + B = 2 * (A + B)

So A = C.

Secondly, move pointer P1 back to the head of linked list. Then move P1 and P2 with same speed. P1 and P2 must meet again at node Q which is the node where the cycle starts.

      Q       P

--A---|---B---|
      |       |
      |       |
      |       |
      |---C---|

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
     
        p1 = p2 = head
        
        while p1 and p1.next and p2:
            p1 = p1.next.next
            p2 = p2.next
            
            if p1 == p2:
                # find the cycle
                p1 = head
                
                while p1 != p2:
                    p1 = p1.next
                    p2 = p2.next
                
                return p1
        
        
        return None

[LeetCode] 141. Linked List Cycle

Problem : https://leetcode.com/problems/linked-list-cycle/

Hash set based solution:

Time Complexity = O( N )

Space Complexity = O( N )

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        p = head
        memo = set()
        
        while p:
            if p in memo:
                return True
            else:
                memo.add(p)
                p = p.next
      

        return False

Fast and slow pointer solution:

Iterate the list with 'fast' and 'slow' pointers. If 'fast' pointer encounter 'slow' pointer, it means there is a cycle in the linked list.

Time Complexity = O ( N )

Space Complexity = O ( 1 )

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        fast, slow = head, head
        
        while fast and fast.next:
            if fast.next == slow:
                return True
            
            # 'fast' moves forward 2 steps
            fast = fast.next.next
            
            # 'slow' moves forward 1 step
            slow = slow.next
        
        return False

[LeetCode] 140. Word Break II

Problem : https://leetcode.com/problems/word-break-ii/

Use memorization approach to cache the result of,  starting from position "start", whether it is possible to break string into words in dictionary.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordDictSet = set(wordDict)
        result = []
        
        @lru_cache(maxsize = None)
        def backtracking(start):
            if start == len(s):
                return [[]]
            
            result = []
            for i in range(start, len(s)):
                tmp = s[start:i+1]
                if tmp in wordDictSet:
                    partials = backtracking(i+1)
                    for p in partials:
                        result.append([tmp] + p)
                    
            return result
        
        result = backtracking(0)
        
        return map(lambda x : " ".join(x), result)

[LeetCode] 139. Word Break

Problem : https://leetcode.com/problems/word-break/

Iterate the input string from left to right. Find word in dictionary. If found, break the input string into 2 parts, check if the 2nd part is also constructed by the words in dictionary.

Time Complexity = O ( N )

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not wordDict: return False
        
        wordSet = set(wordDict)
        maxLen = max([len(w) for w in wordDict])
        
        @lru_cache(maxsize=None)
        def dfs(start):
            if start >= len(s): 
                return True
            
            for i in range(start, min(start+maxLen, len(s))):
                if s[start:i+1] in wordSet and dfs(i+1):
                    return True
                    
            return False
        
        return dfs(0)

BFS solution:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not wordDict: return False
        wordSet = set(wordDict)
        maxLen = max([len(w) for w in wordDict])
        
        queue = deque([0])
        visited = set([0])
        
        while queue:
            start = queue.popleft()
            
            for i in range(start, min(start+maxLen, len(s))):
                if s[start:i+1] in wordSet:
                    if i + 1 == len(s):
                        return True

                    if i + 1 not in visited:
                        visited.add(i+1)
                        queue.append(i+1)
        
        return False

The bottom-up solution:

class Solution {

    public boolean wordBreak(String s, List wordDict) {
        HashSet<String> words = new HashSet();
        int wordLen = 0;
            
        for (int i = 0; i < wordDict.size(); i++) {
            words.add(wordDict.get(i));
            wordLen = Math.max(wordLen, wordDict.get(i).length());
        }
        
        int N = s.length();
        boolean[] dp = new boolean[N];
        
        for (int i = N-1; i >= 0; i--) {
            for (int j = i; i - j + 1 <= wordLen && j >= 0; j--) {
                
                if (words.contains(s.substring(j, i+1)) && (i + 1 == N || dp[i+1]) ) {
                    dp[j] = true;
                }
            }
        }
        
        return dp[0];

    }
}

Edited on 11/26/2021. Add the bottom-up solution.

[LeetCode] 138. Copy List with Random Pointer

Problem : https://leetcode.com/problems/copy-list-with-random-pointer/

Use dictionary to map the original node to its copy.

Recursive solution:

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        copies = {}
        
        def copy(node):
            if not node:
                return None
            
            copied = None
            if node in copies:
                return copies[node]
           
            copied = Node(node.val)
            copies[node] = copied
                
            copied.next = copy(node.next)
            copied.random = copy(node.random)
            
            return copied
        
        return copy(head)

Iterative solution:

Step1, create copy of each node and save the mapping relationship from each node to its copies.

Step2,  re-link each node's random pointer

"""
# Definition for a Node.
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        
        copies = dict()
        
        dummy = Node(0)
        
        p1 = dummy
        p2 = head
        
        while p2:
            p1.next = Node(p2.val)
            copies[p2] = p1.next
            
            p1 = p1.next
            p2 = p2.next
            
        
        p1 = dummy.next
        p2 = head
        while p1:
            if p2.random:
                p1.random = copies[p2.random]
                
            p1 = p1.next
            p2 = p2.next
            
        
        return dummy.next

[LeetCode] 137. Single Number II

Problem : https://leetcode.com/problems/single-number-ii/

Hash based solution:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        for n, count in Counter(nums).items():
            if count == 1:
                return n

O(1) space complexity solution:

import ctypes

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        
        # calculate sum of bit on each position
        for shift in range(32):
            sum_of_bit = 0
            
            for n in nums:
                mask = 1 << shift
                
                if n & mask != 0:
                    sum_of_bit += 1
            
            # sum_of_bit = 0, if there is no bit from the unique number
            # on this position
            sum_of_bit = sum_of_bit % 3
            
            result = result | sum_of_bit << shift
        
        # convert to integer 
        return ctypes.c_int(result).value

[LeetCode] 136. Single Number

Problem : https://leetcode.com/problems/single-number/

Because A xor A xor B = B. The code xor all numbers together to find the unique number.

from operator import xor

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(xor, nums)

[LeetCode] 135. Candy

Problem : https://leetcode.com/problems/candy/

Step 1, initially give every child 1 candy

Step 2, iterate from left to right. If child on right side has higher rating than child on left side,  child on right side be given1 more candy than child on left.

Step 3, iterate from right to left. If child on left side has higher rating than child on right side and child on left has less candy, child on left side be given 1 more candy than child on right.

class Solution:
    def candy(self, ratings: List[int]) -> int:
        
        candies = [1] * len(ratings)
        

        for i in range(len(ratings) - 1):
            if ratings[i+1] > ratings[i]:
                candies[i+1] = candies[i] + 1
        
        for i in reversed(range(1, len(ratings))):
            if ratings[i-1] > ratings[i]:
                candies[i-1] = max(candies[i-1], candies[i] + 1)
        
        return sum(candies)

[LeetCode] 134. Gas Station

Problem : https://leetcode.com/problems/gas-station/

DFS Solution ( Time Limit Exceeded ) 

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        
        def dfs(start, current, remain):
            if remain < 0:
                return False
            
            if start == current:
                return True
            
            return dfs(start, (current + 1) % len(gas), remain + gas[current] - cost[current])
        
        for i in range(len(gas)):
            if dfs(i, (i + 1) % len(gas), gas[i] - cost[i]):
                return i
        
        return -1

The DFS based solution will time out. However it reveals :

1. To finish a circle, the total gained gas must larger than total used gas

2. At each position, remained gas = last remained gas + gained gas - used gas. 

To reach to the next position, remained gas must larger than 0

If remained gas < 0, it means from the start position to current position, none of them can be used as start point. Because the initial remained gas of start position = 0

Greedy Solution

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # to finish a circle, gained gas must larger or equal to used gas
        total = 0
        
        # at each pos, remained gas = last remained gas + gained gas - used gas
        # if remained gas < 0, it means from start pos to current pos,
        # none of them can be used as start point.
        # because the initial remained gas of the start position = 0
        remain = 0
        
        start = 0
        
        for i in range(len(gas)):
            
            total += gas[i] - cost[i]
            remain += gas[i] - cost[i]
            
            if remain < 0:
                start = i + 1
                remain = 0
        
        
        return start if total >= 0 else -1

[LeetCode] 133. Clone Graph

Problem : https://leetcode.com/problems/clone-graph/

Use DFS approach to copy the graph. Because node's value is the same as its index. Node value can be used as key to locate the copied node.

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        copies = {}
        
        def copy(node):
            if not node:
                return None
            
            if node.val in copies:
                return copies[node.val]
            
            copied = Node(node.val)
            copies[node.val] = copied
            
            for n in node.neighbors:
                copied.neighbors.append(copy(n))
            
            return copied
        
        return copy(node)

[LeetCode] 132. Palindrome Partitioning II

Problem : https://leetcode.com/problems/palindrome-partitioning-ii/

This problem includes 2 sub-problems.

Let isPalindrome[i][j] = True if s[i:j+1] is a palindrome string.

The transformation formula is

isPalindrome[i][j] = True,  when:

1)  s[i] == s[j]  and j - i <= 2     # i.e. "aa" or "aba"

2)  s[i] == s[j]  and isPalindrome[i+1][j-1] == True.   # i.e.  "a ****  a"

Let minCut[i] = min cut needed for s[0:i+1]

For any s[0:i+1], it can be split into 2 parts:  s[0:j] and s[j:i+1]

if s[j : j + 1] is a palindrome,  then minCut[i] = min( minCut[i], minCut[j-1] + 1 )

if s[0: j + 1] is already a palindrome, minCut[i] = 0

class Solution:
    def minCut(self, s: str) -> int:
        if not s:
            return 0
        
        # isPalindrome[i][j] = True if s[i:j+1] is palindrome string
        isPalindrome = [[False] * len(s) for _ in range(len(s))]
        
        for j in range(len(s)):
            for i in range(j+1):
                if s[i] == s[j] and (j - i <= 2 or isPalindrome[i+1][j-1] == True):
                    isPalindrome[i][j] = True
        
        
        # minCut[i] = min cut of s[0:i+1]
        minCut = [i for i in range(len(s))]
        
        for i in range(len(s)):
            for j in range(i+1):
                if isPalindrome[j][i]:
                    if j == 0:
                        # s[0:i+1] is already a palindrome
                        # no need to cut
                        minCut[i] = 0
                        break
                    
                    minCut[i] = min(minCut[i], minCut[j-1] + 1)
    
        return minCut[-1]

The top-down memorization + backtracking solution:

class Solution:
    def minCut(self, s: str) -> int:
        
        @cache
        def isPalindrome(left, right):
            if left >= right:
                return True
            
            if right - left == 1:
                return True
                
            if s[left] == s[right-1] and isPalindrome(left+1, right-1):
                return True
            
            return False
        
        @cache
        def helper(left, right):
            if isPalindrome(left, right):
                # s[left:right] is already a palindrome. no need to cut.
                return 0
            
            result = right - left - 1
            
            for mid in range(left+1, right):
                if isPalindrome(left, mid):
                    # s[left:mid] is palindrome, we can try to cut it at 'mid' and calculate the least cut of rest of string
                    result = min(result, 1 + helper(mid, right))
            
            return result
        
        return helper(0, len(s))

Edited on 08/07/2021. Add the top-down memorization + backtracking solution.

[LeetCode] 131. Palindrome Partitioning

Problem : https://leetcode.com/problems/palindrome-partitioning/

Memorization Solution:

Step 1, find the first palindrome and put it to current partial result.

Step 2, repeat step1 to find palindrome in the rest string and append to partial result.

Stop repeating step 1 when rest string is empty.

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        
        @lru_cache(maxsize = None)
        def isPalindrome(start, end):
            while start < end:
                if s[start] != s[end]:
                    return False
                start += 1
                end -= 1
            
            return True
        
        def helper(start, partial):
            if start == len(s):
                result.append(partial)
                return
            
            for i in range(start, len(s)):
                if isPalindrome(start, i):
                    helper(i+1, partial + [s[start:i+1]])
                   
        helper(0, [])
        
        return result

DP + DFS solution:

class Solution {
    int N;
    boolean[][] palindrome;
    Map<Integer, List<List<String>>> memo = new HashMap<>();
    
    public List<List<String>> partition(String s) {
        N = s.length();
        palindrome = new boolean[N][N];
        
        for (int left = N-1; left >= 0; left--) {
            for (int right = N-1; right >= left; right--) {
                palindrome[left][right] = s.charAt(left) == s.charAt(right) && (right - left <= 1 || palindrome[left+1][right-1]);
            }
        }
        
        return helper(s, 0);
    }
    
    List<List<String>> helper(String s, int start) {
        if (memo.containsKey(start)) {
            return memo.get(start);
        }
        
        List<List<String>> result = new ArrayList<>();
        
        if (start >= N) {
            List<String> tmp = new ArrayList<>();
            result.add(tmp);
           
            return result;
        }
        
        for (int i = start; i < N; i++) {
            if (palindrome[start][i]) {
                for (List<String> suffix : helper(s, i+1)) {
                    List<String> tmp = new ArrayList<>();
                    tmp.add(s.substring(start, i+1));
                    tmp.addAll(suffix);
                    result.add(tmp);
                }
            }
        }
        
        memo.put(start, result);
        
        return result;
    }
}

DP solution:

Time complexity = O( N ** 2 )

class Solution {
    public List<List<String>> partition(String s) {
        int N = s.length();
        boolean[][] palindrome = new boolean[N][N];
        
        // memo[i] = palindrome partitions of s[i:]
        List<List<List<String>>> memo = new ArrayList<>(N+1);
        
        for (int i = 0; i < N; i++) {
            memo.add(new ArrayList<List<String>>());
        }
        
        // Add an empty partition list for position 'N'
        // memo[N] = [[]]
        memo.add(Arrays.asList(Collections.emptyList()));
        
        for (int left = N-1; left >= 0; left--) {
            for (int right = N-1; right >= left; right--) {
                palindrome[left][right] = s.charAt(left) == s.charAt(right) && (right - left <= 1 || palindrome[left+1][right-1]);
                
                if (palindrome[left][right]) {
                    // s[left:right+1] is a palindrome
                    // use it to expand the palindrome partitions of s[right+1:]
                    for (List<String> suffix : memo.get(right+1)) {
                        List<String> tmp = new ArrayList<>();
                        tmp.add(s.substring(left, right+1));
                        tmp.addAll(suffix);
                        memo.get(left).add(tmp);
                    }
                }
            }
        }
        
        // return palindrome partitions of s[0:]
        return memo.get(0);
    }
}

Edited on 04/13/2021. Add DP solution.

Edited on 01/04/2022. Refactor the DP + DFS solution.

Edited on 01/04/2022. Refactor the DP solution.

[LeetCode] 130. Surrounded Regions

Problem : https://leetcode.com/problems/surrounded-regions/

Use DFS approach to traverse from 4 edges of the given board.  Replace every visited  'O' with '#'.

Iterate each rows to replace every 'O' with 'X' and every '#' with 'O'

Time Complexity = O ( M * N ),   M = total rows of board,  N = total columns of board.

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        if not board:
            return
        
        row = len(board)
        column = len(board[0])
        
        def dfs(y, x):
            if board[y][x] == 'X' or board[y][x] == '#':
                return
            
            board[y][x] = '#'
            
            for dy in (-1, 1):
                if 0 <= y + dy < row:
                    dfs(y + dy, x)
          
            for dx in (-1, 1):
                if 0 <= x + dx < column:
                    dfs(y, x + dx)
        
        for i in range(row):
            for j in (0, column - 1):
                dfs(i, j)
        
        for i in (0, row -1):
            for j in range(column):
                dfs(i, j)
                
        
        for i in range(row):
            for j in range(column):
                if board[i][j] == '#':
                    board[i][j] = 'O'
                else:
                    board[i][j] = 'X'

[LeetCode] 129. Sum Root to Leaf Numbers

Problem : https://leetcode.com/problems/sum-root-to-leaf-numbers/

Use DFS approach to travel from root to every leafs.

A rescurisve approach:

Time Complexity = O ( N )

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    int dfs(TreeNode node, int tmp) {
        tmp = tmp  * 10 + node.val;
        if (node.left == null && node.right == null) {
            return tmp;
        }

        int result = 0; 
        result += (node.left != null) ? dfs(node.left, tmp) : 0;
        result += (node.right != null) ? dfs(node.right, tmp) : 0;
        return result;
    }
}

An iterative approach:

Time Complexity = O ( N )

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        result = 0
        stack = [(0, root)]
        
        while stack:
            num, node = stack.pop()
            num =  num * 10 + node.val
            
            if not node.left and not node.right:
                result += num
            else:
                if node.right:
                    stack.append((num, node.right))
                if node.left:
                    stack.append((num, node.left))
        
        return result

Edited on 03/13/2023. Replace the recursive solution with a Java based solution.

Edited on 04/24/2021. Refactor the recursive solution.

Edited on 04/24/2021. Add the iterative solution.

[LeetCode] 128. Longest Consecutive Sequence

Problem : https://leetcode.com/problems/longest-consecutive-sequence/

Hash table based solution:

Store the input numbers in Set. Then lookup for consecutive sequence if current number does not have preceding number.

Time Complexity = O ( N )

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        memo = set(nums)
        
        result = 0
        
        for n in nums:
            if n - 1 not in memo:
                tmp = 1
            
                while n + 1 in memo:
                    tmp += 1
                    n += 1
            
                result = max(result, tmp)
        
        return result

Union-Find based solution:

Put the contiguous numbers in one group. Then find the maximum number of items in one group.

class UnionFind:
    def __init__(self, nums):
        self.memo = {}
        for n in nums:
            self.memo[n] = n
    
    def union(self, x, y):
        parent = y
        while parent != self.memo[parent]:
            tmp = self.memo[parent]
            self.memo[parent] = self.memo[x]
            parent = tmp
            
        self.memo[y] = self.memo[x]
    
    def find(self, x):
        if x not in self.memo:
            return None
        
        parent = self.memo[x]
        
        while self.memo[parent] != parent:
            parent = self.memo[parent]
    
        while self.memo[x] != parent:
            tmp = self.memo[x]
            self.memo[x] = parent
            x = tmp
            
        return parent

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        uf = UnionFind(nums)
        
        for n in nums:
            if uf.find(n-1) != None:
                uf.union(n-1, n)
            
            if uf.find(n+1) != None:
                uf.union(n, n+1)
        
        maxLength  = defaultdict(int)
        
        # count number of items in each group
        for k in uf.memo.keys():
            p = uf.find(k)
            maxLength[p] += 1
        
        return max(maxLength.values()) if maxLength.values() else 0

[LeetCode] 127. Word Ladder

Problem : https://leetcode.com/problems/word-ladder/

Consider every word in wordList is a node of a graph. Use BFS to find the shortest path from begin word to end word.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        INT_MAX = 2 ** 31 - 1
        N = len(beginWord)
        
        wordDict = {word: INT_MAX for word in wordList}
        intermediates = defaultdict(list)
        
        if endWord not in wordDict: return 0
        
        for word in wordList:
            for i in range(N):
                wordMask = word[:i] + '*' + word[i+1:]
                intermediates[wordMask].append(word)
        
        queue = deque([beginWord])
        step = 1
        
        while queue:
            for _ in range(len(queue)):
                word = queue.popleft()
                
                for i in range(N):
                    wordMask = word[:i] + '*' + word[i+1:]

                    for newWord in intermediates[wordMask]:
                        if newWord == endWord:
                            return step + 1
                        
                        if newWord == word or wordDict[newWord] < step + 1:
                            continue
                        
                        wordDict[newWord] = step + 1
                        queue.append(newWord)

            step += 1
        
        return 0

Bidirectional BFS

Time complexity = O ( N * W * N + N * W * N ) = O ( W * N ** 2), N = length of each word, W = total number of word.

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        INT_MAX = 2 ** 31 - 1
        N = len(beginWord)
        
        wordDict = {word: INT_MAX for word in wordList}
        intermediates = defaultdict(list)
        
        if endWord not in wordDict: return 0
        
        for word in wordList:
            for i in range(N):
                wordMask = word[:i] + '*' + word[i+1:]
                intermediates[wordMask].append(word)
        
        queue = set([beginWord])
        opposite = set([endWord])
        
        step = 1
        
        while queue:
            tmp = []
            
            for word in queue:
                for i in range(N):
                    wordMask = word[:i] + '*' + word[i+1:]

                    for newWord in intermediates[wordMask]:
                        if newWord in opposite:
                            return step + 1
                        
                        if newWord == word or wordDict[newWord] < step + 1:
                            # word has been visited
                            continue
                        
                        wordDict[newWord] = step + 1
                        tmp.append(newWord)
                        
            queue = set(tmp) if len(tmp) < len(opposite) else opposite
            opposite = opposite if len(tmp) < len(opposite) else set(tmp)
            
            step += 1
        
        return 0

[LeetCode] 126. Word Ladder II

Problem : https://leetcode.com/problems/word-ladder-ii/

Consider every word in the wordList is a node of a graph. 

On each node, we may replace the letters of the word to find the next words.

The problem equals find the shortest routines from the begin word to the end word in this graph.

The solution includes two steps.  Firstly, use BFS approach to find the shortest routines from begin word to end word. Meanwhile, save the parent of each visited word. Word A is parent of word B if A can transform to B by replacing a letter.  Secondly, reconstruct routines from end word back to begin word by using the saved parent info of words on shortest routines.

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        # impossible to transform if endWord is not in wordList.
        if endWord not in wordList: return []
        
        # construct word mask map
        wordMap = defaultdict(list)
        
        for word in wordList:
            for i in range(len(word)):
                mask = word[:i] + "#" + word[i+1:]
                wordMap[mask].append(word) 
        
        # save the previous word was used to transform to current word
        preWord = defaultdict(list)
        
        # save the minimum step to transform to current word
        visited = defaultdict(lambda : 2 ** 31 - 1)
        visited[beginWord] = 0
        
        # use bfs to find all possible transformation paths
        step = 1
        queue = deque([beginWord])
        
        while queue:
            found = False
            
            for _ in range(len(queue)):
                word = queue.popleft()

                if word == endWord:
                    found = True

                for i in range(len(word)):
                    mask = word[:i] + "#" + word[i+1:]
                    for nxtWord in wordMap[mask]:
                        if nxtWord == word:
                            # skip the current word
                            continue

                        if visited[nxtWord] < step:
                            # already find the shortest path to nxtWord
                            continue
                        
                        if visited[nxtWord] != step:
                            # find the shortest path to nxtWord
                            visited[nxtWord] = step
                            # add nxtWord to queue if this is the first time we reach to it
                            queue.append(nxtWord)
                        
                        # save the previous word of nxtWord
                        preWord[nxtWord].append(word)
            
            step += 1
            if found:
                break
            
        # there is no way to reach to endWord
        if not preWord[endWord]:
            return []
        
        # use dfs to construct the transformation path
        result = []
        stack = []
        stack.append((endWord, [endWord]))
        
        while stack:
            word, tmp = stack.pop()
            
            if word == beginWord:
                result.append(tmp[::-1])
            else:
                for pre in preWord[word]:
                    stack.append((pre, tmp + [pre]))
        
        return result

Edited on 06/19/2021. Optimize performance.

Edited on 07/24/2021. Optimize performance.

[LeetCode] 125. Valid Palindrome

Problem : https://leetcode.com/problems/valid-palindrome/

Use two pointers to compare letters from head and tail. And ignore none-alpha-num letter.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        
        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
                
            while i < j and not s[j].isalnum():
                j -= 1
                
            if i < j and s[i].lower() != s[j].lower():
                break
            
            i += 1
            j -= 1
       
        return i >= j

[LeetCode] 124. Binary Tree Maximum Path Sum

Problem : https://leetcode.com/problems/binary-tree-maximum-path-sum/

On each node,  its path sum = Max( node,  node + left_path, node  + right_path, node + left_path + right_path)

Use postorder traversal to find the maximum path sum

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.result = -1000
        
        def postOrder(node):
            
            if node.left and node.right:
                left = postOrder(node.left)
                right = postOrder(node.right)
                
                self.result = max(self.result, node.val + left + right, node.val + left, node.val + right, node.val)
                
                return max(node.val + left, node.val + right, node.val)
            
            if node.left:
                left = postOrder(node.left)
                
                self.result = max(self.result, node.val + left, node.val)
                
                return max(node.val + left, node.val)
            
            if node.right:
                right = postOrder(node.right)
                
                self.result = max(self.result, node.val + right, node.val)
                return  max(node.val + right, node.val)
            
            self.result = max(self.result, node.val)
            return node.val
        
        if root:
            postOrder(root)
        
        
        return self.result

[LeetCode] 123. Best Time to Buy and Sell Stock III

Problem : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

Consider splitting the input array into 2 parts,  prices[:i] and prices[i:]. 

Let left[i] be the maximum profit can be made by ending on day i.

Let right[i] be the maximum profit can be made by starting on day i

Then the maximum profit can be made by 2 transactions = Max( left[i-1] + right[i] )

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        N = len(prices)
        
        left = [0] * N
        mi = prices[0]
        
        for i in range(1, N):
            left[i] = max(left[i-1], prices[i] - mi)
            mi = min(mi, prices[i])
        
        right = [0] * N
        mx = prices[N-1]
        
        for i in reversed(range(N-1)):
            right[i] = max(right[i+1], mx - prices[i])
            mx = max(mx, prices[i])
        
        result =0
        
        for i in range(N):
            if i == 0:
                result = max(result, right[i])
            elif i == N-1:
                result = max(result, left[i])
            else:
                result = max(result, left[i-1] + right[i])
     
        return result

Edited on 10/15/2021. Fix the logic error in previous code.