Posted on Edited on

Cmake settings

Discuss the setting in cmake only.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
find_package(PythonLibs 3.6)
find_package(PythonInterp 3.6)
include_directories(${PYTHON_INCLUDE_DIRS}) 


...

set(PYBIND11_DIR ${CMAKE_CURRENT_SOURCE_DIR}/external/pybind11)
add_subdirectory(${PYBIND11_DIR}/ pybind11)


...

target_link_libraries(example_embed pybind11::embed)
# use link lib pybind11::embed to embed a python interpreter in you c++ code.

# if want to generate wrapper
pybind11_add_module(example_wrapper MODULE main.cpp)
target_link_libraries(example_wrapper PRIVATE pybind11::module)
set_target_properties(example_wrapper PROPERTIES PREFIX "${PYTHON_MODULE_PREFIX}"
SUFFIX "${PYTHON_MODULE_EXTENSION}")
#

Read more »

Posted on Edited on

Max-flow/Min-cut theorem

Posted on Edited on

How to write a formula parser

Shunting Yard is a place where people reassemble and reorder the cargos of trains and the shunting-yard algorithm describes a similar process when dealing with liner text (usually mathematical input) which contains operators, arguments, and brackets. It is the fundamental algorithm of calculators, and it can be further generalized to operator precedence parsing.

Read more »

Posted on Edited on

Global settings

Assuming the structure of the project xxx is like below

1
2
3
4
5
6
7
8
9
10
11
12
13
xxx/-
     |
	src/
	    |
		A.h
		A.cpp
	external/-
		|
		tinyexpr/
		json/
	cmake/-


1
2
3
4
5
6
cmake_minimum_required(VERSION 3.x)
# set min cmake version
project(xxxx) 
# set ${PROJECT_NAME} as xxx
set(CMAKE_MODULE_PATH ${CMAKE_MODULE_PATH} ${CMAKE_CURRENT_SOURCE_DIR}/cmakes)
# add ${CMAKE_CURRENT_SOURCE_DIR}/cmakes to cmake search path
Read more »

Posted on Edited on

Arrays

Constriant subsets

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        mapval2idx = {}
        for i, num in enumerate(nums):
            if target - num not in mapval2idx:
                mapval2idx[num] = i
            else:
                return [mapval2idx[target-num], i]
        return [-1,-1]

O(n) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut mapval2idx = HashMap::new();
        for (i, num) in nums.iter().enumerate(){
            match mapval2idx.get(&(target - num)) {
                Some(&idx) => {return vec![idx, i as i32];}
                _ => {mapval2idx.insert(num, i as i32);}
            }
        }
        vec![-1,-1]

    }
}

3. Largest Substring withthout Repeating

Given a string, find the length of the longest substring without repeating characters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 1
        charpool = {}
        maxlen = 0
        while right < len(s)+1:
            addchar = s[right-1]
            if addchar not in charpool or charpool[addchar]==0:
                charpool[addchar]= 1;
                maxlen = max(maxlen, right - left)
                right += 1
            else:
                left+=1
                charpool[s[left-1]] -= 1
        return maxlen

    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        charpool = {}
        maxlen = 0
        for right, char in enumerate(s):
            # right = i + 1
            if (char in charpool) and (charpool[char] >= left):
                maxlen = max(maxlen, right -left)
                left = charpool[char] + 1
            charpool[char]= i # store the lastes appearance
        maxlen = max(maxlen, len(s) -left)
        return maxlen
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
use std::collections::HashMap;
use std::cmp;
impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let mut hash = HashMap::with_capacity(s.len());
        let mut max = 0;
        let mut left = 0;
        for (right, item) in s.chars().enumerate() {
            if let Some(j) = hash.get(&item) {
                //checks that current symbol is in the current window.
                if *j >= left {
                    max = std::cmp::max(max, right - left);
                    //move window
                    left = *j + 1;
                }
            }
            hash.insert(item, right);
        }
        max = std::cmp::max(max, s.len() -left);
        max as i32
    }
}

15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:

        def twoSumII(nums:List[int], idx:int, res:List[List[int]]):
            left = idx+1
            right = len(nums)-1
            target = -nums[idx]
            while left < right:
                sum2 = nums[left]+ nums[right]
                if(sum2 > target or ( right <len(nums)-1 and nums[right]==nums[right+1])):
                    right -= 1
                elif( sum2 < target or( left > idx + 1 and nums[left]== nums[left-1])):
                    left += 1
                elif (sum2== target):
                    res.append([-target,nums[left],nums[right]])
                    right -=1
                    left += 1

        nums.sort()
        res = []
        for idx, val in enumerate(nums):
            if(val > 0):
                return res
            elif (idx >0 and nums[idx] == nums[idx -1]):
                continue
            else:
                twoSumII(nums, idx, res)
        return res

93. Restore IP Address

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

A valid IP address consists of exactly four integers (each integer is between 0 and 255) separated by single points.

Example:

Input: “25525511135”
Output: [“255.255.11.135”, “255.255.111.35”]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def subRestore(start:int, depth:int)->List[str]:
            if(depth>3) or start>=len(s):
                return []
            if((4-depth)*3 < len(s)-start):
                # early truncation
                return []
            if(depth==3):
                # exclude substrings that starts with several 0s
                if int(s[start:])<256 and str(int(s[start:])) == s[start:]:
                    return [s[start:]]
                else:

                    return []
            res = []
            for h in range(start+1, start+4):
                if(int(s[start:h])<256 and str(int(s[start:h])) == s[start:h]):
                    tails = subRestore(h,depth+1)
                    for tail in tails:
                        res.append(s[start:h]+"."+tail)
            return res
        return subRestore(0,0)

209 Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

1
2
3
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        lp = 0
        cursum = 0
        minlen = float('inf')
        n = len(nums)
        for rp in range(n):
            cursum += nums[rp]
            while cursum >= s and lp <= rp:
                cursum -= nums[lp]
                minlen = min(minlen, rp -lp + 1)
                lp += 1
        return minlen if minlen < float('inf') else 0

322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if(len(coins)==0):
            return -1
        coins.sort(reverse=True)
        mem = {} # store all amount: minnum dictionary
        mem[0]=0
        def coinMin(amount: int) -> int:
            nonlocal coins, mem
            if(amount in mem):
                return mem[amount]
            elif coins[-1] > amount:
                mem[amount] = -1
                return -1
            else:
                minnum = -1
                for val in coins:
                    newamount = amount - val
                    if newamount < 0:
                        continue
                    else:
                        cpnum = coinMin(newamount)
                        if minnum == -1:
                            if cpnum > -1:
                                minnum = cpnum + 1
                        elif cpnum > -1:
                            minnum = min(minnum, cpnum+1)
                        else:
                            continue
                mem[amount] = minnum
                return mem[amount]
        res = coinMin(amount)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount==0:
            return 0
        if amount in coins:
            return 1
        seen = set(coins)
        dist = dict.fromkeys(coins, 1)
        search_queue = coins.copy()
        while search_queue:
            node = search_queue.pop(0)
            for c in coins:
                new_node = node + c
                if new_node in seen or new_node>amount:
                    continue
                if new_node==amount:
                    return dist[node] + 1
                seen.add(new_node)
                search_queue.append(new_node)
                dist[new_node]=dist[node]+1
        return -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
    pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
        let mut D = vec![amount+1;(amount+1) as usize];
        D[0] = 0;
        for i in 0..=amount {
            for &coin in coins.iter() {
                if coin <= i {
                   D[i as usize] = std::cmp::min(D[i as usize], D[(i-coin) as usize] + 1);
                }
            }
        }
        let retval = D[amount as usize];
        if retval > amount {
            -1
        } else {
            retval
        }
    }
}

325 Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:

1
2
3
Input: nums = [1, -1, 5, -2, 3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        summ = 0
        memo = {}
        memo[0]= -1
        mxl = 0
        for i, val in enumerate(nums):
            summ += val
            if summ - k in memo:
                mxl = max(mxl, i-memo[summ-k])
            if summ not in memo:
                memo[summ] = i
        return mxl

457 Circular Array Loop

You are given a circular array nums of positive and negative integers. If a number k at an index is positive, then move forward k steps. Conversely, if it’s negative (-k), move backward k steps. Since the array is circular, you may assume that the last element’s next element is the first element, and the first element’s previous element is the last element.

Determine if there is a loop (or a cycle) in nums. A cycle must start and end at the same index and the cycle’s length > 1. Furthermore, movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        roots = ["#" for _ in nums]
        # roots stores all the starting root for each indices
        # could be faster if we use dictionary
        n = len(nums)
        for i, c in enumerate(nums):
            if roots[i] != "#":
                continue
            roots[i] = i
            sgn = c>0
            lb = i
            idx = (i + c) % n
            if idx == i:
                continue
            pre = i
            while True:
                curstep = nums[idx]
                cursgn = curstep > 0
                if cursgn != sgn:
                    # different sign abandon current trial
                    break
                if roots[idx] == "#":
                    # not visited before set root
                    roots[idx] = lb
                elif roots[idx] == lb:
                    if pre != idx:
                        # current idx is the start point of the cycle
                        return True
                    else:
                        # lenth 1 subloop abandon
                        break
                else:
                    break
                pre = idx
                idx = (idx + curstep) % n
        return False



Search / Bisect

4. Median of Two Sorted Arrays

I would prefer to concatenate + sort…

109. Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

the crutial part is to find the mid points. For lower cost, it is better to convert the linked list ot array first for random access

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 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 sortedListToBST(self, head: ListNode) -> TreeNode:
        lis = []
        while head != None:
            lis.append(head.val)
            head = head.next
        def toTree(l:int, r:int)->TreeNode:
            if l == r:
                return TreeNode(lis[l],None, None)
            elif l <= r:
                mid = (l + r)//2
                leftNode = toTree(l, mid-1)
                rightNode = toTree(mid+1, r)
                return TreeNode(lis[mid],leftNode, rightNode)
            else:
                return None
        return toTree(0, len(lis)-1)

Sort

75 Sort Color

If there are only three values in the array it is possible to sort the array faster than quick sort

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def sortColors(self, a: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(a)
        lbench = 0
        rbench = n -1
        m = lbench
        while m <= rbench:
            if a[m] == 0:
                a[lbench], a[m] = a[m], a[lbench]
                m+=1
                lbench+=1
            elif a[m]==1:
                m+=1
            else:
                a[rbench], a[m]= a[m], a[rbench]
                rbench -= 1

This is a simpel case where we know the array takes values from a finite set (partial ordered)
We can do counting sort in general.

179 Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

1
2
Input: [10,2]
Output: "210"

Example 2:
1
2
Input: [3,30,34,5,9]
Output: "9534330"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import functools
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def compare_strNum(s0:str, s1:str)-> int:
            return 1 if s0+s1 > s1 +s0 else -1
            # minlen = min(len(s0), len(s1))
            # for i in range(minlen):
            #     if s0[i] > s1[i]:
            #         return 1
            #     elif s0[i] < s1[i]:
            #         return -1
            # if minlen < len(s0):
            #     return compare_strNum(s0[minlen:],s1)
            # elif minlen < len(s1):
            #     return compare_strNum(s0,s1[minlen:])
            # else:
            #     return 0

        strNums = [str(n) for n in nums]
        strNumsSort = sorted(strNums, key=functools.cmp_to_key(compare_strNum), reverse=True)

        return str(int("".join(strNumsSort)))

692 Top K Frequent Words

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:

1
2
3
4
Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output: ["i", "love"]
Explanation: "i" and "love" are the two most frequent words.
    Note that "i" comes before "love" due to a lower alphabetical order.

912. Sort an Array

Given an array of integers nums, sort the array in ascending order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
use std::vec::Vec;
fn partition(nums: &mut Vec<i32>, start: usize, end: usize ) -> i32 {
    let mut pivot = nums[end];

    let mut index = start;

    let mut i = start;
    while i < end {
        if nums[i] < pivot {
            nums.swap(i, index);
            index+=1;
        }
        i+=1;
    }
    nums.swap(index, end);
    return index as i32;
}

fn quick_sort(nums: &mut Vec<i32>, start: usize, end: usize) {
    if start >= end {
        return;
    }
    let pivot = partition(nums, start, end);
    // println!("=={}", pivot);
    if ((pivot as usize) > start) {
        quick_sort(nums, start, (pivot - 1) as usize);
    }
    if ((pivot as usize) < end) {
        quick_sort(nums, (pivot + 1) as usize, end);
    }
}
impl Solution {
    pub fn sort_array(nums: Vec<i32>) -> Vec<i32> {
        let mut nums = nums;
        let high = nums.len() -1;
        quick_sort(&mut nums, 0, high);
        nums
    }
}

Pattern matching

28. Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Recall the KMP algorithm, the key part is to construct the partial matching table

1
2
Given string p
T[i] := largest k such that p[0:k] == p[i-k+1: i+1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def strStr(self, s: str, p: str) -> int:
        if not p: return 0
        n, m = len(s), len(p)


        next_ = [0 for _ in range(m+1)]
        # for convenience, we use next_ = [0] + pmt
        j = 0
        # build partial match table(array)
        for i in range(1, m):
            while j and p[i] != p[j]:
                # will be skiped if comparing the head
                # the case j > 0 and p[i]!=p[j]
                j = next_[j]
                #  iteration of above line will get next longest match
                # such that p[0:k] == p[i+1-k:i+1]

            if p[i] == p[j]:
                j += 1
            next_[i+1] = j
        print(next_)
        # KMP match
        j = 0
        res = []
        for i in range(n):
            while j and p[j] != s[i]:
                j = next_[j]
            if p[j] == s[i]:
                j += 1

            if j == m:
                res.append(i -j +1)
                j = j - 1 # reset j to valid value in next
        if res: return res[0]
        return -1
        # this algorithm has infact recorded all the locations the pattern string appears

Stacks

simple use

1209. Remove All Adjacent Duplicates in String II

Given a string s, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made.

It is guaranteed that the answer is unique.

Example 1:

1
2
3
Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []
        for c in s:
            if not stack or stack[-1][0] != c:
                stack.append(c)
            elif stack[-1][0] == c:
                stack[-1] = stack[-1]+ c
                if len(stack[-1]) >= k:
                    stack.pop()
        return "".join(stack)

394 Decoding String

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Example 1:

1
2
Input: s = "3[a]2[bc]"
Output: "aaabcbc"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def decodeString(self, s: str) -> str:
        print(f"Trying to decode {s}")
        if len(s) == 0: return ""
        if s[0].isdigit():
            i = 1
            while s[i].isdigit():
                i+=1
            assert s[i] == "[", "After a number, it should be an opening bracked"
            j = i
            open_par = 1
            close_par = 0
            while open_par != close_par:
                j+=1
                if s[j] == "[": open_par+=1
                if s[j] == "]": close_par+=1
            return self.decodeString(s[i+1:j]) * int(s[:i]) + self.decodeString(s[j+1:])
        else: #if it's a letter
            return s[0]+ self.decodeString(s[1:])

Linked List

19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        fast = head
        slow = head
        for i in range(n-1):
            fast = fast.next
        newhead = ListNode(-1)
        pre = newhead
        pre.next = head
        while fast.next != None:
            fast = fast.next
            pre = slow
            slow = slow.next
        pre.next = slow.next
        return newhead.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy = ListNode::new(0);
        dummy.next = head;
        let mut dummy = Box::new(dummy);
        let mut fast = dummy.clone();
        let mut slow =  dummy.as_mut();
        // move fast n forward
        for _ in 0..n {
            fast = fast.next.unwrap();
        }

        while fast.next.is_some() {
            fast = fast.next.unwrap();
            slow = slow.next.as_mut().unwrap();
        }
        let next = slow.next.as_mut().unwrap();
        slow.next = next.next.clone();
        dummy.next
    }
}

In Plase/ COPY

Reverse a linked list from position m to n. Do it in one-pass.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if(m==n):
            return head
        head_handle = ListNode(-1)
        mid_handle = ListNode(-1) # mid_handle.next should be n in the end
        head_handle.next = head
        node_m = head_handle # finally stop at m
        node_n = head_handle # finally stop at n
        # locate m first and then run to n start from m
        prev = head_handle
        for i in range(0,m):
            prev = node_m
            node_m = node_m.next
        mid_handle.next = node_m
        node_n = node_m.next
        for j in range(m,n):
            temp = node_n.next
            node_n.next = mid_handle.next
            mid_handle.next =node_n
            node_n = temp
        ## at this moment node_n is at the head of (tail part)
        prev.next = mid_handle.next
        node_m.next = node_n
        return head_handle.next

138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
illustration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
#include <map>
class Solution {
public:
    Node* copyRandomList(Node* head) {
        std::map<Node*, Node*> old_new_map;
        Node* shuttle = head;
        if(head == NULL){
            return head;
        }
        old_new_map[NULL] = NULL;
        while(shuttle != NULL){
            Node * newNode = new Node(shuttle->val);
            old_new_map[shuttle]=newNode;
            newNode->next = shuttle->next;
            newNode->random  = shuttle->random;
            shuttle = shuttle->next;
        }
        for(auto & item: old_new_map){
            if(item.first==NULL) continue;
            item.second->next = old_new_map[item.first->next];
            item.second->random = old_new_map[item.first->random];
        }
        return old_new_map[head];
    }
};

143 Reorder Linked List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 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.
        """
        posNodeDict = {}

        pos = 0
        while head != None:
            posNodeDict[pos]= head
            head = head.next
            pos +=1
        n = pos
        handle = ListNode(-1)
        tail = handle
        print(len(posNodeDict), n)
        for i in range(n):
            idx = -1
            if i % 2 == 0:
                idx = i // 2
            else:
                idx = n - i//2 -1
            tail.next =  posNodeDict[idx]
            tail = tail.next
        tail.next = None
        return

Merge

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 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:
        resulttail = None
        result = ListNode(-1, None)
        rest = 0
        while ((l1!= None) or (l2!= None)):
            val1, l1 = (l1.val, l1.next) if (l1 != None) else (0, None)
            val2, l2 = (l2.val, l2.next)  if (l2!= None) else (0, None)
            val = (val1 + val2 + rest) % 10
            rest = (val1 + val2 + rest)//10
            if (resulttail == None):
                result.next = ListNode(val)
                resulttail = result.next
            else:
                resulttail.next = ListNode(val)
                resulttail = resulttail.next

        if rest > 0:
            resulttail.next = ListNode(rest)
        return result.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
  pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    )->Option<Box<ListNode>>{
        let mut head = ListNode::new(-1);
        let mut cur = &mut head.next;
        let (mut x,mut y) = (l1,l2);
        let mut carry = 0;
        let node_val = |node:&Option<Box<ListNode>>| node.as_ref().map_or(0, |x| x.val);
        while x.is_some() || y.is_some() || carry!=0 {
            let sum = node_val(&x)+node_val(&y)+carry;
            *cur = Some(Box::new(ListNode::new(sum % 10)));
            cur = &mut cur.as_mut().unwrap().next;
            carry = sum  / 10;
            x = x.and_then(|n| n.next);
            y = y.and_then(|n| n.next);
        }
        head.next
    }
}

Disjoint Set

find maximal union

128. Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

1
2
3
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        ancestor = {}
        size = {}
        def find(x:int)->int:
            if ancestor[x] != x:
                ancestor[x] = find(ancestor[x])
            return ancestor[x]

        def union(x, y):
            rx, ry = find(x), find(y)
            if rx == ry:
                return
            if size[rx] > size[ry]:
                ancestor[ry] = rx
                size[rx] += size[ry]
            else:
                ancestor[rx] = ry
                size[ry] += size[rx]

        for x in nums:
            if x not in ancestor:
                ancestor[x] = x
                size[x] = 1
            if (x - 1) in ancestor:
                union(x, x-1)
            if (x + 1) in ancestor:
                union(x, x+1)

        return max(size.values())

Trees

Search / Traverse

94 Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]

1
  \
    2
  /
3

Output: [1,3,2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def helper(curNode: TreeNode)->None:
            if not curNode:
                return
            else:
                helper(curNode.left)
                res.append(curNode.val)
                helper(curNode.right)
            return
        helper(root)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        leftvisited = {}
        if not root:
            return []
        stack = [root]
        while stack:
            curNode = stack.pop()
            if not curNode in leftvisited:
                stack.append(curNode)
                leftvisited[curNode]=True
                if curNode.left:
                    stack.append(curNode.left)
            else:
                res.append(curNode.val)
                if curNode.right:
                    stack.append(curNode.right)

        return res

98 Validate Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# 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 isValidBST(self, root: TreeNode) -> bool:
        def TreeRange(node:TreeNode) -> (bool, int, int):
            if not node:
                return (True, -1,-1)
            val = node.val
            leftRes, leftLB , leftUB = TreeRange(node.left)
            rightRes, rightLB, rightUB = TreeRange(node.right)
            if not leftRes or not rightRes:
                return (False, -1, -1)
            else:
                if node.left and node.right:
                    return (leftUB< val < rightLB, leftLB, rightUB)
                elif node.left:
                    return (leftUB <val, leftLB, val)
                elif node.right:
                    return (val < rightLB, val,  rightUB)
                else:
                    return (True, val, val)
        return TreeRange(root)[0]


    ### another iterative solution with stack
    def isValidBST_iter(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True

        stack = [(root, float('-inf'), float('inf')), ]
        while stack:
            root, lower, upper = stack.pop()
            if not root:
                continue
            val = root.val
            if val <= lower or val >= upper:
                return False
            stack.append((root.right, val, upper))
            stack.append((root.left, lower, val))
        return True

117 Populating Next Right Pointers in Each Node II

Given a binary tree

struct Node {
int val;
Node left;
Node right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.
illustration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        level_shadow = {}
        level_shadow[0] = None
        def connect2shadow(curNode:Node, level:int)->None:
            if not curNode:
                return
            if level not in level_shadow:
                level_shadow[level]= None
            curNode.next = level_shadow[level]
            level_shadow[level]= curNode
            connect2shadow(curNode.right, level+1)
            connect2shadow(curNode.left, level+1)
        connect2shadow(root, 0)
        return root

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if (root == None or root == p or root == q):
            return root
        else:
            l = self.lowestCommonAncestor(root.left, p, q)
            r = self.lowestCommonAncestor(root.right, p, q)

            if(l!= None and r != None):
                return root
            else:
                return l if (l!= None) else r

Non recursive solution but slow.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <unordered_map>
#include <list>
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        std::unordered_map<TreeNode*, TreeNode*> parentmap;
        std::list<TreeNode*> searchqueue;
        parentmap[root] = nullptr;
        searchqueue.push_back(root);
        while(! searchqueue.empty()){
            auto curNode = searchqueue.front();
            searchqueue.pop_front();
            if (curNode->left != nullptr){
                searchqueue.push_back(curNode->left);
                parentmap[curNode->left]= curNode;
            }
            if (curNode->right != nullptr){
                searchqueue.push_back(curNode->right);
                parentmap[curNode->right]=curNode;
            }
        }
        std::unordered_map<TreeNode*, bool> pas;
        auto pa = p;
        while(pa != nullptr){
            pas[pa]= true;
            pa = parentmap[pa];
        }
        auto qa = q;
        while(qa != nullptr){
            if (pas.find(qa) != pas.end()){
                return qa;
            }
            else {
                qa = parentmap[qa];
            }
        }
        return root;

    }
};

Paths

129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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:
        def subsum(curnode:TreeNode, pathsum:int)->int:
            if not curnode:
                return 0
            nsum = (pathsum + curnode.val) * 10
            if not curnode.left and not curnode.right:
                # curnode is a leaf
                return pathsum + curnode.val
            else:
                return subsum(curnode.left, nsum) + subsum(curnode.right,nsum)
        return subsum(root,0)

Other Manipulations

Graphs

Traverse

133. Clone Graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
"""
# 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':
        if not node:
            return None
        ONMap = {}
        searchQueue = [node]
        newHead = Node(node.val, node.neighbors)
        ONMap[node]= newHead
        while(searchQueue):
            cur = searchQueue.pop(0)
            for nb in cur.neighbors:
                if nb not in ONMap:
                    newNode = Node(nb.val, nb.neighbors)
                    ONMap[nb]=newNode
                    searchQueue.append(nb)
        for nd in ONMap:
            nbs = ONMap[nd].neighbors
            ONMap[nd].neighbors = [ONMap[x] for x in nbs]
        return newHead

Components

130 Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

Example:

X X X X

X O O X

X X O X

X O X X

After running your function, the board should be:

X X X X

X X X X

X X X X

X O X X

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board:
            return
        if(len(board)<3) or (len(board[0])<3):
            return
        m = len(board)
        n = len(board[0])
        components_map = {}
        def valid(i,j)->bool:
            return -1<i < m and -1<j<n
        def bfs(i:int, j:int, lb:str)-> None:
            search_queue = [(i,j)]
            board[i][j]=lb
            surrounded = True
            while(search_queue):
                x,y = search_queue.pop(0)
                for nbx, nby in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
                    if not valid(nbx,nby):
                        continue
                    if board[nbx][nby] == 'O':
                        board[nbx][nby]=lb
                        search_queue.append((nbx,nby))
                        if nbx ==0 or nbx == m-1 or nby==0 or nby == n-1:
                            surrounded = False


                components_map[lb] = 'X' if surrounded else 'O'

        # start with node(1,1)
        visited = {}
        search_queue = []
        # use integers to represents components


        cpnum  = 0
        for i in range(1,m-1):
            for j in range(1, n-1):
                if board[i][j]=='O':
                    # never visited before
                    bfs(i,j,str(cpnum))
                    cpnum += 1
        for i in range(m):
            for j in range(n):
                if board[i][j]!= 'X' and board[i][j] != 'O':
                    board[i][j]= components_map[board[i][j]]

1192. Critical Connections in a Network

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some server unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

1
2
3
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

The idea of Tarjan algorithm is just dfs and label each node with label timestampe and lowstamp, storing the first visit time and lowest stamp reachable from the node (but not through the parent)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        lowstamp = {}
        timestamp = {}
        graph = collections.defaultdict(list)
        for i,j in connections:
            graph[i].append(j)
            graph[j].append(i)
            # for non-directed graph case
            # only graph[i].append(j)
        dfstime = 0
        for i in range(n):
            lowstamp[i]=math.inf
        componentstack = []
        onstack = {}
        def dfs(curNode:int=0, parNode:int=-1):
            nonlocal dfstime
            if curNode not in timestamp:
                timestamp[curNode]=dfstime
                lowstamp[curNode]=dfstime
                onstack[curNode]=True
                componentstack.append(curNode)
                dfstime += 1
            for neighbor in graph[curNode]:
                if neighbor == parNode:
                    continue
                if neighbor not in timestamp:
                    # never visited before
                    dfs(neighbor, curNode)
                    lowstamp[curNode] = min(lowstamp[curNode],lowstamp[neighbor])
                else:
                    lowstamp[curNode] = min(lowstamp[curNode],timestamp[neighbor])
            if lowstamp[curNode]==timestamp[curNode]:
                while True:
                    nd = componentstack.pop()
                    onstack[nd]=False
                    lowstamp[nd] = min(lowstamp[nd], lowstamp[curNode])
                    if nd == curNode:
                        break
            return
        dfs(0)
        res =[]
        print(lowstamp)
        for x,y in connections:
            if lowstamp[x] != lowstamp[y]:
                res.append([x,y])
        return res

Paths

127 Word Ladder

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list.
Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:

Input:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

Output: 5

Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        ABC = "abcdefghijklmnopqrstuvwxyz"
        if endWord not in wordList:
            return 0
        if beginWord not in wordList:
            wordList.append(beginWord)
        posdic = {}
        for i, word in enumerate(wordList):
            posdic[word] = i
        beginidx, endidx = posdic[beginWord],posdic[endWord]
        def neighbors(curword:str):
            res = set()
            for i in range(len(curword)):
                for c in ABC:
                    if(c == curword[i]):
                        continue
                    sword = curword[:i]+c+curword[i+1:]
                    if sword in posdic:
                        res.add(posdic[sword])
            return res
        graph = [neighbors(i) for i in wordList]
        def Dijkstra(begin:int, end:int, graph)->int:
            prevs = {}
            dists = {}
            N = len(graph) * 2
            for i in range(len(graph)):
                dists[i] = N
            # prevs[begin]= -1
            dists[begin]=0
            search_queue = [begin]
            while(search_queue):
                curnode = search_queue.pop(0)
                if curnode == end:
                    break
                for j in graph[curnode]:
                    alt = dists[curnode] + 1
                    if alt <dists[j]:
                        dists[j]= alt
                        # prevs[j]= curnode
                        search_queue.append(j)
            if dists[end]==N:
                return -1
            else:
                return dists[end]
        return Dijkstra(beginidx, endidx, graph) + 1



499 The Maze III

Slightly different from 505

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up (u), down (d), left (l) or right (r), but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction. There is also a hole in this maze. The ball will drop into the hole if it rolls on to the hole.

Given the ball position, the hole position and the maze, find out how the ball could drop into the hole by moving the shortest distance. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the hole (included). Output the moving directions by using ‘u’, ‘d’, ‘l’ and ‘r’. Since there could be several different shortest ways, you should output the lexicographically smallest way. If the ball cannot reach the hole, output “impossible”.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The ball and the hole coordinates are represented by row and column indexes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
        #用heap排序

        m, n, q, dist = len(maze), len(maze[0]), [(0, "", ball[0], ball[1])], {(ball[0], ball[1]):(0, "")}
        while q:
            curdist, curpath, x, y = heapq.heappop(q)
            if [x, y] == hole:
                break
            for dirchar,i, j in (('u',-1, 0), ('d',1, 0), ('l',0, -1), ('r',0, 1)):
                newX, newY, d = x, y, 0
                while 0 <= newX + i < m and 0 <= newY + j < n and maze[newX + i][newY + j] != 1:
                    newX += i
                    newY += j
                    d += 1
                    if [newX, newY] == hole:
                        break
                if d == 0:
                    continue
                newdist, newpath = (curdist + d, curpath + dirchar)
                if (newX, newY) not in dist or newdist < dist[(newX, newY)][0]:
                    dist[(newX, newY)] = (newdist, newpath)
                    heapq.heappush(q, (newdist, newpath, newX, newY))
                elif newdist == dist[(newX, newY)][0]:
                    lowpath =min(newpath, dist[(newX, newY)][1])
                    dist[(newX, newY)] = (newdist, lowpath)
                    heapq.heappush(q, (newdist, lowpath, newX, newY))
        return dist[(hole[0],hole[1])][1] if (hole[0], hole[1]) in dist else "impossible"

505. The Maze II

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball’s start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input 1: a maze represented by a 2D array

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (4, 4)

Output: 12

Explanation: One shortest way is : left -> down -> left -> down -> right -> down -> right.
             The total distance is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.


""

This DFS results in TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import numpy as np
from typing import Tuple
class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        dirMap={0:np.array([1,0]),1:np.array([0,1]),2:np.array([-1,0]),3:np.array([0,-1])}
        nmaze = np.array(maze)
        nstart = np.array(start)
        target = np.array(destination)
        m = len(maze)
        n = len(maze[0])
        @lru_cache(None)
        def nextStop(x:int,y:int,direct:int)->Tuple[np.array,int]:
            vec = dirMap[direct]
            cur = np.array([x,y])
            count = 0
            while True:
                next = cur + vec
                if 0<= next[0] < m and 0 <= next[1] < n and nmaze[next[0]][next[1]] == 0:
                    cur = next
                    count += 1
                else:
                    break
            return cur, count
        visited = [[False] * n for _ in range(m)]
        srtdist = math.inf
        def dfs(root:np.array, curlen:int):
            nonlocal srtdist
            if curlen >= srtdist:
                return
            if (root == target).all():
                srtdist = min(srtdist, curlen)
            else:
                for direc in range(4):
                    nextstop, length = nextStop(root[0],root[1], direc)
                    if length != 0 and not visited[nextstop[0]][nextstop[1]]:
                        visited[nextstop[0]][nextstop[1]] = True
                        dfs(nextstop, length + curlen)
                        visited[nextstop[0]][nextstop[1]] = False
            return
        visited[nstart[0]][nstart[1]] = True
        dfs(nstart,0)
        visited[nstart[0]][nstart[1]] = False

        return srtdist if srtdist < math.inf else -1

The DFS actually pass through but still quite slow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import numpy as np
from typing import Tuple
class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        dirMap={0:np.array([1,0]),1:np.array([0,1]),2:np.array([-1,0]),3:np.array([0,-1])}
        nmaze = np.array(maze)
        nstart = np.array(start)
        target = np.array(destination)
        m = len(maze)
        n = len(maze[0])
        @lru_cache(None)
        def nextStop(x:int,y:int,direct:int)->Tuple[np.array,int]:
            vec = dirMap[direct]
            cur = np.array([x,y])
            count = 0
            while True:
                next = cur + vec
                if 0<= next[0] < m and 0 <= next[1] < n and nmaze[next[0]][next[1]] == 0:
                    cur = next
                    count += 1
                else:
                    break
            return cur, count
        visited = [[False] * n for _ in range(m)]
        srtdist = math.inf
        dp  = [[math.inf] * n for _ in range(m)] # store the min distance from the start
        dp[nstart[0]][nstart[1]] = 0
        srtlen = math.inf
        def dfs(x:int, y:int, curlen:int):
            nonlocal srtlen
            if curlen >= srtlen:
                return
            if x== target[0] and y == target[1]:
                srtlen = min(srtlen, curlen)
                return
            else:
                localmin =  math.inf
                for direc in range(4):
                    nextstop, length = nextStop(x,y, direc)
                    if length != 0:
                        if dp[x][y] + length < dp[nextstop[0]][nextstop[1]]:
                            dp[nextstop[0]][nextstop[1]] = dp[x][y] + length
                            dfs(nextstop[0],nextstop[1],curlen + length)
                return

        dfs(nstart[0],nstart[1],0)
        res  = dp[target[0]][target[1]]
        return res if res < math.inf else -1

Faster than DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import numpy as np
from typing import Tuple
class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        dirMap={0:np.array([1,0]),1:np.array([0,1]),2:np.array([-1,0]),3:np.array([0,-1])}
        nmaze = np.array(maze)
        nstart = np.array(start)
        target = np.array(destination)
        m = len(maze)
        n = len(maze[0])
        @lru_cache(None)
        def nextStop(x:int,y:int,direct:int)->Tuple[np.array,int]:
            vec = dirMap[direct]
            cur = np.array([x,y])
            count = 0
            while True:
                next = cur + vec
                if 0<= next[0] < m and 0 <= next[1] < n and nmaze[next[0]][next[1]] == 0:
                    cur = next
                    count += 1
                else:
                    break
            return cur[0],cur[1],count
        visited = [[False] * n for _ in range(m)]
        srtdist = math.inf
        dp  = [[math.inf] * n for _ in range(m)] # store the min distance from the start
        dp[nstart[0]][nstart[1]] = 0
        srtlen = math.inf
        queue = [start]
        while queue:
            curx, cury = queue.pop()
            for direc in range(4):
                nxx, nxy, length = nextStop(curx,cury,direc)
                val = dp[curx][cury] + length
                if val < dp[nxx][nxy] and val < dp[target[0]][target[1]]:
                    queue.append([nxx,nxy])
                    dp[nxx][nxy] = val

        res  = dp[target[0]][target[1]]
        return res if res < math.inf else -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        m, n, q, stopped = len(maze), len(maze[0]), [(0, start[0], start[1])], {(start[0], start[1]):0}
        while q:
            dist, x, y = heapq.heappop(q)
            if [x, y] == destination:
                return dist
            for i, j in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                newX, newY, d = x, y, 0
                while 0 <= newX + i < m and 0 <= newY + j < n and maze[newX + i][newY + j] != 1:
                    newX += i
                    newY += j
                    d += 1
                if (newX, newY) not in stopped or dist + d < stopped[(newX, newY)]:
                    stopped[(newX, newY)] = dist + d
                    heapq.heappush(q, (dist + d, newX, newY))
        return -1

1293. Shortest Path in a Grid with Obstacles Elimination

You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:

        rows, cols = len(grid), len(grid[0])
        target = (rows - 1, cols - 1)

        def manhattan_distance(row, col):
            return target[0] - row + target[1] - col

        # (row, col, remaining_elimination)
        state = (0, 0, k)

        # (estimation, steps, state)
        # h(n) = manhattan distance,  g(n) = 0
        queue = [(manhattan_distance(0, 0), 0, state)]
        seen = set([state])

        while queue:
            estimation, steps, (row, col, remain_eliminations) = heapq.heappop(queue)

            # we can reach the target in the shortest path (manhattan distance),
            #   even if the remaining steps are all obstacles
            remain_min_distance = estimation - steps
            if remain_min_distance <= remain_eliminations:
                return estimation

            # explore the four directions in the next step
            for new_row, new_col in [(row, col + 1), (row + 1, col), (row, col - 1), (row - 1, col)]:
                # if (new_row, new_col) is within the grid boundaries
                if (0 <= new_row < rows) and (0 <= new_col < cols):
                    new_eliminations = remain_eliminations - grid[new_row][new_col]
                    new_state = (new_row, new_col, new_eliminations)

                    # if the next direction is worth exploring
                    if new_eliminations >= 0 and new_state not in seen:
                        seen.add(new_state)
                        new_estimation = manhattan_distance(new_row, new_col) + steps + 1
                        heapq.heappush(queue, (new_estimation, steps + 1, new_state))

        # did not reach the target
        return -1

Directed Graph/ Topological Sort

207 Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def canFinish(self, numCourses: int, prerequisites) -> bool:
        res = []
        graph = [[] for _ in range(numCourses)]
        graph_backward = [[] for _ in range(numCourses)]
        for x, y in prerequisites:
            graph[x].append(y)
            graph_backward[y].append(x)
        queue = [node for node in range(numCourses) if not graph_backward[node]]

        while queue:
            node = queue.pop(0)
            res.append(node)
            for m in graph[node]:
                graph_backward[m].remove(node)
                if not graph_backward[m]:
                    queue.append(m)
            graph[node]=[]

            # print(res)
        return len(res)==numCourses
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def canFinish(self, numCourses: int, prerequisites) -> bool:
    statedict = dict(zip(list(range(numCourses)), [0 for _ in range(numCourses)]))
    res = []
    graph = [[] for _ in range(numCourses)]
    for x, y in prerequisites:
        graph[x].append(y)
    def dfs(i):
        # print(i,graph[i])
        if statedict[i] == 0:
            # activate it with mark 1
            statedict[i] = 1
            for j in graph[i]:
                if not dfs(j):
                    return False
        elif statedict[i] == 1:
            # cycle detected
            return False
        elif statedict[i] == 2:
            return True
        statedict[i] = 2
        res.insert(0,i)
        return True

    # print(dfs(0))
    for i in range(numCourses):
        if not dfs(i):
            return False
    return True

210 Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        res = []
        graph = [[] for _ in range(numCourses)]
        graph_backward = [[] for _ in range(numCourses)]
        for x, y in prerequisites:
            graph[x].append(y)
            graph_backward[y].append(x)
        queue = [node for node in range(numCourses) if not graph[node]]
        while queue:
            node = queue.pop(0)
            res.append(node)
            for m in graph_backward[node]:
                graph[m].remove(node)
                if not graph[m]:
                    queue.append(m)
        if len(res)!= numCourses:
            return []
        return res

277 Find the Celebrity

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def findCelebrity(self, n):
        """
        :type n: int
        :rtype: int
        """
        candi = 0
        # go to the first sink in the graph
        for i in range(1, n):
            if knows(candi, i):
                candi = i
        # if there is really one celebrity, candi shoudl already capture it.
        for i in range(n):
            if i != candi and knows(candi, i):
                return -1
            if i != candi and not knows(i, candi):
                return -1

        return ans

Dynamic Programming

One Fold

120 Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        min_dist=[triangle[0][0]]
        for i, item  in enumerate(triangle):
            if i == 0:
                continue
            for j in range(len(item)-1, -1, -1):
                # in reversed order avoid copy min_dist
                if j == 0:
                    min_dist[j]= min_dist[j] + item[j]
                elif j == len(item)-1:
                    min_dist.append(min_dist[j-1] + item[j])
                else:
                    min_dist[j] = min(min_dist[j],min_dist[j - 1]) + item[j]
        return min(min_dist)

this approach is slower than DP because it has to go through some unnecessary paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import heapq
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        MAX = 10 ** 10
        dists = [[MAX for _ in r] for r in triangle]
        dists[0][0]= triangle[0][0]
        search_queue = [(dists[0][0],0,0)]
        heapq.heapify(search_queue)
        while(search_queue):
            curdis, row, col =heapq.heappop(search_queue)
            left, right =  col, col +1
            if row < len(triangle)-1:
                for ncol in [left, right]:
                    alt = curdis + triangle[row+1][ncol]
                    if alt < dists[row+1][ncol]:
                        dists[row+1][ncol] = alt
                        heapq.heappush(search_queue,(alt,row+1, ncol))
        mindis = MAX
        for dis in dists[-1]:
            if dis < mindis:
                mindis = dis
        return mindis

918 Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], …, C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

1
2
3
Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:
1
2
3
Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

This is a typical Kadane’s Algorithm for calculating max/min sum subarray in array, it is a hiden 1d dynamic progrming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:

        S = 0
        ans1 = -float("inf")
        # that end in index i, not necessarily include A[i]
        curSum = -float("inf")
        # dpmax_ = [-inf,0,0,0,...,0] length n + 1, stores maxsum subarr
        #that end in index i, strictly include A[i]
        ans2 = float("inf")
        curSum2 = float("inf")
        # dpmin_ = [-inf,0,0,0,...,0] length n + 1,
        # stores minsum subarr that end in index i, strictly include A[i]
        for x in A:
        # for i in range(1,n+1)
            S += x
            curSum = x + max(0, curSum)
            # dpmax_[i] = A[i] + dpmax_[i-1]
            ans1 = max(ans1, curSum)
            curSum2 = min(0, curSum2) + x
            # dpmin_[i] = min(0, dpmin_[i-1]) + A[i]
            ans2 = min(ans2,curSum2)


        ans2 = S - ans2 # reverse to get the maxSum of two range intervals
        if ans2 == 0:
            # if max sum of two range interval  is zero (then it is empty, should not compare it)
            return ans1
        else:
            return max(ans1,ans2)

689. Maximum Sum of 3 Non-Overlapping Subarrays

In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.
Example:

1
2
3
4
Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

The following algorithm can be generalized to N-nonoverlapping constant length subarrs. For non-constant length refer to

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        dp  = [[0 for _ in range(n)] for _ in range(1,4)]
        cursum = 0
        dpidx = [[[k* s for s in range(j)] for _ in range(n)] for j in range(1,4)]
        for i in range(3):
            cursum = 0
            for j , x in enumerate(nums):
                cursum = cursum + x - (nums[j-k] if j>=k else 0)
                if j == 0:
                    dp[i][j] = x
                elif j < (i+1) * k:
                    dp[i][j] = dp[i][j-1] + x
                else:
                    # j >= (i+1) * k
                    # compare dp[i][j-1] and dp[i-1][j-k] + cursum
                    if i > 0:
                        if dp[i][j-1] < dp[i-1][j-k] + cursum:
                            dp[i][j] = dp[i-1][j-k] + cursum
                            dpidx[i][j] = dpidx[i-1][j-k] + [j-k+1]
                        else:
                            dp[i][j] = dp[i][j-1]
                            dpidx[i][j] = dpidx[i][j-1]
                    else:
                        if dp[i][j-1] < cursum:
                            dp[i][j] = cursum
                            dpidx[i][j] = [j-k+1]
                        else:
                            dp[i][j] = dp[i][j-1]
                            dpidx[i][j] = dpidx[i][j-1]
        return dpidx[-1][-1]

188. Best Time to Buy and Sell Stock IV

Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

1
2
3
Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:
1
2
3
4
Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if k >= len(prices)//2:
            return sum(max(0, prices[i] - prices[i-1]) for i in range(1, len(prices)))
        # if not prices:
        #     return 0
        # Kadane's algo
        ##
        n = len(prices)
        dp = [0] * n
        for _ in range(k):
            val = 0
            for i in range(1, n):
                val = max(dp[i], val+prices[i]-prices[i-1])
                dp[i] = max(dp[i-1],val)
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if k >= len(prices)//2:
            return sum(max(0, prices[i] - prices[i-1]) for i in range(1, len(prices)))

        cost, pnl = [inf]*k, [0]*k
        for price in prices:
            for i in range(k):
                cost[i] = min(buy[i], price - (pnl[i-1] if i else 0))
                pnl[i] = max(pnl[i], price - cost[i])
        return pnl[-1] if prices and k else 0

1043 Partition Array for Maximum Sum

Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:

1
2
3
Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:
        n = len(A)
        dp = [float("-inf") for _ in A]
        dp[0]= A[0]
        if n == 0:
            return A[0]
        rMax = {}
        def rangeMax(start:int, end:int)->int:
            # return max in the inclusive range
            if (start, end) in rMax:
                return rMax[(start, end)]
            elif start == end:
                rMax[(start,end)]= A[start]
                return A[start]
            else:
                res = max(rangeMax(start,end-1),A[end])
                rMax[(start,end)]=res
                return res
        # dp[x] = max([dp[x-i]+max(A[x-i+1: x]) * (x-i)) for i in range(min(x+1,k))])
        # use a memorization for the range max

        for i in range(1,len(A)):
            for j in range(max(i-K,-1), i):
                candi = -1
                if j == -1:
                    candi = rangeMax(0,i) * (i+1)
                else:
                    candi = dp[j] + rangeMax(j+1,i) * (i-j)
                dp[i] = max(dp[i],candi)
        return dp[n-1]

    # same idea but shorter and faster
    def maxSumAfterPartitioning1(self, A: List[int], K: int) -> int:
        N = len(A)
        dp = [0] * (N + 1)
        for i in range(N):
            curMax = 0
            for k in range(1, min(K, i+1) + 1):
                curMax = max(curMax, A[i - k + 1])
                dp[i] = max(dp[i], dp[i-k] + curMax * k)
        return dp[N - 1]

1477 Find Two Non-overlapping Sub-arrays Each with Target Sum

Given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        inf = 100000000
        n = len(arr)
        minlen = [inf] * n
        res = inf
        sm = 0
        s = 0
        minl = inf
        for e in range(n):
            sm += arr[e]
            while sm > target:
                sm -= arr[s]
                s += 1
            if sm == target:
                curl = e - s + 1
                if s > 0 and minlen[s-1] != inf:
                    res = min(res, curl + minlen[s-1])
                minl = min(minl, curl)
            minlen[e] = minl
        if res >= inf: return -1
        return res

Two Fold

10 Regular expression matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:

1
2
3
4
5
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:
1
2
3
4
5
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def isMatch(self, text, pattern):
        dp = [[False] * (len(pattern) + 1) for _ in range(len(text) + 1)]

        dp[-1][-1] = True
        for i in range(len(text), -1, -1):
            for j in range(len(pattern) - 1, -1, -1):
                first_match = i < len(text) and pattern[j] in {text[i], '.'}
                if j+1 < len(pattern) and pattern[j+1] == '*':
                    dp[i][j] = dp[i][j+2] or first_match and dp[i+1][j]
                else:
                    dp[i][j] = first_match and dp[i+1][j+1]

        return dp[0][0]

96 Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST’s:

1
2
3
4
5
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    def numTrees(self, n: int) -> int:
        G = [0 for _ in range(n+1)]
        F = [[0 for _ in range(n+1)] for _ in range(n+1)]
        if n  == 1:
            return 1
        G[0] = 1
        F[0][0] = 1
        # F[i][j] means the number of trees with j nodes and with root i
        # j > i
        for j in range(n+1):
            for i in range(j):
                left_num = i
                right_num = j-i-1
                F[i][j] = G[left_num]*G[right_num]
                G[j] += F[i][j]
        return G[-1]

    def numTrees_recursive_with_memo(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        memo = {}
        memo[0] = 1
        memo[1] = 1
        def count_trees(num:int)->int:
            if num in memo:
                return memo[num]
            allNum = 0
            for leftNum in range(num):  # pick up a root
                rightNum = num - leftNum -1
                allNum += count_trees(leftNum) * count_trees(rightNum)

            memo[num] = allNum
                # connect left and right subtrees to the root
            return allNum

        return count_trees(n) if n else 0

95 Unique Binary Search Trees II

Same as previsous but generate all unique bsts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# 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 generateTrees(self, n: int) -> List[TreeNode]:
        if n == 0:
            return []
        def copyTree(node:TreeNode, shift:int)->TreeNode:
            if not node:
                return None
            if not node.left and not node.right:
                return TreeNode(node.val+shift)
            else:
                return TreeNode(node.val+shift, copyTree(node.left,shift), copyTree(node.right, shift))

        memo = [[[None] for _ in range(n+1)] for _ in range(n+1)]

        memo[1][0] = [TreeNode(1)]
        res = []
        for num in range(1,n+1):
            res = []
            for leftNum in range(num):
                rightNum = num - leftNum -1
                val = leftNum + 1
                leftTrees = memo[leftNum][0]
                rightTrees = memo[rightNum][val]
                for lt in leftTrees:
                    for rt in rightTrees:
                        res.append(TreeNode(leftNum + 1, lt, rt))
            memo[num][0] = res
            for shift in range(1, n-num+1):
                memo[num][shift] = [copyTree(tr, shift) for tr in res]
        return memo[n][0]

def generateTrees_recrusive(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        def generate_trees(start, end):
            if start > end:
                return [None,]

            all_trees = []
            for i in range(start, end + 1):  # pick up a root
                # all possible left subtrees if i is choosen to be a root
                left_trees = generate_trees(start, i - 1)

                # all possible right subtrees if i is choosen to be a root
                right_trees = generate_trees(i + 1, end)

                # connect left and right subtrees to the root i
                for l in left_trees:
                    for r in right_trees:
                        current_tree = TreeNode(i)
                        current_tree.left = l
                        current_tree.right = r
                        all_trees.append(current_tree)

            return all_trees

        return generate_trees(1, n) if n else []

312 Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:

1
2
3
4
Input: [3,1,5,8]
Output: 167
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1]+nums+[1]
        n = len(nums)
        dp = [[0] * n for _ in nums]
        # dp[x][y]  store the max val for existing burst bolloons are from x to y

        for left in range(n-2,-1,-1):
            for right in range(left+2, n): ## must engineer in correct direction so that dp are built correctly
                dp[left][right]= max(nums[left]* nums[i]* nums[right] + dp[left][i] + dp[i][right] for i in range(left+1,right))
        return dp[0][n-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from functools import lru_cache

class Solution:
    def maxCoins(self, nums: List[int]) -> int:

        # reframe the problem
        nums = [1] + nums + [1]
        # cache this
        @lru_cache(None) # memorized on stack
        def dp(left, right):

            # no more balloons can be added
            if left + 1 == right: return 0

            # add each balloon on the interval and return the maximum score
            return max(nums[left] * nums[i] * nums[right] + dp(left, i) + dp(i, right) for i in range(left+1, right))

        # find the maximum number of coins obtained from adding all balloons from (0, len(nums) - 1)
        return dp(0, len(nums)-1)

Backtracking

General

77 Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

1
2
3
4
5
6
7
8
9
10
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # avail = {}
        # for i in range(1, n+1):
        #     avail[i]=True
        res = []
        def backtrack(rem:int, cur:int, seq:List[int]):
            if rem == 0:
                res.append(seq.copy())
                return
            for i in range(cur+1,n+1):
                seq.append(i)
                backtrack(rem -1, i, seq)
                seq.pop()
            return
        backtrack(k, 0,[])
        return res

294 Flip Game II

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive “++” into “—“. The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

Example:

1
2
3
Input: s = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    memo = {}
    def canWin(self, s: str) -> bool:
        # can Win means it taks odd number of flips to make s unflipable
        # else it means the first player will lose
        if s in self.memo:
            return self.memo[s]
        if len(s) < 2:
            return False
        for i in range(0, len(s)-1):
            if s[i:i+2] == "++" and not self.canWin(s[:i]+"--"+s[i+2:]):
                self.memo[s] = True
                return True
        self.memo[s]= False
        return False

351 Android Unlock Patterns

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

Rules for a valid pattern:

  1. Each pattern must connect at least m keys and at most n keys.
  2. All the keys must be distinct.
  3. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.
  4. The order of keys used matters.

illustration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        buttons = list(range(1,10))
        midPair = {2:[(1,3)],4:[(1,7)],6:[(3,9)],8:[(7,9)],5:[(1,9),(2,8),(3,7),(4,6)]}
        interReq = {}
        for key in midPair:
            for u, v in midPair[key]:
                interReq[(u,v)]=key
                interReq[(v,u)]=key
        avail = {}
        for key in range(1,10):
            avail[key]=True
        def isValid(thisNum:int, nextNum:int)->bool:
            if not avail[nextNum]:
                return False
            elif (thisNum, nextNum) in interReq:
                inter = interReq[(thisNum, nextNum)]
                if not avail[inter]:
                    return True
                else:
                    return False
            else:
                return True

        def calcFromCurState(start:int, length:int)->int:
            avail[start]= False
            if length == 1:
                avail[start]= True
                return 1
            summ = 0
            for nextNum in range(1,10):
                if isValid(start, nextNum):
                    summ += calcFromCurState(nextNum,length-1)
            avail[start]=True
            return summ

        res = 0
        for i in range(m, n+1):
            if i <10:
                res += calcFromCurState(1, i) * 4
                res += calcFromCurState(2, i) * 4
                res += calcFromCurState(5, i) * 1
        return res

698 Partition to K Equal Sum Subsets

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

1
2
3
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:

    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        color = [0 for _ in nums] # final result should be 1 to k
        nums.sort(reverse=True)
        n = len(nums)
        total = sum(nums)
        if total % k != 0:
            return False
        target = total // k
        def dfs(remtarget:int, start:int,level:int)->bool:
            color[start]=level
            if remtarget == nums[start]:
                if level == k:
                    return True
                else:
                    # one level finished
                    # find the first index unoccupied
                    for idx in range(n):
                        val = nums[idx]
                        if color[idx] == 0:
                            if dfs(target, idx, level+1):
                                return True
            else:
                # find the first index > start that nums[indx] smaller than remtarget
                for idx in range(start+1,n):
                    val = nums[idx]
                    if (remtarget-nums[start] >= val and color[idx]==0):
                        color[idx] = level
                        if dfs(remtarget-nums[start], idx, level):
                            return True
            color[start] = 0
            return False
        res = dfs(target,0, 1)
        return res

Other

Math Tricks

829 Consecutive Number Sum

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?

Example 1:

1
2
3
Input: 5
Output: 2
Explanation: 5 = 5 = 2 + 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import numpy as np
class Solution:
    def consecutiveNumbersSum(self, N: int) -> int:
        def sumVal(start:int, end:int)->int:
            if start == end:
                return start
            else:
                return (start + end) *(end-start+1) // 2
#         def bisecSearch(target:int,left:int, right:int,trialFunc)->int:
#             mid = (left + right)//2
#             while left <= right:
#                 val = trialFunc(mid)
#                 if val== target:
#                     return mid
#                 elif val < target:
#                     left = mid +1
#                 elif val > target:
#                     right = mid -1
#                 mid = (left + right)//2
#             return -1
#         res = 1
#         for start in range(1,(N+1)//2):
#             trialFunc = lambda x: sumVal(start, x)
#             find = bisecSearch(N, start, N, trialFunc)
#             if find != -1:
#                 res += 1

#         return res
        res = 0
        upbound = int(np.sqrt(2 * N)) + 1
        for k in range(1, upbound):
            mul = N - sumVal(1,k)
            if mul % k == 0:
                res += 1
        return res

Concurrence

Data Structures Design

146. LRU_cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
class DLinkedNode():
    def __init__(self):
        self.key = 0
        self.value = 0
        self.prev = None
        self.next = None

class LRUCache():
    def _add_node(self, node):
        """
        Always add the new node right after head.
        """
        node.prev = self.head
        node.next = self.head.next

        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        """
        Remove an existing node from the linked list.
        """
        prev = node.prev
        new = node.next

        prev.next = new
        new.prev = prev

    def _move_to_head(self, node):
        """
        Move certain node in between to the head.
        """
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self):
        """
        Pop the current tail.
        """
        res = self.tail.prev
        self._remove_node(res)
        return res

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cache = {}
        self.size = 0
        self.capacity = capacity
        self.head, self.tail = DLinkedNode(), DLinkedNode()

        self.head.next = self.tail
        self.tail.prev = self.head


    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        node = self.cache.get(key, None)
        if not node:
            return -1

        # move the accessed node to the head;
        self._move_to_head(node)

        return node.value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        node = self.cache.get(key)

        if not node:
            newNode = DLinkedNode()
            newNode.key = key
            newNode.value = value

            self.cache[key] = newNode
            self._add_node(newNode)

            self.size += 1

            if self.size > self.capacity:
                # pop the tail
                tail = self._pop_tail()
                del self.cache[tail.key]
                self.size -= 1
        else:
            # update the value.
            node.value = value
            self._move_to_head(node)

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class MinStack:

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

    def push(self, x: int) -> None:
        if not self.current_min or  x <= self.current_min[-1]:
            self.current_min.append(x)
            self.stack.append(x)
        else:
            self.stack.append(x)

    def pop(self) -> None:
        if self.current_min[-1] == self.stack[-1]:
            self.stack.pop(-1)
            self.current_min.pop(-1)
        else:
            self.stack.pop(-1)

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


    def getMin(self) -> int:
        return self.current_min[-1]

460 LFU Cache

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

1
2
3
4
5
6
7
8
9
10
11
12
LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Node:

	def __init__(self, key, val, freq):
		self.key = key
		self.val = val
		self.freq = freq

class LFUCache:

	def __init__(self, capacity: int):
		self.capacity = capacity
		self.mapping = {}
		self.freq_mapping = collections.defaultdict(collections.OrderedDict)
		self.min_freq = None

	def get(self, key: int) -> int:
		if key not in self.mapping:
			return -1

		node = self.mapping[key]
		self.freq_mapping[node.freq].pop(key)

		if not self.freq_mapping[node.freq]:
			self.freq_mapping.pop(node.freq)

		node.freq += 1
		self.freq_mapping[node.freq][key] = node

		if not self.freq_mapping[self.min_freq]:
			self.min_freq += 1

		return node.val

	def put(self, key: int, value: int) -> None:
		if not self.capacity:
			return

		if key in self.mapping:
			self.mapping[key].val = value
			self.get(key)
			return
		else:
			if len(self.mapping) == self.capacity:
				k, n = self.freq_mapping[self.min_freq].popitem(last=False)
				self.mapping.pop(k)

			new_node = Node(key, value, 1)
			self.mapping[key] = new_node
			self.freq_mapping[1][key] = new_node
			self.min_freq = 1
			return

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

432 All O one Data structure

Implement a data structure supporting the following operations:

1
2
3
4
Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".
GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string "".

Challenge: Perform all these in O(1) time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class Node:
    def __init__(self, count, keys):
        self.count = count
        self.keys = keys
        self.next = None
        self.prev = None

class AllOne:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.head = Node(None, None)
        self.tail = Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.key2node = {}

    def remove_node(self, node):
        if node not in {self.head, self.tail}:
            left = node.prev
            right = node.next
            left.next, right.prev = right, left

    def insert_node(self, count, key, left, right):
        new_node = Node(count, {key})
        left.next, new_node.prev = new_node, left
        right.prev, new_node.next = new_node, right
        return new_node

    def print_structure(self):
        print({k: v.count for k, v in self.key2node.items()})
        forward = []
        node = self.head
        while node:
            forward.append((node.count, node.keys))
            node = node.next
        backward = []
        node = self.tail
        while node:
            backward.append((node.count, node.keys))
            node = node.prev
        print("FORWARD:", forward)
        #print("BACKWARD:", backward)

    def inc(self, key: str) -> None:
        """
        Inserts a new key <Key> with value 1. Or increments an existing key by 1.
        """
        if key in self.key2node:
            node = self.key2node.pop(key)
            node.keys.remove(key)
            desired_count = node.count + 1
        else:
            node = self.head
            desired_count = 1
        if node.next.count == desired_count:
            new_node = node.next
            new_node.keys.add(key)
        else:
            new_node = self.insert_node(desired_count, key, node, node.next)
        if not node.keys:
            self.remove_node(node)
        self.key2node[key] = new_node
        #self.print_structure()

    def dec(self, key: str) -> None:
        """
        Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
        """
        if key not in self.key2node:
            return
        node = self.key2node.pop(key)
        node.keys.remove(key)
        desired_count = node.count - 1
        if node.prev.count == desired_count:
            new_node = node.prev
            new_node.keys.add(key)
            self.key2node[key] = new_node
        elif desired_count != 0:
            new_node = self.insert_node(desired_count, key, node.prev, node)
            self.key2node[key] = new_node
        if not node.keys:
            self.remove_node(node)
        #self.print_structure()


    def getMaxKey(self) -> str:
        """
        Returns one of the keys with maximal value.
        """
        node = self.tail.prev
        if node == self.head:
            return ""
        for val in node.keys:
            return val


    def getMinKey(self) -> str:
        """
        Returns one of the keys with Minimal value.
        """
        node = self.head.next
        if node == self.tail:
            return ""
        for val in node.keys:
            return val



# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()
0%