This is my learning notes on various topics.

Data Structure & Algorithms

Computer Network

Concepts

Operating System

Linux

Software Design

System Design

Interview

Leetcode

Casual

Resources

int findKthSmallest(int vec1[], int n1, int vec2[], int n2, int k) 
{ 
    if (n1 == 0)
        return vec2[k-1]; 
    else if (n2 == 0) 
        return vec1[k-1]; 
    if (k == 1)
        return vec1[0] < vec2[0] ? vec1[0] : vec2[0]; 
     
    int idx1 = n1*1.0 / (n1 + n2) * (k - 1); 
    int idx2 = k - idx1 - 2; 
    if (vec1[idx1] == vec2[idx2]) 
        return vec1[idx1]; 
    else if (vec1[idx1] < vec2[idx2]) 
        return findKthSmallest(&vec1[idx1+1], n1-idx1-1, vec2, idx2+1, k-idx1-1); 
    else 
        return findKthSmallest(vec1, idx1+1, &vec2[idx2+1], n2-idx2-1, k-idx2-1); 
}

Binary Tree

If every node has either 0 or 2 children, a binary tree is called full.
If the lowest d-1 levels of a binary tree of height d are filled and level d is partially filled from left to right, the tree is called complete.
If all d levels of a height-d binary tree are filled, the tree is called perfect.
A perfect tree of height h has \(2^{h+1} - 1\) nodes.
In a non-empty, full binary tree, the number of internal nodes is always 1 less than the number of leaves.

# Python implementation of Binary Indexed Tree
# The idea is based on the fact that all positive integers can be represented as the sum of powers of 2.
  
# Returns sum of arr[0..index]. This function assumes
# that the array is preprocessed and partial sums of
# array elements are stored in BITree[].
def getsum(BITTree,i):
    s = 0 #initialize result
  
    # index in BITree[] is 1 more than the index in arr[]
    i = i+1
  
    # Traverse ancestors of BITree[index]
    while i > 0:
  
        # Add current element of BITree to sum
        s += BITTree[i]
  
        # Move index to parent node in getSum View
        i -= i & (-i)
    return s
  
# Updates a node in Binary Index Tree (BITree) at given index
# in BITree. The given value 'val' is added to BITree[i] and
# all of its ancestors in tree.
def updatebit(BITTree , n , i ,v):
  
    # index in BITree[] is 1 more than the index in arr[]
    i += 1
  
    # Traverse all ancestors and add 'val'
    while i <= n:
  
        # Add 'val' to current node of BI Tree
        BITTree[i] += v
  
        # Update index to that of parent in update View
        i += i & (-i)
  
  
# Constructs and returns a Binary Indexed Tree for given
# array of size n.
def construct(arr, n):
  
    # Create and initialize BITree[] as 0
    BITTree = [0]*(n+1)
  
    # Store the actual values in BITree[] using update()
    for i in range(n):
        updatebit(BITTree, n, i, arr[i])
  
    # Uncomment below lines to see contents of BITree[]
    #for i in range(1,n+1):
    #     print BITTree[i],
    return BITTree

Do not allow duplication in input

Backtrack

def subsets(nums: List[int]) -> List[List[int]]: 
    """
    :param nums: values to select from
    :return: all subsets

    >>> print(subsets([1, 2, 3]))
    [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
    """
    output, cur = [], []

    def backtrack(start):
        output.append(cur[:])

        for i in range(start, len(nums)):
            cur.append(nums[i])
            backtrack(i + 1)
            cur.pop()

    backtrack(0)
    return output

Simple Method

def subsets2(nums: List[int]) -> List[List[int]]: 
    """
    :param nums: values to select from
    :return: all subsets

    >>> print(subsets2([1, 2, 3]))
    [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
    """
    res = [[]]
    for num in nums:
        res.extend([x + [num] for x in res])
    return res

Method using bitmask

def subsets3(nums: List[int]) -> List[List[int]]:
    """
    :param nums: values to select from
    :return: all subsets

    >>> print(subsets3([1, 2, 3]))
    [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
    """
    n = len(nums)
    output = []

    for i in range(2 ** n, 2 ** (n + 1)):
        # generate bitmask, from 0..00 to 1..11
        bitmask = bin(i)[3:]

        # append subset corresponding to that bitmask
        output.append([nums[j] for j in range(n) if bitmask[j] == '1'])

    return output

Allow duplication in input

def subsetsWithDup(nums):
    """
    :param nums: values to select from. Allow duplication
    :return: all unique subsets

    >>> print(subsetsWithDup([1, 2, 3, 3]))
    [[], [3], [3, 3], [2], [2, 3], [2, 3, 3], [1], [1, 3], [1, 3, 3], [1, 2], [1, 2, 3], [1, 2, 3, 3]]
    """
    from collections import Counter
    ct = Counter(nums)

    output, cur = [], []

    items = list(ct.items())

    def backtrack(idx):
        k, v = items[idx]
        for i in range(v + 1):
            cur.extend([k] * i)

            if idx == len(items) - 1:
                output.append(cur[:])

            if idx < len(items) - 1:
                backtrack(idx + 1)

            for _ in range(i):
                cur.pop()

    backtrack(0)
    return output


def combine(nums, k):
    """
    :param nums: values to select from
    :param k: number of values to pick
    :return: combinations with k values from nums

    >>> print(combine([1, 2, 3], 2))
    [[1, 2], [1, 3], [2, 3]]
    >>> print(combine([1, 2, 3, 3], 2))
    [[1, 2], [1, 3], [1, 3], [2, 3], [2, 3], [3, 3]]
    """
    output, cur = [], []

    def backtrack(start):
        if len(cur) == k:
            output.append(cur[:])
            return
        for i in range(start, len(nums) + 1 - k + len(cur)):
            cur.append(nums[i])
            backtrack(i + 1)
            cur.pop()

    backtrack(0)
    return output


def combineUnique(nums, k):
    """

    :param nums: values to select from, may have duplicate
    :param k: number of values to pick
    :return: combinations with k values from nums

    >>> print(combineUnique([1, 2, 3, 3], 2))
    [[3, 3], [2, 3], [1, 3], [1, 2]]
    """
    from collections import Counter
    ct = Counter(nums)

    output, cur = [], []

    items = list(ct.items())

    def backtrack(idx):
        if idx == len(items):
            return
        num, v = items[idx]
        for i in range(min(v + 1, k - len(cur) + 1)):
            cur.extend([num] * i)

            if len(cur) == k:
                output.append(cur[:])

            if len(cur) < k:
                backtrack(idx + 1)

            for _ in range(i):
                cur.pop()

    backtrack(0)
    return output


def combineWithRepetition(nums, k):
    """

    :param nums: values to select from
    :param k: number of values to pick
    :return: combinations with k values from nums. Each value can be selected any number of times

    >>> print(combineWithRepetition([1, 2, 3], 2))
    [[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]
    """
    output, cur = [], []

    def backtrack(start):
        if len(cur) == k:
            output.append(cur[:])
            return
        for i in range(start, len(nums)):
            cur.append(nums[i])
            backtrack(i)
            cur.pop()

    backtrack(0)
    return output

from typing import List


def permute(nums):
    """
    :param nums: values to be permuted
    :return: all permutations
    
    >>> print(permute([1, 2, 3]))
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
    """

    def backtrack(start):
        if start == n:
            output.append(nums[:])
        for i in range(start, n):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]

    n = len(nums)
    output = []
    backtrack(0)
    return output


def permuteUnique(nums):
    """
    :param nums: values to be permuted
    :return: all permutations

    >>> print(permuteUnique([1, 1, 2]))
    [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

    >>> print(permuteUnique([1, 2, 3, 3]))
    [[1, 2, 3, 3], [1, 3, 2, 3], [1, 3, 3, 2], [2, 1, 3, 3], [2, 3, 1, 3], [2, 3, 3, 1], [3, 2, 1, 3], [3, 2, 3, 1], [3, 1, 2, 3], [3, 1, 3, 2], [3, 3, 1, 2], [3, 3, 2, 1]]

    """
    output = []

    def backtrack(start):
        if start == len(nums) - 1:
            output.append(nums[:])
            return

        seen = set()
        for i in range(start, len(nums)):
            if nums[i] in seen:
                continue
            seen.add(nums[i])

            nums[i], nums[start] = nums[start], nums[i]
            backtrack(start + 1)
            nums[i], nums[start] = nums[start], nums[i]

    backtrack(0)
    return output


# Another approach with Counter
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    from collections import Counter
    ct = Counter(nums)
    res = []

    def backtrack(cur, counter):
        if len(cur) == len(nums):
            res.append(cur[:])
            return
        for c, count in counter.items():
            if count == 0:
                continue
            cur.append(c)
            counter[c] -= 1
            backtrack(cur, counter)
            counter[c] += 1
            cur.pop()

    backtrack([], ct)
    return res

int add_no_arithm(int a, int b) { 
    if (b == 0) return a; 
    int sum = a ^ b; // add without carrying 
    int carry = (a & b) << 1; // carry, but don’t add 
    return add_no_arithm(sum, carry); // recurse 
  }

Euclidean algorithm (The time complexity of this algorithm is O(log(min(a, b)))

 def gcd(a, b):
    if a < b:
        a, b = b, a
    while b > 0:
        a, b = b, a % b
    return a

The least common multiple can be found by the following

def lcm(a, b):
    return a * b // gcd(a, b)

Short polling is an AJAX-based timer that calls at fixed delays

Long polling is a technique where the server elects to hold a client’s connection open for as long as possible, delivering a response only after data becomes available or a timeout threshold has been reached. It is based on Comet.

WebSocket is a persistent connection between the client and the server. This is a communications protocol providing full-duplex communication channels over a single TCP connection.

Server Sent Event is a mechanism that allows the server to asynchronously push the data to the client once the client-server connection is established. The server can then decide to send data whenever a new “chunk” of data is available. It can be considered as a one-way publish-subscribe model.

Here are the useful vocabularies in System Design

Concepts

Jitter

Patterns

Circuit Breaker

These numbers are from Designs, Lessons and Advice from Building Large Distributed Systems

Operation	Time
L1 cache reference	0.5 ns
Branch mispredict	5 ns
L2 cache reference	7 ns
Mutex lock/unlock	25 ns
Main memory reference	100 ns
Compress 1K bytes with Zippy	3,000 ns
Send 2K bytes over 1 Gbps network	20,000 ns
Read 1 MB sequentially from memory	250,000 ns
Round trip within same datacenter	500,000 ns
Disk seek	10,000,000 ns
Read 1 MB sequentially from disk	20,000,000 ns
Send packet CA->Netherlands->CA	150,000,000 ns

Design a news feeding system

Design a notification system

Design a web crawler

Design a payment system

Design dropbox

Concepts

Transaction Isolation Levels

This is a collection of good questions and their solutions.

deque

from collections import deque

append(x)
appendleft(x)
pop()
popleft()
clear()
count()
extend(iterable)
extendleft()
remove(val)
reverse()
rotate(n = 1)
maxlen

heapq

import heapq

heappush(h, item)
heappop(h)
heapreplace(h, item)
heapify(h)

bisect

import bisect

bisect(list, val, low=0, high=len(list))
bisect_left(list, val)
insort(list, val)
insort_left(list, val)

binary search tree

from sortedcontainers import SortedList (Similar to multiset in C++)

add(val)
update(iterable)
discard(val)
remove(val)
pop(index=-1)
count(val)
index(val)
bisect_left(val)
bisect_right(val)

from sortedcontainers import SortedDict

pop(key)
popitem(index=-1)
peekitem(index=- 1) (return (key, value) pair at index)

from sortedcontainers import SortedSet

add(val)
pop(index=-1)
remove(val)
discard(val)

Useful Functions

chr(97) = 'a'
ord('a') = 97
map(fun, iterable)
filter(fun, iterable)
reduce(func, iterable)
float('inf')
divmod()
bin()
float.is_integer()
int.bit_length()

Useful Syntax

[f(x) if condition else g(x) for x in sequence]
[f(x) for x in sequence if condition]
[entry for tag in tags for entry in entries if tag in entry]
zeros = [[[0 for _ in range(4)] for _ in range(3)] for _ in range(2)]
zeros = [[0]*M for _ in range(N)]

list

front()
back()
push_front()
pop_front()
push_back()
pop_back()
insert(iter, val)
insert(iter, n, val)
erase()
remove()
unique()
merge()
splice(position, list& x)
splice(position, list& x, first, last)

vector

front()
back()
push_back()
pop_back()
insert()
erase()
emplace(pos, args)
assign()
resize()
shrink_to_fit()

string

push_back(char)
pop_back()
copy(char*, len, pos)
find()
rfind()
substr(pos, len)
compare(str)
npos: maximum value for size_t

unordered_map

find()
count()
insert()
erase(iter)
erase(key_type)

priority_queue

std::priority_queue<int, std::vector<int>, std::greater<int>> (minheap)
std::priority_queue<int> (minheap) (maxheap)

push(val)
pop()
top()
size()
empty()
emplace()

set

insert()
erase(iter)
erase(val)
find()
count()
lower_bound()
upper_bound()

deque

front()
back()
push_back()
push_front()
pop_back()
pop_front()
insert()
erase()

queue

front()
back()
push()
pop()
emplace()

stack

top()
push()
pop()
emplace()

Lambda

[]() {}

[&x]: capture x by ref
[&]: capture all by ref
[=]: capture all by value
[&, x]: x by value, others by ref

Syntax

auto data = std::make_unique<unsigned char[]>(16000);

int *p1 = malloc(4*sizeof(int))
memcpy (str1, str2, sizeof(str2))
char *pBuffer = new char[1024]
delete[] pBuffer

// A 3x4 2D vector of integers, all initialized to 0
std::vector<std::vector<int>> matrix(nrows, std::vector<int>(ncols, 0));

Algorithms

swap(T& a, T& b)
max(T& a, T& b)
min(T& a, T& b)
max_element()
min_element()
sort()
partial_sort()
stable_sort()
all_of()
any_of()
none_of()
for_each()
count()
count_if()
find()
find_if()
find_if_not()
find_end()
search()
copy()
copy_n()
fill()
transform()
iota()
accumulate()
remove()
remove_if()
replace()
replace_if()
reverse()
reverse_copy()
rotate()
unique()
random_shuffle()
partition()
lower_bound()
upper_bound()
merge()
includes()
set_difference()
set_intersection()
set_symmetric_difference()
set_union()
is_heap()
make_heap()
push_heap()
pop_heap()
sort_heap()
is_permutation()
next_permutation()
prev_permutation()
partial_sum()
adjacent_difference()
exclusive_scan()
inner_product()
lexicographical_compare()

Series of Questions

Implement a Calculator

Buy and sell stock

Merge Intervals

Jump Game

4. Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

A Python solution using Binary search

class Solution: 
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: 
        if len(nums1) < len(nums2): 
            nums1, nums2 = nums2, nums1 
        m, n = len(nums1), len(nums2) 
        sum_length = m + n 
        is_odd = sum_length % 2 == 1 
        target = (sum_length + 1) // 2 
        low = target - n  # The minimum number of elements from array 1 in the first half 
        high = target  # The maximum number of elements from array 1 in the first half 
        while low <= high: 
            num1_in_half = (low + high) // 2  # Number of elements from array 1 in the first half 
            num2_in_half = target - num1_in_half 
            if num1_in_half > 0 and num2_in_half < n and nums1[num1_in_half - 1] > nums2[num2_in_half]: 
                high = num1_in_half - 1 
            elif num2_in_half > 0 and num1_in_half < m and nums2[num2_in_half - 1] > nums1[num1_in_half]: 
                low = num1_in_half + 1 
            else: 
                if num2_in_half == 0: 
                    leftmax = nums1[num1_in_half - 1] 
                elif num1_in_half == 0: 
                    leftmax = nums2[num2_in_half - 1] 
                else: 
                    leftmax = max(nums1[num1_in_half - 1], nums2[num2_in_half - 1]) 
                if is_odd: 
                    return leftmax 
                if num1_in_half == m: 
                    rightmin = nums2[num2_in_half] 
                elif num2_in_half == n: 
                    rightmin = nums1[num1_in_half] 
                else: 
                    rightmin = min(nums1[num1_in_half], nums2[num2_in_half]) 
                return (leftmax + rightmin) / 2

A C++ solution with different idea

int findMedian_logn(int vec1[], int n1, int vec2[], int n2) 
{ 
    int m1 = (n1-1) / 2, m2 = (n2-1) / 2; 
    if(n1 == 1) 
    {
        if(n2 == 1) 
            return vec1[0] < vec2[0] ? vec1[0] : vec2[0]; 
        if(n2 % 2 == 0) 
        { 
            if(vec1[0] >= vec2[m2+1]) 
                return vec2[m2+1]; 
            else if(vec1[0] <= vec2[m2]) 
                return vec2[m2]; 
            else return vec1[0]; 
        } 
        else 
        { 
            if(vec1[0] >= vec2[m2]) 
                return vec2[m2]; 
            else if(vec1[0] <= vec2[m2-1]) 
                return vec2[m2-1]; 
            else return vec1[0]; 
        } 
    } 
    else if(n2 == 1) 
    {
        if(n1 % 2 == 0) 
        { 
            if(vec2[0] >= vec1[m1+1]) 
                return vec1[m1+1]; 
            else if(vec2[0] <= vec1[m1]) 
                return vec1[m1]; 
            else return vec2[0]; 
        } 
        else 
        { 
            if(vec2[0] >= vec1[m1]) 
                return vec1[m1]; 
            else if(vec2[0] <= vec1[m1-1]) 
                return vec1[m1-1]; 
            else return vec2[0]; 
        } 
    } 
    else 
    { 
        int cutLen = n1/2 > n2/2 ? n2/2 : n1/2;
        if(vec1[m1] == vec2[m2])return vec1[m1]; 
        else if(vec1[m1] < vec2[m2]) 
            return findMedian_logn(&vec1[cutLen], n1-cutLen, vec2, n2-cutLen); 
        else 
            return findMedian_logn(vec1, n1-cutLen, &vec2[cutLen], n2-cutLen); 
    } 
}

11. Container With Most Water

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

def maxArea(self, height): 
    res = 0  
    x = len(height) - 1 
    y = 0 
    while x != y: 
        if height[x] > height[y]: 
            area = height[y] * (x - y) 
            y += 1 
        else: 
            area = height[x] * (x - y) 
            x -= 1 
        res = max(res, area) 
    return res

18. 4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

class Solution: 
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]: 
        nums.sort() 
         
        def kSum(nums, start, target, k): 
            if nums[0] * k > target or nums[-1] * k < target: 
                return [] 
            res = [] 
             
            if k == 2: 
                return twoSum(nums, start, target) 
             
            for i in range(start, len(nums) - k + 1): 
                if i > start and nums[i] == nums[i - 1]: 
                    continue 
                for x in kSum(nums, i + 1, target - nums[i], k - 1): 
                    res.append([nums[i]] + x) 
            return res 
                 
        def twoSum(nums, start, target): 
            low = start 
            high = len(nums) - 1 
            res = [] 
            while low < high: 
                s = nums[low] + nums[high] 
                if s < target or (low != start and nums[low] == nums[low - 1]): 
                    low += 1 
                elif s > target or (high != len(nums) - 1 and nums[high] == nums[high + 1]): 
                    high -= 1 
                else: 
                    res.append(([nums[low], nums[high]])) 
                    low += 1 
                    high -= 1 
            return res 
         
        return kSum(nums, 0, target, 4)

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

def generateParenthesis(self, n: int) -> List[str]: 
    ans = [] 
    def backtrack(s, left, right): 
        if left == right == n: 
            ans.append(s) 
            return 
            
        if left < n: 
            backtrack(s + '(', left + 1, right) 
            
        if left > right: 
            backtrack(s + ')', left, right + 1) 
            
    backtrack('', 0, 0) 
            
    return ans

32. Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

def longestValidParentheses(self, s: str) -> int:
    from collections import deque
    q = deque()
    longest = 0
    
    q.append(-1)

    for i, c in enumerate(s):
        if c == '(':
            q.append(i)
        else:
            q.pop()
            if not q:
                q.append(i)
            else:
                longest = max(i - q[-1], longest)
                
    return longest

Another simpler idea. Scan from left and then scan from right.

def longestValidParentheses(self, s: str) -> int: 
    m = left = right = 0 
    for i in s: 
        if i == '(': 
            left += 1 
        else: 
            right += 1 
        if left == right: 
            m = max(m, right + left) 
        elif right > left: 
            left = right = 0 

    left = right = 0 
    for i in s[::-1]: 
        if i == ')': 
            right += 1 
        else: 
            left += 1 
        if left == right: 
            m = max(m, right + left) 
        elif left > right: 
            left = right = 0 
    return m

33. Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array.

class Solution: 
    def search(self, nums: List[int], target: int) -> int: 
        start, end = 0, len(nums) - 1 
        while start <= end: 
            mid = start + (end - start) // 2 
            if nums[mid] == target: 
                return mid 
            elif nums[mid] >= nums[start]: 
                if target >= nums[start] and target < nums[mid]: 
                    end = mid - 1 
                else: 
                    start = mid + 1 
            else: 
                if target <= nums[end] and target > nums[mid]: 
                    start = mid + 1 
                else: 
                    end = mid - 1 
        return -1

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

def maxSubArray(self, nums: 'List[int]') -> 'int': 
    n = len(nums) 
    curr_sum = max_sum = nums[0] 
    for i in range(1, n): 
        curr_sum = max(nums[i], curr_sum + nums[i]) 
        max_sum = max(max_sum, curr_sum) 
            
    return max_sum

55. Jump Game

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

public class Solution { 
    public boolean canJump(int[] nums) { 
        int lastPos = nums.length - 1; 
        for (int i = nums.length - 1; i >= 0; i--) { 
            if (i + nums[i] >= lastPos) { 
                lastPos = i; 
            } 
        } 
        return lastPos == 0; 
    } 
}

75. Sort Colors

Given an array nums 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.

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

You must solve this problem without using the library's sort function. Use one-pass only.

Double quick sort

class Solution: 
    def sortColors(self, nums: List[int]) -> None: 
        left = 0 
        right = len(nums) - 1 
         
        i = 0 
        while i <= right: 
            if nums[i] == 0: 
                nums[i], nums[left] = nums[left], nums[i] 
                left += 1 
                i += 1 
            elif nums[i] == 2: 
                nums[i], nums[right] = nums[right], nums[i] 
                right -= 1 
            else: 
                i += 1

81. Search in Rotated Sorted Array II

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

def search(self, nums: List[int], target: int) -> bool: 
    low = 0 
    high = len(nums) - 1 
     
    while low <= high: 
        mid = low + (high - low) // 2 
        if nums[mid] == target: 
            return True 
         
        if nums[mid] == nums[low] == nums[high]: 
            low += 1 
            high -= 1 
         
        elif nums[mid] >= nums[low]: 
            if nums[low] <= target < nums[mid]: 
                high = mid - 1 
            else: 
                low = mid + 1 
         
        else: 
            if nums[mid] < target <= nums[high]: 
                low = mid + 1 
            else: 
                high = mid - 1 
                 
    return False

84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

class Solution: 
    def largestRectangleArea(self, heights: List[int]) -> int: 
        stack = [-1] # Record the last index that is smaller 
        heights += [-1] # Add it to clear out the stack at the end 
        area = 0 
         
        for i, height in enumerate(heights):  
            # When it is equal, still need to update because you want the "last" index that is smaller than the current 
            while (stack[-1] != -1 and heights[stack[-1]] >= height): 
                idx = stack.pop() 
                area = max(area, (i - stack[-1] - 1) * heights[idx]) 
             
            stack.append(i) 
        return area

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: 
    """ 
    Do not return anything, modify nums1 in-place instead. 
    """ 
    p1 = m - 1 
    p2 = n - 1 
    p = m + n - 1 
        
    while p >= 0: 
        if p2 == -1 or (p1 >= 0 and nums1[p1] >= nums2[p2]): 
            nums1[p] = nums1[p1] 
            p1 -= 1 
        else: 
            nums1[p] = nums2[p2] 
            p2 -= 1
        p -= 1

128. Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time.

def longestConsecutive(self, nums):
    nums = set(nums)
    best = 0
    for x in nums:
        if x - 1 not in nums:
            y = x + 1
            while y in nums:
                y += 1
            best = max(best, y - x)
    return best

class Node:
    def __init__(self, val):
        self.val = val
        self.parent = self
        self.size = 1
    
class UnionFind:
        
    def find(self, node):
        if node.parent != node:
            node.parent = self.find(node.parent)
        return node.parent
    
    def union(self, node1, node2):
        parent_1 = self.find(node1)
        parent_2 = self.find(node2)
        if parent_1 != parent_2:
            parent_2.parent = parent_1
            parent_1.size += parent_2.size
        return parent_1.size
        
        
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        uf = UnionFind()
        nodes = {}
        max_size = 0
        for num in nums:
            if num not in nodes:
                node = Node(num)
                nodes[num] = node
                size = 1
                if num + 1 in nodes:
                    size = uf.union(node, nodes[num+1])
                if num - 1 in nodes:
                    size = uf.union(node, nodes[num-1])
                max_size = max(max_size, size)
                
        return max_size

135. Candy

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children.

def candy(self, ratings: List[int]) -> int: 
    N = len(ratings) 
        
    leftArray = [1] * N 
        
    for i in range(1, N): 
        if ratings[i] > ratings[i - 1]: 
            leftArray[i] = leftArray[i - 1] + 1 
        
    for i in range(N - 2, -1, -1): 
        if ratings[i] > ratings[i + 1]: 
            leftArray[i] = max(leftArray[i], leftArray[i + 1] + 1) 
                
    return sum(leftArray)

152. Maximum Product Subarray

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

def maxProduct(self, nums: List[int]) -> int: 
    curmin = curmax = ans = nums[0] 
        
    for num in nums[1:]: 
        # If num is zero, the following will set everything to zero 
        t = (num, num * curmin, num * curmax) 
        curmin = min(t) 
        curmax = max(t) 
            
        ans = max(ans, curmax) 
        
    return ans

162. Find Peak Element

A peak element is an element that is strictly greater than its neighbors. Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. You may imagine that nums[-1] = nums[n] = -∞. You must write an algorithm that runs in O(log n) time.

def findPeakElement(self, nums: List[int]) -> int:
    low = 0
    high = len(nums) - 1
    
    while low < high:
        mid = low + (high - low) // 2
        if nums[mid] > nums[mid + 1]:
            high = mid
        else:
            low = mid + 1
        
    return low

167. Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

def twoSum(self, numbers: List[int], target: int) -> List[int]:
    i, j = 0, len(numbers) - 1
    while i < j:
        s = numbers[i] + numbers[j]
        if s == target:
            return [i + 1, j + 1]
        elif s < target:
            i += 1
        else:
            j -= 1

215. Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Quick select

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:          
        def partition(start, end):
            # Add some randomization
            idx = randint(start, end)
            nums[idx], nums[start] = nums[start], nums[idx]

            pivot = start
            pivot_value = nums[start]
            for i in range(start + 1, end + 1): # It is the same whether you start from "start" or "start + 1"
                if nums[i] < pivot_value:
                    pivot += 1
                    nums[i], nums[pivot] = nums[pivot], nums[i]

            nums[start], nums[pivot] = nums[pivot], nums[start]
            return pivot # Pivot is also the same as the number of elements smaller than the pivot element
        
        def kthSmallest(start, end, k):  # k start from 1
            pivot = partition(start, end)
            if pivot - start == k - 1:
                return nums[pivot]
            elif pivot - start > k - 1:
                return kthSmallest(start, pivot - 1, k)
            else:
                return kthSmallest(pivot + 1, end, k - pivot - 1 + start)

        return kthSmallest(0, len(nums) - 1, len(nums) + 1 - k)

225. Implement Stack using Queues

Two queues

class MyStack: 
    def __init__(self):
        self.primary = collections.deque() 
        self.secondary = collections.deque() 
        self._top = None 
         
    def _swap(self):
        self.primary, self.secondary = self.secondary, self.primary 
         
    def push(self, x: int) -> None:
        self.primary.append(x)
        self._top = x 

    def pop(self) -> int:
        self._top = None 
        while len(self.primary) > 1: 
            if len(self.primary) == 2: 
                self._top = self.primary[0] 
            self.secondary.append(self.primary.popleft()) 
        self._swap() 
        return self.secondary.popleft()

    def top(self) -> int:
        return self._top

    def empty(self) -> bool:
        return not self.primary

One queue

class MyStack: 
    def __init__(self): 
        self.q = collections.deque() 
         
    def push(self, x: int) -> None: 
        self.q.append(x) 
        N = len(self.q) 
        for i in range(N - 1): 
            self.q.append(self.q.popleft())

    def pop(self) -> int: 
        return self.q.popleft()     
        
    def top(self) -> int: 
        return self.q[0]

    def empty(self) -> bool: 
        return len(self.q) == 0

232. Implement Queue using Stacks

class MyQueue: 
    def __init__(self): 
        self.primary = [] 
        self.secondary = [] 
        self._front = None 
         
    def push(self, x: int) -> None: 
        self.primary.append(x)

    def pop(self) -> int: 
        self.peek() 
        return self.secondary.pop() 
     
    def peek(self) -> int: 
        if not self.secondary: 
            while self.primary: 
                self.secondary.append(self.primary.pop()) 
        return self.secondary[-1] 
        
    def empty(self) -> bool: 
        return not self.primary and not self.secondary

239. Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

from collections import deque 
class Solution: 
    def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]': 
        # base cases 
        n = len(nums) 
        if n * k == 0: 
            return [] 
        if k == 1: 
            return nums 
         
        def clean_deque(i): 
            # remove indexes of elements not from sliding window 
            if deq and deq[0] == i - k: 
                deq.popleft() 
                 
            # remove from deq indexes of all elements  
            # which are smaller than current element nums[i] 
            while deq and nums[i] > nums[deq[-1]]: 
                deq.pop() 
         
        # init deque and output 
        deq = deque() 
        max_idx = 0 
        for i in range(k): 
            clean_deque(i) 
            deq.append(i) 
            # compute max in nums[:k] 
            if nums[i] > nums[max_idx]: 
                max_idx = i 
        output = [nums[max_idx]] 
         
        # build output 
        for i in range(k, n): 
            clean_deque(i)           
            deq.append(i) 
            output.append(nums[deq[0]]) 
        return output

class Solution: 
    def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]': 
        n = len(nums) 
        if n * k == 0: 
            return [] 
        if k == 1: 
            return nums 
         
        left = [0] * n 
        left[0] = nums[0] 
        right = [0] * n 
        right[n - 1] = nums[n - 1] 
        for i in range(1, n): 
            # from left to right 
            if i % k == 0: 
                # block start 
                left[i] = nums[i] 
            else: 
                left[i] = max(left[i - 1], nums[i]) 
            # from right to left 
            j = n - i - 1 
            if (j + 1) % k == 0: 
                # block end 
                right[j] = nums[j] 
            else: 
                right[j] = max(right[j + 1], nums[j]) 
         
        output = [] 
        for i in range(n - k + 1): 
            output.append(max(left[i + k - 1], right[i])) 
             
        return output

295. Find Median from Data Stream

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.

from heapq import heappop, heappush 

class MedianFinder: 
    def __init__(self): 
        """ 
        initialize your data structure here. 
        """ 
        self._low =  [] # maxheap, allow to have one extra element
        self._high = [] # minheap 
        self._median = None
    
    def low_to_high(self):
        heappush(self._high, -heappop(self._low))

    def high_to_low(self):
        heappush(self._low, -heappop(self._high))

    def balance(self):
        if (len(self._low) > len(self._high) + 1):
            self.low_to_high()
        elif len(self._high) > len(self._low):
            self.high_to_low()

    def addNum(self, num: int) -> None: 
        heappush(self._low, -num)
        if len(self._high) > 0 and -self._low[0] > self._high[0]: 
            self.low_to_high()
        self.balance()

    def findMedian(self) -> float: 
        if len(self._low) > len(self._high): 
            return -self._low[0] 
        else: 
            return (-self._low[0] + self._high[0]) / 2

300. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

def lengthOfLIS(self, nums: List[int]) -> int: 
    trail = [] 
    for num in nums: 
        i = bisect_left(trail, num) 
        if i == len(trail): 
            trail.append(num) 
        else: 
            trail[i] = num 
    return len(trail)

301. Remove Invalid Parentheses

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid. Return all the possible results. You may return the answer in any order.

def removeInvalidParentheses(self, s: str) -> List[str]: 
    score = collections.defaultdict(int) 
    score['('], score[')'] = 1, -1 
     
    def findNumberToRemove(s): 
        cum = 0 
        lowest = 0 
        for c in s: 
            cum += score[c] 
            lowest = min(lowest, cum) 
        return cum + abs(lowest), abs(lowest) 
     
    curstr = [] 
    curscore = 0 
    res = set() 
     
    leftmax, rightmax = findNumberToRemove(s) 
     
    def backtrack(start):     
        nonlocal curscore, leftmax, rightmax 
        if curscore < 0: 
            return 
         
        if start == len(s): 
            if leftmax == rightmax == 0: 
                res.add(''.join(curstr)) 
            return 
         
        c = s[start] 
        if c == '(' and leftmax > 0: 
            leftmax -= 1 
            backtrack(start + 1) 
            leftmax += 1 
             
        if c == ')' and rightmax > 0: 
            rightmax -= 1 
            backtrack(start + 1) 
            rightmax += 1 
             
        curstr.append(c) 
        curscore += score[c] 
        backtrack(start + 1) 
        curstr.pop() 
        curscore -= score[c] 
         
    backtrack(0) 
    return list(res)

315. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Merge Sort

def countSmaller(self, nums: List[int]) -> List[int]:
    res = [0] * len(nums)
    
    array = list(zip(nums, range(len(nums))))
    
    def mergeSort(arr, left, right):
        if left == right:
            return
        
        mid = left + (right - left) // 2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid + 1, right)
        merge(arr, left, mid, right)
        
    def merge(arr, left, mid, right):
        i = left
        j = mid + 1
        
        tmp = []
        
        while i <= mid or j <= right:
            if j > right or (i <= mid and arr[i][0] <= arr[j][0]):
                tmp.append(arr[i])
                res[arr[i][1]] += j - mid - 1
                i += 1
            else:
                tmp.append(arr[j])
                j += 1
                
        arr[left:right + 1] = tmp
        
    mergeSort(array, 0, len(nums) - 1)
    return res

Segment Tree

def countSmaller(self, nums: List[int]) -> List[int]: 
    # implement segment tree 
    def update(index, value, tree, size): 
        index += size  # shift the index to the leaf 
        # update from leaf to root 
        tree[index] += value 
        while index > 1: 
            index //= 2 
            tree[index] = tree[index * 2] + tree[index * 2 + 1] 
    def query(left, right, tree, size): 
        # return sum of [left, right) 
        result = 0 
        left += size  # shift the index to the leaf 
        right += size 
        while left < right: 
            # if left is a right node 
            # bring the value and move to parent's right node 
            if left % 2 == 1: 
                result += tree[left] 
                left += 1 
            # else directly move to parent 
            left //= 2 
            # if right is a right node 
            # bring the value of the left node and move to parent 
            if right % 2 == 1: 
                right -= 1 
                result += tree[right] 
            # else directly move to parent 
            right //= 2 
        return result 
    offset = 10**4  # offset negative to non-negative 
    size = 2 * 10**4 + 1  # total possible values in nums 
    tree = [0] * (2 * size) 
    result = [] 
    for num in reversed(nums): 
        smaller_count = query(0, num + offset, tree, size) 
        result.append(smaller_count) 
        update(num + offset, 1, tree, size) 
    return reversed(result)

Binary Index Tree

def countSmaller(self, nums: List[int]) -> List[int]: 
    # implement Binary Index Tree 
    def update(index, value, tree, size): 
        index += 1  # index in BIT is 1 more than the original index 
        while index < size: 
            tree[index] += value 
            index += index & -index 
    def query(index, tree): 
        # return sum of [0, index) 
        result = 0 
        while index >= 1: 
            result += tree[index] 
            index -= index & -index 
        return result 
    offset = 10**4  # offset negative to non-negative 
    size = 2 * 10**4 + 2  # total possible values in nums plus one dummy 
    tree = [0] * size 
    result = [] 
    for num in reversed(nums): 
        smaller_count = query(num + offset, tree) 
        result.append(smaller_count) 
        update(num + offset, 1, tree, size) 
    return reversed(result)

316. Remove Duplicate Letters

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

def removeDuplicateLetters(self, s: str) -> str: 
    ct = collections.Counter(s)              
    stack = [] 
    seen = set() 
     
    for i, c in enumerate(s): 
        if c in seen: 
            ct[c] -= 1 
            continue 
        while stack and s[stack[-1]] >= c and ct[s[stack[-1]]] > 1: 
            idx = stack.pop() 
            seen.remove(s[idx]) 
            ct[s[idx]] -= 1 
        stack.append(i) 
        seen.add(c) 
         
    return ''.join([s[i] for i in stack])

341. Flatten Nested List Iterator

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it. Implement the NestedIterator class:

NestedIterator(List nestedList) Initializes the iterator with the nested list nestedList. int next() Returns the next integer in the nested list. boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Stack solution

class NestedIterator: 
     
    def __init__(self, nestedList: [NestedInteger]): 
        self.stack = list(reversed(nestedList)) 
         
         
    def next(self) -> int: 
        self.make_stack_top_an_integer() 
        return self.stack.pop().getInteger() 
     
         
    def hasNext(self) -> bool: 
        self.make_stack_top_an_integer() 
        return len(self.stack) > 0 
         
         
    def make_stack_top_an_integer(self): 
        # While the stack contains a nested list at the top... 
        while self.stack and not self.stack[-1].isInteger(): 
            # Unpack the list at the top by putting its items onto 
            # the stack in reverse order. 
            self.stack.extend(reversed(self.stack.pop().getList()))

Recursive solution:

class NestedIterator: 
     
    def __init__(self, nestedList: [NestedInteger]): 
        def flatten_list(nested_list): 
            for nested_integer in nested_list: 
                if nested_integer.isInteger(): 
                    self._integers.append(nested_integer.getInteger()) 
                else: 
                    flatten_list(nested_integer.getList())  
        self._integers = [] 
        self._position = -1 # Pointer to previous returned. 
        flatten_list(nestedList) 
     
    def next(self) -> int: 
        self._position += 1 
        return self._integers[self._position] 
         
    def hasNext(self) -> bool: 
        return self._position + 1 < len(self._integers)

Two stacks to keep index:

class NestedIterator: 
     
    def __init__(self, nestedList: [NestedInteger]): 
        self.stack = [[nestedList, 0]] 
         
    def make_stack_top_an_integer(self): 
         
        while self.stack: 
             
            # Essential for readability :) 
            current_list = self.stack[-1][0] 
            current_index = self.stack[-1][1] 
             
            # If the top list is used up, pop it and its index. 
            if len(current_list) == current_index: 
                self.stack.pop() 
                continue 
             
            # Otherwise, if it's already an integer, we don't need  
            # to do anything. 
            if current_list[current_index].isInteger(): 
                break 
             
            # Otherwise, it must be a list. We need to increment the index 
            # on the previous list, and add the new list. 
            new_list = current_list[current_index].getList() 
            self.stack[-1][1] += 1 # Increment old. 
            self.stack.append([new_list, 0]) 
             
     
    def next(self) -> int: 
        self.make_stack_top_an_integer() 
        current_list = self.stack[-1][0] 
        current_index = self.stack[-1][1] 
        self.stack[-1][1] += 1 
        return current_list[current_index].getInteger() 
         
     
    def hasNext(self) -> bool: 
        self.make_stack_top_an_integer() 
        return len(self.stack) > 0

347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Use bucket to search

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    from itertools import chain
    ct = collections.Counter(nums)
    m = max(ct.values())
    hold = [[] for _ in range(m)]
    for kk, v in ct.items():
        hold[v - 1].append(kk)
    return list(chain(*hold))[::-1][:k]

Quick select

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    count = collections.Counter(nums)
    unique = list(count.keys())
    
    def partition(left, right, pivot_index) -> int:
        pivot_frequency = count[unique[pivot_index]]
        unique[pivot_index], unique[right] = unique[right], unique[pivot_index]  
        
        store_index = left
        for i in range(left, right):
            if count[unique[i]] < pivot_frequency:
                unique[store_index], unique[i] = unique[i], unique[store_index]
                store_index += 1

        unique[right], unique[store_index] = unique[store_index], unique[right]  
        
        return store_index
    
    def quickselect(left, right, k_smallest) -> None:
        """
        Sort a list within left..right till kth less frequent element
        takes its place. 
        """
        # base case: the list contains only one element
        if left == right: 
            return
        
        # select a random pivot_index
        pivot_index = random.randint(left, right)     
                        
        # find the pivot position in a sorted list   
        pivot_index = partition(left, right, pivot_index)
        
        # if the pivot is in its final sorted position
        if k_smallest == pivot_index:
                return 
        # go left
        elif k_smallest < pivot_index:
            quickselect(left, pivot_index - 1, k_smallest)
        # go right
        else:
            quickselect(pivot_index + 1, right, k_smallest)
        
    n = len(unique) 
    # kth top frequent element is (n - k)th less frequent.
    # Do a partial sort: from less frequent to the most frequent, till
    # (n - k)th less frequent element takes its place (n - k) in a sorted array. 
    # All element on the left are less frequent.
    # All the elements on the right are more frequent.  
    quickselect(0, n - 1, n - k)
    # Return top k frequent elements
    return unique[n - k:]

363. Max Sum of Rectangle No Larger Than K

Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

class Solution { 
public: 
    int result = INT_MIN; 
    void updateResult(vector<int>& nums, int k) { 
        int sum = 0; 
        // Container to store sorted prefix sums. 
        set<int> sortedSum; 
        set<int>::iterator it; 
        // Add 0 as the prefix sum for an empty sub-array. 
        sortedSum.insert(0); 
        for (int& num : nums) { 
            // Running Sum. 
            sum += num; 
            // Get X where Running sum - X <= k such that sum - X is closest to k. 
            it = sortedSum.lower_bound(sum - k); 
            // If such X is found in the prefix sums. 
            // Get the sum of that sub array and update the global maximum resul. 
            if (it != sortedSum.end()) 
                result = max(result, sum - *it); 
            // Insert the current running sum to the prefix sums container. 
            sortedSum.insert(sum); 
        } 
    } 
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { 
        // Stores the 1D representation of the matrix. 
        vector<int> rowSum(matrix[0].size()); 
        for (int i = 0; i < matrix.size(); i++) { 
            // Initialize the 1D representation with 0s. 
            fill(rowSum.begin(), rowSum.end(), 0); 
            // We convert the matrix between rows i..row inclusive to 1D array 
            for (int row = i; row < matrix.size(); row++) { 
                // Add the current row to the previous row. 
                // This converts the matrix between i..row to 1D array 
                for (int col = 0; col < matrix[0].size(); col++) 
                    rowSum[col] += matrix[row][col]; 
                // Run the 1D algorithm for `rowSum` 
                updateResult(rowSum, k); 
                // If result is k, this is the best possible answer, so return. 
                if (result == k) 
                    return result; 
            } 
        } 
        return result; 
    } 
};

class Solution: 
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int: 
        res = -float('inf') 
         
        def update(arr): 
            nonlocal res 
            from bisect import bisect_left, bisect_right, insort 
            prefix_sum = [0] 
            sum_ = 0 
            for v in arr: 
                sum_ += v 
                idx = bisect_left(prefix_sum, sum_ - k) 
                 
                if idx < len(prefix_sum): 
                    res = max(res, sum_ - prefix_sum[idx]) 
                 
                insort(prefix_sum, sum_) 
                             
        m, n = len(matrix), len(matrix[0]) 
         
        for i in range(m): 
            rowsum = [0] * n 
             
            for i2 in range(i, m): 
                for j in range(n): 
                    rowsum[j] += matrix[i2][j] 
                update(rowsum) 
                 
                if res == k: 
                    return k 
                     
        return res

402. Remove K Digits

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        st = []
        for n in num:
            while st and k and st[-1] > n:
                st.pop()
                k -= 1
            
            if st or n is not '0': # prevent leading zeros
                st.append(n)
                
        if k: # not fully spent
            st = st[0:-k]
            
        return ''.join(st) or '0'

435. Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

def eraseOverlapIntervals(self, intervals):
    end = float('-inf')
    erased = 0
    for i in sorted(intervals, key=lambda i: i.end):
        if i.start >= end:
            end = i.end
        else:
            erased += 1
    return erased

484. Find Permutation

By now, you are given a secret signature consisting of character 'D' and 'I'. 'D' represents a decreasing relationship between two numbers, 'I' represents an increasing relationship between two numbers. And our secret signature was constructed by a special integer array, which contains uniquely all the different number from 1 to n (n is the length of the secret signature plus 1). For example, the secret signature "DI" can be constructed by array [2,1,3] or [3,1,2], but won't be constructed by array [3,2,4] or [2,1,3,4], which are both illegal constructing special string that can't represent the "DI" secret signature. On the other hand, now your job is to find the lexicographically smallest permutation of [1, 2, ... n] could refer to the given secret signature in the input.

public class Solution {
    public int[] findPermutation(String s) {
        int[] res = new int[s.length() + 1];
        Stack < Integer > stack = new Stack < > ();
        int j = 0;
        for (int i = 1; i <= s.length(); i++) {
            if (s.charAt(i - 1) == 'I') {
                stack.push(i);
                while (!stack.isEmpty())
                    res[j++] = stack.pop();
            } else
                stack.push(i);
        }
        stack.push(s.length() + 1);
        while (!stack.isEmpty())
            res[j++] = stack.pop();
        return res;
    }
}

554. Brick Wall

There is a rectangular brick wall in front of you with n rows of bricks. The ith row has some number of bricks each of the same height (i.e., one unit) but they can be of different widths. The total width of each row is the same.

Draw a vertical line from the top to the bottom and cross the least bricks. If your line goes through the edge of a brick, then the brick is not considered as crossed. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Given the 2D array wall that contains the information about the wall, return the minimum number of crossed bricks after drawing such a vertical line.

def leastBricks(self, wall: List[List[int]]) -> int:
    edgecut = collections.defaultdict(int)
    
    for w in wall:
        pos = 0
        for i in range(len(w) - 1):
            pos += w[i]
            edgecut[pos] += 1
    
    return len(wall) - max(edgecut.values(), default=0)

581. Shortest Unsorted Continuous Subarray

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the shortest such subarray and output its length.


def findUnsortedSubarray(self, nums: list[int]) -> int:
    max_so_far = nums[:]
    for i in range(1, len(nums)):
        max_so_far[i] = max(max_so_far[i - 1], nums[i])

    min_so_far = nums[:]
    for i in range(len(nums) - 2, -1, -1):
        min_so_far[i] = min(min_so_far[i + 1], nums[i])

    i = -1
    while i + 1 < len(nums) and max_so_far[i + 1] == min_so_far[i + 1]:
        i += 1

    j = len(nums)
    while j - 1 >= 0 and max_so_far[j - 1] == min_so_far[j - 1]:
        j -= 1

    return max(0, j - i - 1)

658. Find K Closest Elements

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

|a - x| < |b - x|, or
|a - x| == |b - x| and a < b

def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]: 
    left = 0 
    right = len(arr) - k 
     
    while left < right: 
        mid = left + (right - left) // 2 
        if x - arr[mid] > arr[mid + k] - x: # Think about middle point. I am comparing mid and mid + k because both cannot be in the result
            left = mid + 1 
        else: 
            right = mid 
    return arr[left : left + k]

670. Maximum Swap

You are given an integer num. You can swap two digits at most once to get the maximum valued number. Return the maximum valued number you can get.

def maximumSwap(self, num: int) -> int:
    s = list(str(num))
    
    m = -1
    idx = -1
    replace = None
    for i in range(len(s) - 1, -1, -1):
        if int(s[i]) > m:
            m = int(s[i])
            idx = i
        elif int(s[i]) < m:
            replace = i, idx
    
    if not replace:
        return num
    
    i, idx = replace
    s[i], s[idx] = s[idx], s[i]
    
    return int(''.join(s))

696. Count Binary Substrings

Given a binary string s, return the number of non-empty substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

class Solution(object): 
    def countBinarySubstrings(self, s): 
        groups = [1] 
        for i in xrange(1, len(s)): 
            if s[i-1] != s[i]: 
                groups.append(1) 
            else: 
                groups[-1] += 1 
        ans = 0 
        for i in xrange(1, len(groups)): 
            ans += min(groups[i-1], groups[i]) 
        return ans

895. Maximum Frequency Stack

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:

FreqStack() constructs an empty frequency stack.
void push(int val) pushes an integer val onto the top of the stack.
int pop() removes and returns the most frequent element in the stack.
- If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

Dictionary of List

class FreqStack(object): 
    def __init__(self): 
        self.freq = collections.Counter() 
        self.group = collections.defaultdict(list) 
        self.maxfreq = 0

    def push(self, x): 
        f = self.freq[x] + 1 
        self.freq[x] = f 
        if f > self.maxfreq: 
            self.maxfreq = f 
        self.group[f].append(x)

    def pop(self): 
        x = self.group[self.maxfreq].pop() 
        self.freq[x] -= 1 
        if not self.group[self.maxfreq]: 
            self.maxfreq -= 1 
        return x

Use a timer

class FreqStack: 
    def __init__(self): 
        self.h = [] 
        self.timer = 0 
        self.freq = collections.defaultdict(int) 

    def push(self, val: int) -> None: 
        self.freq[val] += 1 
        heappush(self.h, (-self.freq[val], -self.timer, val)) 
        self.timer += 1 
        
    def pop(self) -> int: 
        _, _, val = heappop(self.h) 
        self.freq[val] -= 1 
        return val

992. Subarrays with K Different Integers

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K. (For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.) Return the number of good subarrays of A.

from collections import Counter
class Solution:
    # This solution requires "atMost". If the usual sliding windows method is used, you will find that the "left" pointer will move in both directions, which is not the idea for sliding windows
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        def atMost(K):
            ct = Counter()
            countDiff = 0
            res = i = 0
            for j in range(len(A)):
                ct[A[j]] += 1
                if ct[A[j]] == 1:
                    countDiff += 1

                while countDiff > K:
                    ct[A[i]] -= 1
                    if ct[A[i]] == 0:
                        countDiff -= 1
                    i += 1
                res += j - i + 1
            
            return res
        
        return atMost(K) - atMost(K-1)

1004. Max Consecutive Ones III

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

    def longestOnes(self, nums: List[int], k: int) -> int: 
        N = len(nums) 
        nZeros = 0 
        i = 0  
        res = 0 
         
        for j in range(N): 
            nZeros += (nums[j]) == 0 
            while nZeros > k: 
                nZeros -= (nums[i] == 0) 
                i += 1 
            res = max(j - i + 1, res) 
             
        return res

A harder to understand version

    def longestOnes(self, nums: List[int], k: int) -> int: 
        N = len(nums) 
        nZeros = 0 
        i = 0 
        res = 0 
         
        for j in range(N): 
            nZeros += (nums[j]) == 0 
            if nZeros > k: 
                nZeros -= (nums[i] == 0) 
                i += 1 
        return j - i + 1

1235. Maximum Profit in Job Scheduling

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i]. You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range. If you choose a job that ends at time X you will be able to start another job that starts at time X.

Sort by start time

def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int: 
    from collections import deque 
    from bisect import bisect_left, bisect_right 
        
    events = sorted(zip(startTime, endTime, profit)) 
        
    dp = deque() 
    dp.appendleft((float('inf'), 0)) 
        
    for i in range(len(events) - 1, -1, -1): 
        start, end, profit = events[i] 
            
        idx = bisect_left(dp, (end, -float('inf'))) 
        if dp[idx][1] + profit > dp[0][1]: 
            dp.appendleft((start, dp[idx][1] + profit)) 
                            
    return dp[0][1]

Sort by end time

def jobScheduling(self, startTime, endTime, profit): 
    jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1]) 
    dp = [[0, 0]] 
    for s, e, p in jobs: 
        i = bisect.bisect_right(dp, [s, float('inf')]) - 1 
        i = min(i, len(dp) - 1) 
        if dp[i][1] + p > dp[-1][1]: 
            dp.append([e, dp[i][1] + p]) 
    return dp[-1][1]

1248. Count Number of Nice Subarrays

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays.

def numberOfSubarrays2(self, nums, k): 
        i = count = nice_count = odd_count = 0 # The variable "count" is needed because when "j" hits an even number, it still need to add count
        for j in range(len(nums)): 
            if nums[j] % 2 == 1: 
                odd_count += 1 
                count = 0  # Note that when the number is even, count will remain constant
            while odd_count == k: 
                odd_count -= nums[i] % 2 
                i += 1 
                count += 1 
            nice_count += count 
        return nice_count

1286. Iterator for Combination

Design the CombinationIterator class:

CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
next() Returns the next combination of length combinationLength in lexicographical order.
hasNext() Returns true if and only if there exists a next combination.

class Solution:
    def __init__(self, characters: str, combinationLength: int): 
        self.chars = characters 
        self.N = len(self.chars) 
        self.k = combinationLength 
        self.idx = 0 
        self.end = 2 ** self.N 
         
        base = 2 ** (self.N - 1) 
        for i in range(self.k): 
            self.idx += base 
            base = base >> 1 
            
    def next(self) -> str: 
        res = [self.chars[i] for i in range(self.N) if (1 << (self.N - 1 -i)) & self.idx] 
        self.idx -= 1 
        while self.idx > 0: 
            if bin(self.idx).count('1') == self.k: 
                break 
            self.idx -= 1 
        return ''.join(res) 
             
    def hasNext(self) -> bool: 
        return self.idx > 0

1288. Remove Covered Intervals

Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.

The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.

Return the number of remaining intervals.

def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
    res, longest = len(intervals), 0
    srtd = sorted(intervals, key = lambda i: (i[0], -i[1]))
    
    for _, end in srtd:
        if end <= longest:
            res -= 1
        else:
            longest = end
            
    return res

1428. Leftmost Column with at Least a One

A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order. Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn't exist, return -1. You can’t access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface: BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y) (0-indexed). BinaryMatrix.dimensions() returns a list of 2 elements [m, n], which means the matrix is m * n. Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int: 
        
    rows, cols = binaryMatrix.dimensions() 
        
    # Set pointers to the top-right corner. 
    current_row = 0 
    current_col = cols - 1 
        
    # Repeat the search until it goes off the grid. 
    while current_row < rows and current_col >= 0: 
        if binaryMatrix.get(current_row, current_col) == 0: 
            current_row += 1 
        else: 
            current_col -= 1 
        
    # If we never left the last column, it must have been all 0's. 
    return current_col + 1 if current_col != cols - 1 else -1

1673. Find the Most Competitive Subsequence

Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k. An array's subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array. We define that a subsequence a is more competitive than a subsequence b (of the same length) if in the first position where a and b differ, subsequence a has a number less than the corresponding number in b. For example, [1,3,4] is more competitive than [1,3,5] because the first position they differ is at the final number, and 4 is less than 5.

Monotone stack

def mostCompetitive(self, A, k): 
        stack = [] 
        for i, a in enumerate(A): 
            while stack and stack[-1] > a and len(stack) - 1 + len(A) - i >= k: 
                stack.pop() 
            if len(stack) < k: 
                stack.append(a) 
        return stack

1696. Jump Game VI

You are given a 0-indexed integer array nums and an integer k.

You are initially standing at index 0. In one move, you can jump at most k steps forward without going outside the boundaries of the array. That is, you can jump from index i to any index in the range [i + 1, min(n - 1, i + k)] inclusive.

You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j] for each index j you visited in the array.

Return the maximum score you can get.

def maxResult(self, nums: List[int], k: int) -> int: 
    N = len(nums) 
        
    score = nums[-1] 
    q = collections.deque() 
    q.append((nums[-1], N - 1)) 
        
    for start in reversed(range(N - 1)): 
        while q and q[-1][1] - start > k: 
            q.pop() 
        score = nums[start] + q[-1][0] 
        while q and score >= q[0][0]: 
            q.popleft() 
        q.appendleft((score, start)) 
        
    return score

1760. Minimum Limit of Balls in a Bag

You are given an integer array nums where the ith bag contains nums[i] balls. You are also given an integer maxOperations. You can perform the following operation at most maxOperations times: Take any bag of balls and divide it into two new bags with a positive number of balls. For example, a bag of 5 balls can become two new bags of 1 and 4 balls, or two new bags of 2 and 3 balls. Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.

Return the minimum possible penalty after performing the operations.

def minimumSize(self, nums: List[int], maxOperations: int) -> int: 
    left, right = 1, max(nums) 
    while left < right: 
        mid = (left + right) // 2 
        if sum((n - 1) // mid for n in nums) > maxOperations: 
            left = mid + 1 
        else: 
            right = mid 
    return left

1738. Find Kth Largest XOR Coordinate Value

You are given a 2D matrix of size m x n, consisting of non-negative integers. You are also given an integer k. The value of coordinate (a, b) of the matrix is the XOR of all matrix[i][j] where 0 <= i <= a < m and 0 <= j <= b < n (0-indexed). Find the kth largest value (1-indexed) of all the coordinates of matrix.

Matrix Block Sum

def kthLargestValue(self, matrix: List[List[int]], K: int) -> int: 
	R, C = len(matrix), len(matrix[0]) 
	arr = [] 
	for i in range(R): 
		for j in range(C): 
			if i and j: 
				matrix[i][j] ^= matrix[i-1][j]^matrix[i][j-1]^matrix[i-1][j-1] 
			elif i: 
				matrix[i][j] ^= matrix[i-1][j] 
			elif j: 
				matrix[i][j] ^= matrix[i][j-1] 
			arr.append(matrix[i][j]) 
	arr.sort() 
	return arr[-K]

1776. Car Fleet II

There are n cars traveling at different speeds in the same direction along a one-lane road. You are given an array cars of length n, where cars[i] = [positioni, speedi] represents:

positioni is the distance between the ith car and the beginning of the road in meters. It is guaranteed that positioni < positioni+1.
speedi is the initial speed of the ith car in meters per second. For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the slowest car in the fleet.

Return an array answer, where answer[i] is the time, in seconds, at which the ith car collides with the next car, or -1 if the car does not collide with the next car.

def getCollisionTimes(self, cars: List[List[int]]) -> List[float]: 
    stack = [] 
    res = [-1] * len(cars) 
    inf = float('inf') 
        
    def chaseTime(i, j): 
        if cars[i][1] <= cars[j][1]: 
            return inf 
        return (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1]) 
        
    for i in range(len(cars) - 1, -1, -1): 
        while stack: 
            time = chaseTime(i, stack[-1]) 
            if time == inf or time > res[stack[-1]] > -1: 
                stack.pop() 
            else: 
                break 
            
        if stack: 
            res[i] = chaseTime(i, stack[-1]) 
                
        stack.append(i) 
                
    return res

1871. Jump Game VII

You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:

i + minJump <= j <= min(i + maxJump, s.length - 1), and
s[j] == '0'.

Return true if you can reach index s.length - 1 in s, or false otherwise.

def canReach(self, s: str, minJump: int, maxJump: int) -> bool: 
    if s[-1] == '1': 
        return False 
    
    n = len(s) 
    
    reach = [False] * n 
    
    reach[0] = True 
    cum = 0 
    
    for i in range(1, n): 
        
        if i - maxJump - 1 >= 0: 
            cum -= reach[i - maxJump - 1] 
        if i - minJump >= 0: 
            cum += reach[i - minJump] 
        
        reach[i] = s[i] == '0' and cum > 0 
        
    return reach[-1]

1944. Number of Visible People in a Queue

There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the ith person.

A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]).

Return an array answer of length n where answer[i] is the number of people the ith person can see to their right in the queue.

All the values of heights are unique.

def canSeePersonsCount(self, heights: List[int]) -> List[int]: 
    res = [0] * len(heights) 
    s = [] 
     
    for i, h in enumerate(heights): 
        while s and heights[s[-1]] <= h: 
            res[s[-1]] += 1 
            s.pop() 
        if s: 
            res[s[-1]] += 1 
        s.append(i) 
         
    return res

21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

class Solution: 
    def mergeTwoLists(self, l1, l2): 
        # maintain an unchanging reference to node ahead of the return node. 
        prehead = ListNode(-1) 
        prev = prehead 
        while l1 and l2: 
            if l1.val <= l2.val: 
                prev.next = l1 
                l1 = l1.next 
            else: 
                prev.next = l2 
                l2 = l2.next             
            prev = prev.next 
        # exactly one of l1 and l2 can be non-null at this point, so connect 
        # the non-null list to the end of the merged list. 
        prev.next = l1 if l1 is not None else l2 
        return prehead.next

143. Reorder List

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

def reorderList(self, head: ListNode) -> None: 
    if not head: 
        return  
        
    # find the middle of linked list [Problem 876] 
    # in 1->2->3->4->5->6 find 4  
    slow = fast = head 
    while fast and fast.next: 
        slow = slow.next 
        fast = fast.next.next  
            
    # reverse the second part of the list [Problem 206] 
    # convert 1->2->3->4->5->6 into 1->2->3->4 and 6->5->4 
    # reverse the second half in-place 
    prev, curr = None, slow 
    while curr: 
        curr.next, prev, curr = prev, curr, curr.next        
    # merge two sorted linked lists [Problem 21] 
    # merge 1->2->3->4 and 6->5->4 into 1->6->2->5->3->4 
    first, second = head, prev 
    while second.next: 
        first.next, first = second, first.next 
        second.next, second = first, second.next

146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class: LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in O(1) average time complexity.

class Node:
    def __init__(self, val, key):
        self.val = val
        self.key = key
        self.prev = None
        self.nxt = None
        
class DBList:
    def __init__(self):
        self.dummy = Node(None, None)
        self.dummy.nxt = self.dummy
        self.dummy.prev = self.dummy
        self.size = 0
        
    def remove(self, node):
        node.prev.nxt = node.nxt
        node.nxt.prev = node.prev
        self.size -= 1
        
    def append(self, node):
        node.prev = self.dummy.prev
        node.nxt = self.dummy
        self.dummy.prev.nxt = node
        self.dummy.prev = node
        self.size += 1
        
class LRUCache:

    def __init__(self, capacity: int):
        self.data = {}
        self.dblist = DBList()
        self.cap = capacity
        
    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        
        val = self.data[key].val
        self.dblist.remove(self.data[key])
        self.dblist.append(self.data[key])
        return val
        
    def put(self, key: int, value: int) -> None:

        if key in self.data:
            self.dblist.remove(self.data[key])
            self.data[key].val = value
            self.dblist.append(self.data[key])
            return
        
        if self.dblist.size == self.cap:
            del self.data[self.dblist.dummy.nxt.key]
            self.dblist.remove(self.dblist.dummy.nxt)
            
        self.data[key] = Node(value, key)
        self.dblist.append(self.data[key])

Related question: 460. LFU Cache

160. Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    pA = headA
    pB = headB

    while pA != pB:
        pA = headB if pA is None else pA.next
        pB = headA if pB is None else pB.next

    return pA

234. Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome.

Recursive

def isPalindrome(self, head: ListNode) -> bool: 
    self.front_pointer = head 
    def recursively_check(current_node=head): 
        if current_node is not None: 
            if not recursively_check(current_node.next): 
                return False 
            if self.front_pointer.val != current_node.val: 
                return False 
            self.front_pointer = self.front_pointer.next 
        return True 
    return recursively_check()

Iterative

def isPalindrome(self, head: ListNode) -> bool: 
    if head is None: 
        return True 
    # Find the end of first half and reverse second half. 
    first_half_end = self.end_of_first_half(head) 
    second_half_start = self.reverse_list(first_half_end.next) 
    # Check whether or not there's a palindrome. 
    result = True 
    first_position = head 
    second_position = second_half_start 
    while result and second_position is not None: 
        if first_position.val != second_position.val: 
            result = False 
        first_position = first_position.next 
        second_position = second_position.next 
    # Restore the list and return the result. 
    first_half_end.next = self.reverse_list(second_half_start) 
    return result     
def end_of_first_half(self, head): 
    fast = head 
    slow = head 
    while fast.next is not None and fast.next.next is not None: 
        fast = fast.next.next 
        slow = slow.next 
    return slow 
def reverse_list(self, head): 
    prev= None 
    cur = head 
    while current:
        cur.next, prev, cur = prev, cur, cur.next # cur.next needs to always be before cur because of evaluation order
    return previous

287. Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

def findDuplicate(self, nums: List[int]) -> int: 
    slow = fast = 0 
        
    while True: 
        slow = nums[slow] 
        fast = nums[nums[fast]] 
        if slow == fast: 
            break 
            
    slow = 0 
        
    while slow != fast: 
        slow, fast = nums[slow], nums[fast] 
            
    return slow

460. LFU Cache

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

LFUCache(int capacity) Initializes the object with the capacity of the data structure. int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1. void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated. To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions get and put must each run in O(1) average time complexity.

class EntryDataType:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value

class Node:
    def __init__(self, val=None):
        self.prev = None
        self.next = None
        self.val = val

class DBList:
    def __init__(self):
        self.size = 0
        self.dummy = Node()
        self.dummy.next = self.dummy
        self.dummy.prev = self.dummy
    
    def append(self, node):
        node.prev = self.dummy.prev
        node.next = self.dummy
        self.dummy.prev.next = node
        self.dummy.prev = node
    
    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        return node

    def empty(self):
        return self.dummy.next == self.dummy
        
    def pop_left(self):
        return self.remove(self.dummy.next)
    
class LFUCache:

    def __init__(self, capacity: int):
        self.data = {}
        self.freq = collections.defaultdict(int)
        self.freq_tree = collections.defaultdict(DBList)
        self.min_freq = 0
        self.cap = capacity
        self.size = 0

    def _update(self, key):
        freq = self.freq[key]
        self.freq[key] += 1
        node = self.data[key]
        self.freq_tree[freq].remove(node)
        self.freq_tree[freq + 1].append(node)
        
        if freq == self.min_freq and self.freq_tree[freq].empty():
            self.min_freq += 1
        
    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        
        self._update(key)
        
        return self.data[key].val.value

    def put(self, key: int, value: int) -> None:
        if self.cap == 0:
            return
        
        if key not in self.data:
            
            if self.size == self.cap:
                delete_key = self.freq_tree[self.min_freq].pop_left().val.key
                self.size -= 1
                del self.freq[delete_key]
                del self.data[delete_key]
            
            self.min_freq = 1
            self.freq[key] = 1
            node = Node(EntryDataType(key, value))
            self.freq_tree[1].append(node)
            self.data[key] = node
            self.size += 1

        
        else:
            self.data[key].val.value = value
            self._update(key)

1650. Lowest Common Ancestor of a Binary Tree III

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA). Each node will have a reference to its parent node.

This is essentially a linkedlist question instead of binary tree question.

def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
    p1, p2 = p, q
    while p1 != p2:
        p1 = p1.parent if p1.parent else q
        p2 = p2.parent if p2.parent else p
        
    return p1

703. Kth Largest Element in a Stream

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

from heapq import heapify, heappop, heappush 
class KthLargest: 
    def __init__(self, k: int, nums: List[int]): 
        self.h = nums[:k] 
        self.k = k
        heapify(self.h) 
        for i in range(k, len(nums)): 
            self._add(nums[i]) 
         
    def _add(self, val): 
        if len(self.h) < self.k: 
            heappush(self.h, val)` 
        elif val > self.h[0]: 
            heappop(self.h) 
            heappush(self.h, val) 
         
    def add(self, val: int) -> int: 
        self._add(val) 
        return self.h[0]

778. Swim in Rising Water

You are given an n x n integer matrix grid where each value grid[i][j]represents the elevation at that point (i, j).

The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return the least time until you can reach the bottom right square (n - 1, n - 1)if you start at the top left square (0, 0).

def swimInWater(self, grid): 
    N = len(grid) 
    pq, seen = [(grid[0][0], 0, 0)], set([(0, 0)]) 
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)] 
    while pq: 
        t, x, y = heapq.heappop(pq) 
        if x == y == N - 1: 
            return t 
        for i, j in [(x + dx, y + dy) for dx, dy in dirs]: 
            if 0 <= i < N and 0 <= j < N and (i, j) not in seen: 
                seen.add((i, j)) 
                heapq.heappush(pq, (max(grid[i][j], t), i, j))

2158. Amount of New Area Painted Each Day

There is a long and thin painting that can be represented by a number line. You are given a 0-indexed 2D integer array paint of length n, where paint[i] = [starti, endi]. This means that on the ith day you need to paint the area between starti and endi.

Painting the same area multiple times will create an uneven painting so you only want to paint each area of the painting at most once.

Return an integer array worklog of length n, where worklog[i] is the amount of new area that you painted on the ith day.

Line sweep

Here it is using heap. If you use a binary search tree (SortedList), the logic is more natural

class Solution(object):
    def amountPainted(self, paint):
        """
        :type paint: List[List[int]]
        :rtype: List[int]
        """
        points = collections.defaultdict(list)
        for i, (s, e) in enumerate(paint):
            points[s].append((True, i))
            points[e].append((False, i))
        min_heap = []
        exited = [False]*len(paint)
        result = [0]*len(paint)
        prev = -1
        for pos in sorted(points.iterkeys()):
            while min_heap and exited[min_heap[0]]:
                heapq.heappop(min_heap)

            # Till this point, the segment right before this event is for the one with highest priority
            if min_heap:
                result[min_heap[0]] += pos-prev

            prev = pos
            for is_enter, i in points[pos]:
                if is_enter:
                    heapq.heappush(min_heap, i)
                else:
                    exited[i] = True
        return result

10. Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '' where: '.' Matches any single character. '' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

def isMatch(self, s: str, p: str) -> bool: 
    @cache 
    def match(i, j): 
        if j >= len(p): # Empty pattern only match with empty string 
            return i >= len(s) 
        firstMatch = i < len(s) and p[j] in ['.', s[i]] 
        if j + 1 < len(p) and p[j + 1] == '*': 
            if match(i, j + 2): # In this case, * means zero times
                return True 
            return firstMatch and match(i + 1, j)
        else: 
            return firstMatch and match(i + 1, j + 1) 
    return match(0, 0)

76. Minimum Window Substring

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "". Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

def minWindow(self, s: str, t: str) -> str: 
    left = right = 0 
        
    ct = defaultdict(int) 
        
    for c in t: 
        ct[c] += 1 
        
    required = len(ct.items()) 
        
    ans = float('inf'), -1, -1 
        
    incount = 0 
    sct = defaultdict(int) 
    while right < len(s): 
        c = s[right] 
        if ct[c] > 0: 
            sct[c] += 1 
            if sct[c] == ct[c]:     
                incount += 1 
                    
        while left <= right and incount == required: 
            c = s[left] 
            if right - left + 1 < ans[0]: 
                ans = right - left + 1, left, right 
            if ct[c] > 0: 
                sct[c] -= 1 
                if sct[c] < ct[c]: 
                    incount -= 1 
            left += 1 
                
        right += 1 
            
    if ans[1] == float('inf'): 
        return '' 
    else: 
        return s[ans[1] : ans[2] + 1]

132. Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.

class Solution { 
public: 
    int minCut(string s) { 
        vector<int> cutsDp; 
        cutsDp.resize(s.length()); 
        for (int i = 1; i < s.length(); i++) { 
            cutsDp[i] = i; 
        } 
        for (int mid = 0; mid < s.length(); mid++) { 
            // check for odd length palindrome around mid index 
            findMinimumCuts(mid, mid, cutsDp, s); 
            // check for even length palindrome around mid index 
            findMinimumCuts(mid - 1, mid, cutsDp, s); 
        } 
        return cutsDp[s.length() - 1]; 
    } 
    void findMinimumCuts(int startIndex, int endIndex, vector<int> &cutsDp, 
                         string s) { 
        for (int start = startIndex, end = endIndex; 
             start >= 0 && end < s.length() && s[start] == s[end]; 
             start--, end++) { 
            int newCut = start == 0 ? 0 : cutsDp[start - 1] + 1; 
            cutsDp[end] = min(cutsDp[end], newCut); 
        } 
    } 
};

224. Basic Calculator

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation. s consists of digits, '+', '-', '(', ')', and ' '.

def calculate(self, s: str) -> int: 
    curnum = 0 
    sign = 1 
    cursigns = [] 
    curproduct = 1 
    res = 0 
     
    s = '(' + s + ')' 
    for i, c in enumerate(s): 
        if c.isdecimal(): 
            curnum = curnum * 10 + int(c) 
            if i + 1 == len(s) - 1 or not s[i + 1].isdecimal(): 
                res += curnum * curproduct * sign 
                curnum = 0 
        elif c == '-': 
            sign = -1 
         
        elif c == '+': 
            sign = 1 
             
        elif c == ')': 
            curproduct *= cursigns.pop() 
        elif c == '(': 
            cursigns.append(sign) 
            curproduct *= cursigns[-1] 
            sign = 1 
    return res

227. Basic Calculator II

Given a string s which represents an expression, evaluate this expression and return its value. s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.

def calculate(self, s: str) -> int: 
    num = 0 
    res = 0 
    last = 0 
    op = '+' 
     
    for i, c in enumerate(s): 
        if c.isdecimal(): 
            num = 10 * num + int(c) 
            if i == len(s) - 1 or not s[i + 1].isdecimal(): 
                if op == '+': 
                    res += num 
                    last = num 
                elif op == '-': 
                    res -= num 
                    last = -num 
                elif op == '*': 
                    res = res - last + last * num 
                    last = last * num 
                else: 
                    res = res - last + int(last / num) 
                    last = int(last / num) 
                num = 0 
        else: 
            if c in ['+', '-', '*', '/']: 
                op = c 
                 
    return res

420. Strong Password Checker

A password is considered strong if the below conditions are all met:

It has at least 6 characters and at most 20 characters.
It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.
It does not contain three repeating characters in a row (i.e., "...aaa..." is weak, but "...aa...a..." is strong, assuming other conditions are met).

Given a string password, return the minimum number of steps required to make password strong. if password is already strong, return 0.

In one step, you can:

Insert one character to password,
Delete one character from password, or
Replace one character of password with another character.

def strongPasswordChecker(self, s): 
    """ 
    :type s: str 
    :rtype: int 
    """ 
    missing_type = 3 
    if any('a' <= c <= 'z' for c in s): missing_type -= 1 
    if any('A' <= c <= 'Z' for c in s): missing_type -= 1 
    if any(c.isdigit() for c in s): missing_type -= 1 
    change = 0 
    one = two = 0 
    p = 2 
    while p < len(s): 
        if s[p] == s[p-1] == s[p-2]: 
            length = 2 
            while p < len(s) and s[p] == s[p-1]: 
                length += 1 
                p += 1 
                    
            change += length // 3 
            if length % 3 == 0: one += 1 
            elif length % 3 == 1: two += 1 
        else: 
            p += 1 
        
    if len(s) < 6: 
        return max(missing_type, 6 - len(s)) 
    elif len(s) <= 20: 
        return max(missing_type, change) 
    else: 
#If length of the string is larger than 20, we will need to delete some chars and appropriate deletion can reduce the number of replacements needed to break repeating sequences #after deletion. For any repeating sequences with len % 3 == 0, we need to make len/3 replacements and we can reduce the number of replacements len/3 by one by deleting one #character. Similarly, for any repeating sequences with len % 3 == 1, we can reduce one replacement by deleting two characters. Now we know that for all sequences, including #those already deleted chars from, we have len % 3 == 2 so we can reduce every replacement by deleting three characters such that every deleting action counts.
        delete = len(s) - 20 
            
        change -= min(delete, one) 
        change -= min(max(delete - one, 0), two * 2) // 2 
        change -= max(delete - one - 2 * two, 0) // 3 
                
        return delete + max(missing_type, change)

772. Basic Calculator III

Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.

import collections 
class Solution: 
    # Standard parser implementation based on this BNF 
    #   s := expression 
    #   expression := term | term { [+,-] term] } 
    #   term := factor | factor { [*,/] factor] } 
    #   factor :== digit | '(' expression ')' 
    #   digit := [0..9] 
    def calculate(self, s: str) -> 'Node': 
        tokens = collections.deque() 
         
        if s[0] == '-': 
            s = '0' + s 
         
        hasnum = False 
        num = 0 
         
        for c in s: 
            if c.isdigit(): 
                num = int(c) + 10 * num 
                hasnum = True 
            else: 
                if hasnum: 
                    tokens.append(num) 
                    num = 0 
                    hasnum = False 
                tokens.append(c) 
                 
        if hasnum: 
            tokens.append(num) 
                 
        return self.parse_expression(tokens) 

    def parse_expression(self, tokens): 
        lhs = self.parse_term(tokens) 
        while len(tokens) > 0 and tokens[0] in ['+', '-']: 
            op = tokens.popleft() 
            rhs = self.parse_term(tokens) 
            if op == '+': 
                lhs += rhs 
            else: 
                lhs -= rhs 
        return lhs 

    def parse_term(self, tokens): 
        lhs = self.parse_factor(tokens) 
        while len(tokens) > 0 and tokens[0] in ['*', '/']: 
            op = tokens.popleft() 
            rhs = self.parse_factor(tokens) 
            if op == '*': 
                lhs *= rhs 
            else: 
                lhs = int(lhs/rhs) 
        return lhs 

    def parse_factor(self, tokens): 
        if tokens[0] == '(': 
            tokens.popleft()  # consume '(' 
            val = self.parse_expression(tokens) 
            tokens.popleft()  # consume ')' 
            return val 
        else: 
            # Single operand 
            token = tokens.popleft() 
            return token

1597. Build Binary Expression Tree From Infix Expression

A binary expression tree is a kind of binary tree used to represent arithmetic expressions. Each node of a binary expression tree has either zero or two children. Leaf nodes (nodes with 0 children) correspond to operands (numbers), and internal nodes (nodes with 2 children) correspond to the operators '+' (addition), '-' (subtraction), '*' (multiplication), and '/' (division).

For each internal node with operator o, the infix expression that it represents is (A o B), where A is the expression the left subtree represents and B is the expression the right subtree represents.

You are given a string s, an infix expression containing operands, the operators described above, and parentheses '(' and ')'.

Return any valid binary expression tree, which its in-order traversal reproduces s after omitting the parenthesis from it (see examples below).

Please note that order of operations applies in s. That is, expressions in parentheses are evaluated first, and multiplication and division happen before addition and subtraction.

Operands must also appear in the same order in both s and the in-order traversal of the tree.

class Solution: 
    # Standard parser implementation based on this BNF 
    #   s := expression 
    #   expression := term | term { [+,-] term] } 
    #   term := factor | factor { [*,/] factor] } 
    #   factor :== digit | '(' expression ')' 
    #   digit := [0..9] 
     
    def expTree(self, s: str) -> 'Node': 
        tokens = collections.deque(list(s)) 
        return self.parse_expression(tokens) 

    def parse_expression(self, tokens): 
        lhs = self.parse_term(tokens) 
        while len(tokens) > 0 and tokens[0] in ['+', '-']: 
            op = tokens.popleft() 
            rhs = self.parse_term(tokens) 
            lhs = Node(val=op, left=lhs, right=rhs) 
        return lhs 
     
    def parse_term(self, tokens): 
        lhs = self.parse_factor(tokens) 
        while len(tokens) > 0 and tokens[0] in ['*', '/']: 
            op = tokens.popleft() 
            rhs = self.parse_factor(tokens) 
            lhs = Node(val=op, left=lhs, right=rhs) 
        return lhs 

    def parse_factor(self, tokens): 
        if tokens[0] == '(': 
            tokens.popleft() # consume '(' 
            node = self.parse_expression(tokens) 
            tokens.popleft() # consume ')' 
            return node 
        else: 
            # Single operand 
            token = tokens.popleft() 
            return Node(val=token)

2060. Check if an Original String Exists Given Two Encoded Strings

An original string, consisting of lowercase English letters, can be encoded by the following steps: Arbitrarily split it into a sequence of some number of non-empty substrings. Arbitrarily choose some elements (possibly none) of the sequence, and replace each with its length (as a numeric string). Concatenate the sequence as the encoded string. For example, one way to encode an original string "abcdefghijklmnop" might be: Split it as a sequence: ["ab", "cdefghijklmn", "o", "p"]. Choose the second and third elements to be replaced by their lengths, respectively. The sequence becomes ["ab", "12", "1", "p"]. Concatenate the elements of the sequence to get the encoded string: "ab121p". Given two encoded strings s1 and s2, consisting of lowercase English letters and digits 1-9 (inclusive), return true if there exists an original string that could be encoded as boths1 and s2. Otherwise, return false. Note: The test cases are generated such that the number of consecutive digits in s1 and s2 does not exceed 3.

from functools import lru_cache 
class Solution: 
    def possiblyEquals(self, s1: str, s2: str) -> bool: 
         
        def getNextNonDigit(s,start): 
            end = start 
            while end < len(s) and s[end].isdigit(): end += 1 
            return end 
         
        @lru_cache(None) 
        def possibleLengths(s):  # This itself is an interesting problem
            """Return all possible lengths represented by numeric string s.""" 
            ans = {int(s)} 
            for i in range(1, len(s)): 
                # add all lengths by splitting numeric string s at i 
                ans |= {x+y for x in possibleLengths(s[:i]) for y in possibleLengths(s[i:])} 
            return ans 
         
        @lru_cache(None) 
        def dp(i, j, diff):              
            """Return True if s1[i:] matches s2[j:] with given differences.""" 
            # Invalid cases
            if i > len(s1) or j > len(s2):
                return False

            # If both have reached end return true if none of them are leading 
            if i == len(s1) and j == len(s2): 
                return diff == 0 
             
            # s1 has not reached end and s1 starts with a digit 
            if i < len(s1) and s1[i].isdigit():  
                i2 = getNextNonDigit(s1, i) 
                for L in possibleLengths(s1[i:i2]):  
                    # substract since lead of s2  decreases by L 
                    if dp(i2, j, diff-L): return True  
             
            # s2 has not reached end and s2 starts with a digit 
            elif j < len(s2) and s2[j].isdigit():  
                j2 = getNextNonDigit(s2, j) 
                for L in possibleLengths(s2[j:j2]):  
                    # add since lead of s2 increase by L 
                    if dp(i, j2, diff+L): return True  
             
            # if none of them have integer prefix or a lead over the other 
            elif diff == 0:  
                # if only one of them has reached end or current alphabets are not the same  
                if i == len(s1) or j == len(s2) or s1[i] != s2[j]: 
                    return False  
                # skip same alphabets 
                return dp(i+1, j+1, 0) 
             
            # if none of them have integer prefix & s2 lead over s1  
            elif diff > 0:  
                # move s1 pointer forward and reduce diff 
                return dp(i+1, j, diff-1) 
             
            # if none of them have integer prefix & s1 lead over s2 
            else:  
                # move s2 pointer forward and increase diff 
                return dp(i, j+1, diff+1) 
         
        # start with starts of both s1 and s2 with no lead by any of them 
        return dp(0, 0, 0)

99. Recover Binary Search Tree

def recoverTree(self, root: Optional[TreeNode]) -> None: 
    vals = [] 
     
    def addval(cur): 
        if not cur: 
            return 
        addval(cur.left) 
        vals.append(cur.val) 
        addval(cur.right) 
     
    # The first element is always larger than its next one while the second element is always smaller than its previous one.
    def find_two_swapped(nums): 
        x, y = None, None 
        for i in range(len(nums) - 1): 
            if nums[i + 1] < nums[i]: 
                y = nums[i + 1] 
                if x is None: 
                    x = nums[i] 
                else: 
                    break 
        return x, y 
     
    def fixval(cur): 
        if not cur: 
            return 
        if cur.val == x: 
            cur.val = y 
        elif cur.val == y: 
            cur.val = x 
        fixval(cur.left) 
        fixval(cur.right) 
     
    addval(root) 
    x, y = find_two_swapped(vals) 
    fixval(root)

Merge steps

def recoverTree(self, root: TreeNode): 
    stack = [] 
    x = y = pred = None 
     
    while stack or root: 
        while root: 
            stack.append(root) 
            root = root.left 
        root = stack.pop() 
        if pred and root.val < pred.val: 
            y = root 
            if x is None: 
                x = pred  
            else: 
                break 
        pred = root 
        root = root.right 
    x.val, y.val = y.val, x.val

124. Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path. A node's value can be negative.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.res = -float('inf')

        # Returns the max path sum that starts from the node and ends with one of its child
        def dfs(node) -> int:
          if not node:
            return 0
          lmax = max(0, dfs(node.left))
          rmax = max(0, dfs(node.right))
          self.res = max(self.res, lmax + rmax + node.val)
          return node.val + max(lmax, rmax)

        dfs(root)
        return self.res

199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

def rightSideView(self, root: TreeNode) -> List[int]: 
    if root is None: 
        return [] 
        
    rightside = [] 
        
    def helper(node: TreeNode, level: int) -> None: 
        if level == len(rightside): 
            rightside.append(node.val) 
        for child in [node.right, node.left]: 
            if child: 
                helper(child, level + 1) 
                
    helper(root, 0) 
    return rightside

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.

class Solution: 
    def __init__(self): 
        # Variable to store LCA node. 
        self.ans = None 
    def lowestCommonAncestor(self, root, p, q): 
        """ 
        :type root: TreeNode 
        :type p: TreeNode 
        :type q: TreeNode 
        :rtype: TreeNode 
        """ 
        def recurse_tree(current_node): 
            # If reached the end of a branch, return False. 
            if not current_node: 
                return False 
            # Left Recursion 
            left = recurse_tree(current_node.left) 
            # Right Recursion 
            right = recurse_tree(current_node.right) 
            # If the current node is one of p or q 
            mid = current_node == p or current_node == q 
            # If any two of the three flags left, right or mid become True. 
            if mid + left + right >= 2: 
                self.ans = current_node 
            # Return True if either of the three bool values is True. 
            return mid or left or right 
        # Traverse the tree 
        recurse_tree(root) 
        return self.ans

285. Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST. The successor of a node p is the node with the smallest key greater than p.val.

def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode': 
    result,cur = None,root 
    while cur: 
        if cur.val > p.val: 
            result = cur 
            cur = cur.left 
        else: 
            cur = cur.right 
    return result

307. Range Sum Query - Mutable

Given an integer array nums, handle multiple queries of the following types:

Update the value of an element in nums.
Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class: NumArray(int[] nums) Initializes the object with the integer array nums. void update(int index, int val) Updates the value of nums[index] to be val. int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Segment tree (standard implementation)

class NumArray:

    def __init__(self, nums: List[int]):
        self.N = len(nums)
        self.tree = [0] * self.N + nums
        # self.tree[0] is not used
        for i in range(self.N - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index: int, val: int) -> None:
        pos = index + self.N
        diff = val - self.tree[pos]
        while pos > 0:
            self.tree[pos] += diff
            pos //= 2
            
    def sumRange(self, left: int, right: int) -> int:
        l = left + self.N
        r = right + self.N
        s = 0
        
        while l <= r: # When l == r, it is guaranteed that the loop will exit
            if l % 2:
                s += self.tree[l]
                l += 1
            if not r % 2:
                s += self.tree[r]
                r -= 1

            l //= 2
            r //= 2
        
        return s

315. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Merge Sort

def countSmaller(self, nums: List[int]) -> List[int]:
    res = [0] * len(nums)
    
    array = list(zip(nums, range(len(nums))))
    
    def mergeSort(arr, left, right):
        if left == right:
            return
        
        mid = left + (right - left) // 2
        mergeSort(arr, left, mid)
        mergeSort(arr, mid + 1, right)
        merge(arr, left, mid, right)
        
    def merge(arr, left, mid, right):
        i = left
        j = mid + 1
        
        tmp = []
        
        while i <= mid or j <= right:
            if j > right or (i <= mid and arr[i][0] <= arr[j][0]):
                tmp.append(arr[i])
                res[arr[i][1]] += j - mid - 1
                i += 1
            else:
                tmp.append(arr[j])
                j += 1
                
        arr[left:right + 1] = tmp
        
    mergeSort(array, 0, len(nums) - 1)
    return res

Segment Tree

def countSmaller(self, nums: List[int]) -> List[int]: 
    # implement segment tree 
    def update(index, value, tree, size): 
        index += size  # shift the index to the leaf 
        # update from leaf to root 
        tree[index] += value 
        while index > 1: 
            index //= 2 
            tree[index] = tree[index * 2] + tree[index * 2 + 1] 
    def query(left, right, tree, size): 
        # return sum of [left, right) 
        result = 0 
        left += size  # shift the index to the leaf 
        right += size 
        while left < right: 
            # if left is a right node 
            # bring the value and move to parent's right node 
            if left % 2 == 1: 
                result += tree[left] 
                left += 1 
            # else directly move to parent 
            left //= 2 
            # if right is a right node 
            # bring the value of the left node and move to parent 
            if right % 2 == 1: 
                right -= 1 
                result += tree[right] 
            # else directly move to parent 
            right //= 2 
        return result 
    offset = 10**4  # offset negative to non-negative 
    size = 2 * 10**4 + 1  # total possible values in nums 
    tree = [0] * (2 * size) 
    result = [] 
    for num in reversed(nums): 
        smaller_count = query(0, num + offset, tree, size) 
        result.append(smaller_count) 
        update(num + offset, 1, tree, size) 
    return reversed(result)

Binary Index Tree

def countSmaller(self, nums: List[int]) -> List[int]: 
    # implement Binary Index Tree 
    def update(index, value, tree, size): 
        index += 1  # index in BIT is 1 more than the original index 
        while index < size: 
            tree[index] += value 
            index += index & -index 
    def query(index, tree): 
        # return sum of [0, index) 
        result = 0 
        while index >= 1: 
            result += tree[index] 
            index -= index & -index 
        return result 
    offset = 10**4  # offset negative to non-negative 
    size = 2 * 10**4 + 2  # total possible values in nums plus one dummy 
    tree = [0] * size 
    result = [] 
    for num in reversed(nums): 
        smaller_count = query(num + offset, tree) 
        result.append(smaller_count) 
        update(num + offset, 1, tree, size) 
    return reversed(result)

437. Path Sum III

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int: 
    res = 0 
    h = collections.defaultdict(int) 
    h[0] = 1 
     
    def preorder(node, s): 
        nonlocal res 
        cur_sum = s + node.val 
         
        res += h[cur_sum - targetSum] 
         
        h[cur_sum] += 1 
        if node.left: 
            preorder(node.left, cur_sum) 
        if node.right: 
            preorder(node.right, cur_sum) 
        h[cur_sum] -= 1 
     
    if not root: 
        return 0 
     
    preorder(root, 0) 
     
    return res

958. Check Completeness of a Binary Tree

Given the root of a binary tree, determine if it is a complete binary tree.

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1and 2hnodes inclusive at the last level h.

Short and Smart

def isCompleteTree(self, root: Optional[TreeNode]) -> bool: 
    dq = collections.deque([root]) 
     
    while True: 
        node = dq.popleft() 
        if not node: 
            return not any(dq) 
        dq.append(node.left) 
        dq.append(node.right)

Use node numbering system.

Root is 1. Left is parent * 2, right is parent * 2 + 1

def isCompleteTree(self, root: Optional[TreeNode]) -> bool: 
    filled = set() 
     
    def visit(node, val): 
        if not node: 
            return 
        filled.add(val) 
        visit(node.left, val * 2) 
        visit(node.right, val * 2 + 1) 
         
    visit(root, 1) 
     
    seenFalse = False 
    for i in range(1, max(filled) + 1): 
        if i not in filled: 
            seenFalse = True 
        elif seenFalse: 
            return False 
    return True

140. Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Trie tree (does not have to use this data structure)

class Node: 
    def __init__(self, word=None): 
        self.children = {} 
        self.isleaf = False 
        self.word = word 

class Solution: 
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: 
        s = s 
        dummy = Node('') 
        for word in wordDict: 
            cur = dummy 
            for i, c in enumerate(word): 
                if c not in cur.children: 
                    cur.children[c] = Node() 
                cur = cur.children[c] 
                if i == len(word) - 1: 
                    cur.isleaf = True 
                    cur.word = word 
                    
        @lru_cache(None) 
        def wordBreakPartial(istart): 
            curnode = dummy 
            ans = [] 
            for i in range(istart, len(s)): 
                c = s[i] 
                if c in curnode.children: 
                    curnode = curnode.children[c] 
                    if curnode.isleaf: 
                        if i == len(s) - 1: 
                            ans.append(curnode.word) 
                        else: 
                            for sentence in wordBreakPartial(i + 1): 
                                ans.append(curnode.word + ' ' + sentence) 
                else: 
                    break 
            return ans 
        return wordBreakPartial(istart=0)

212. Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

class TrieNode: 
    def __init__(self): 
        self.is_leaf = False 
        self.children = {} 
        self.word = None 

class TrieTree: 
    def __init__(self): 
        self.root = TrieNode() 
        self.word = False 
    def insert(self, s): 
        cur = self.root 
        for c in s: 
            if c not in cur.children: 
                cur.children[c] = TrieNode() 
            cur = cur.children[c] 
        cur.word = s 
        
class Solution: 
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: 
        tree = TrieTree() 
        for word in words: 
            tree.insert(word) 
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)] 
        m, n = len(board), len(board[0]) 
        ans = [] 
        def backtrack(i, j): 
            nonlocal root 
            letter = board[i][j] 
            if letter not in root.children: 
                return 
            oldroot = root 
            root = root.children[letter] 
            board[i][j] = '#' 
            if root.word: 
                ans.append(root.word) 
                root.word = None 
            for dx, dy in dirs: 
                if 0 <= i + dx < m and 0 <= j + dy < n and board[i + dx][j + dy] != '#': 
                    backtrack(i + dx, j + dy) 
            board[i][j] = letter 
            root = oldroot 
        for i in range(m): 
            for j in range(n): 
                root = tree.root 
                backtrack(i, j) 
        return ans

729. My Calendar I

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking. A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.). The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class: MyCalendar() Initializes the calendar object. boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Using balanced tree in C++

class MyCalendar {
private:
    map<int, int> tree;

public:
    MyCalendar() {}
    
    bool book(int start, int end) {
        auto nxt = tree.lower_bound(start);
        if (nxt != tree.end() && nxt->first < end)
            return false;
        if (nxt != tree.begin() && (--nxt)->second > start)
            return false;

        tree[start] = end;
        return true;
    }
};

820. Short Encoding of Words

A valid encoding of an array of words is any reference string s and array of indices indices such that: words.length == indices.length.

The reference string s ends with the '#' character. For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i]. Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.

The way the Trie data structure is written is awesome

def minimumLengthEncoding(self, words):
    words = list(set(words)) #remove duplicates
    #Trie is a nested dictionary with nodes created
    # when fetched entries are missing
    Trie = lambda: collections.defaultdict(Trie)
    trie = Trie()

    #reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]
    nodes = [reduce(dict.__getitem__, word[::-1], trie)
                for word in words]

    #Add word to the answer if it's node has no neighbors
    return sum(len(word) + 1
                for i, word in enumerate(words)
                if len(nodes[i]) == 0)

1707. Maximum XOR With an Element From Array

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [xi, mi]. The answer to the ith query is the maximum bitwise XOR value of xi and any element of nums that does not exceed mi. In other words, the answer is max(nums[j] XOR xi) for all j such that nums[j] <= mi. If all elements in nums are larger than mi, then the answer is -1. Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the ith query.

class Trie: 
    def __init__(self): 
        self.root = {} 
         
    def insert(self, num): 
        p = self.root 
        for i in range(31, -1, -1): 
            cur = (num >> i) & 1 
            if cur not in p: 
                p[cur] = {} 
            p = p[cur] 
                 
    def query(self, num): 
        if not self.root:  
            return -1 
        p, ans = self.root, 0 
        for i in range(31, -1, -1): 
            cur = (num >> i) & 1 
            if 1 - cur in p: 
                p = p[1 - cur] 
                ans |= (1 << i) 
            else: 
                p = p[cur] 
        return ans 

class Solution: 
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]: 
        nums.sort() 
        queries = sorted(enumerate(queries), key=lambda x: x[1][1]) 
        trie = Trie() 
        ans = [-1] * len(queries) 
        j = 0 
        for i, (x, m) in queries: 
            while j < len(nums) and nums[j] <= m: 
                trie.insert(nums[j]) 
                j += 1 
            ans[i] = trie.query(x) 
        return ans

2034. Stock Price Fluctuation

You are given a stream of records about a particular stock. Each record contains a timestamp and the corresponding price of the stock at that timestamp.

Unfortunately due to the volatile nature of the stock market, the records do not come in order. Even worse, some records may be incorrect. Another record with the same timestamp may appear later in the stream correcting the price of the previous wrong record.

Design an algorithm that:

Updates the price of the stock at a particular timestamp, correcting the price from any previous records at the timestamp. Finds the latest price of the stock based on the current records. The latest price is the price at the latest timestamp recorded. Finds the maximum price the stock has been based on the current records. Finds the minimum price the stock has been based on the current records. Implement the StockPrice class:

StockPrice() Initializes the object with no price records. void update(int timestamp, int price) Updates the price of the stock at the given timestamp. int current() Returns the latest price of the stock. int maximum() Returns the maximum price of the stock. int minimum() Returns the minimum price of the stock.

This is a very classic problem. Need to remember how to do it in multiple languages.

C++ with unordered_map and multiset

class StockPrice {
private:
    multiset<int> count;
    unordered_map<int, int> rec;
    int now;
    
public:
    StockPrice() {}
    
    void update(int timestamp, int price) {
        auto it = rec.find(timestamp);
        if (it != rec.end()) {
            count.erase(count.find(it->second));
        }
        count.insert(price);
        
        rec[timestamp] = price;
        
        now = max(now, timestamp);
    }
    
    int current() {
        return rec[now];
    }
    
    int maximum() {
        return *count.rbegin();
    }
    
    int minimum() {
        return *count.begin();
    }
};

Python with dictionary and SortedList

from sortedcontainers import SortedList

class StockPrice:

    def __init__(self):
        self.l = SortedList()
        self.dct = {}
        self.latest = 0

    def update(self, timestamp: int, price: int) -> None:
        if timestamp in self.dct: 
            self.l.discard(self.dct[timestamp])
        self.l.add(price)

        self.dct[timestamp] = price

        self.latest = max(self.latest, timestamp)

    def current(self) -> int:
        return self.dct[self.latest]

    def maximum(self) -> int:
        return self.l[-1]

    def minimum(self) -> int:
        return self.l[0]

210. Course Schedule II

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

from collections import defaultdict 
class Solution: 
    WHITE = 1 
    GRAY = 2 
    BLACK = 3 
    def findOrder(self, numCourses, prerequisites): 
        # Create the adjacency list representation of the graph 
        adj_list = defaultdict(list) 
        # A pair [a, b] in the input represents edge from b --> a 
        for dest, src in prerequisites: 
            adj_list[src].append(dest) 
        topological_sorted_order = [] 
        is_possible = True 
        # By default all vertces are WHITE 
        color = {k: Solution.WHITE for k in range(numCourses)} 
        def dfs(node): 
            nonlocal is_possible 
            # Don't recurse further if we found a cycle already 
            if not is_possible: 
                return 
            # Start the recursion 
            color[node] = Solution.GRAY 
            # Traverse on neighboring vertices 
            if node in adj_list: 
                for neighbor in adj_list[node]: 
                    if color[neighbor] == Solution.WHITE: 
                        dfs(neighbor) 
                    elif color[neighbor] == Solution.GRAY: 
                         # An edge to a GRAY vertex represents a cycle 
                        is_possible = False 
            # Recursion ends. We mark it as black 
            color[node] = Solution.BLACK 
            topological_sorted_order.append(node) 
        for vertex in range(numCourses): 
            # If the node is unprocessed, then call dfs on it. 
            if color[vertex] == Solution.WHITE: 
                dfs(vertex) 
        return topological_sorted_order[::-1] if is_possible else []

317. Shortest Distance from All Buildings

You are given an m x n grid grid of values 0, 1, or 2, where:

each 0 marks an empty land that you can pass by freely, each 1 marks a building that you cannot pass through, and each 2 marks an obstacle that you cannot pass through. You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right.

Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1. The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

def shortestDistance(self, grid: List[List[int]]) -> int:
    buildings = []
    m = len(grid)
    n = len(grid[0])
    inf = float('inf')    
        
    dist = [[0] * n for _ in range(m)]
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    def inbound(i, j):
        return 0 <= i < m and 0 <= j < n
    
    def neighbors(i, j):
        for dx, dy in dirs:
            newx, newy = i + dx, j + dy
            if inbound(newx, newy) and grid[newx][newy] == identifier:
                yield newx, newy
    
    def bfs(i, j):
        visited = set()
        q = collections.deque([(i, j, 0)])
        visited.add((i, j))
        while q:
            a, b, d = q.popleft()
            dist[a][b] += d
            for x, y in neighbors(a, b):
                if grid[x][y] == identifier:
                    grid[x][y] -= 1
                    q.append((x, y, d + 1))

    identifier = 0 # This is a super trick

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                bfs(i, j)
                identifier -= 1
    
    res = inf
    
    for i in range(m):
        for j in range(n):
            if grid[i][j] == identifier:
                res = min(res, dist[i][j])
    
    return -1 if res == float('inf') else res

332. Reconstruct Itinerary

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"]. You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Eulerian path. Hierholzer's Algorithm

class Solution: 
    def findItinerary(self, tickets): 
        targets = collections.defaultdict(list) 
        for a, b in sorted(tickets)[::-1]: 
            targets[a] += b, 

        route, stack = [], ['JFK'] 
        while stack: 
            while targets[stack[-1]]: 
                stack += targets[stack[-1]].pop(), 
            route += stack.pop(), 
        return route[::-1]

787. Cheapest Flights Within K Stops

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return-1

def findCheapestPrice(self, n, flights, src, dst, K): 
    graph = defaultdict(list) 
    for s, d, p in flights: 
        graph[s].append((d, p))

    least_moves = defaultdict(lambda: float('inf')) 
    least_cost = defaultdict(lambda: float('inf')) 
    least_moves[src] = 0 
    least_cost[src] = 0

    # price, moves, node 
    heap = [(0, 0, src)] 
    while heap: 
        price, moves, node = heappop(heap) 
        if node == dst: 
            return price 
        if moves == K + 1:  # No remaining stops to use 
            continue 
        new_moves = moves + 1

        for nei, cost in graph[node]: 
            new_prive = price + cost 
            if new_prive < least_cost[nei] or new_moves < least_moves[nei]:  # Need to be better on either dimension; actually we want the new entry to be better than all previous entries in at least one dimension, but it will take time to implement it. So here simply record the lastest entry for the same destination and compare the new entry with it as a method for pruning
                least_cost[nei] = new_price 
                least_moves[nei] = new_moves 
                heappush(heap, (new_price, new_moves, nei))

    return -1

847. Shortest Path Visiting All Nodes

You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

DFS

def shortestPathLength(self, graph: List[List[int]]) -> int: 
    cache = {} # Will cause infitite loop if using @cache 
    def steps(node, status): 
        if (node, status) in cache: 
            return cache[node, status] 
        if status & (status - 1) == 0: 
            return 0 
        cache[node, status] = float('inf') # This is the key to avoid infinite loop 
        for neighbor in graph[node]: 
            if status & (1 << neighbor):  
                cache[node, status] = min(cache[node, status], 1 + steps(neighbor, status), 1 + steps(neighbor, status ^ (1 << node))) 
        return cache[node, status] 
    final_status = (1 << len(graph)) - 1 
    return min(steps(node, final_status) for node in range(len(graph)))

BFS

def shortestPathLength(self, graph): 
    if len(graph) == 1: 
        return 0 
     
    n = len(graph) 
    final_status = (1 << n) - 1 
    queue = collections.deque([(node, 1 << node) for node in range(n)]) 
    seen = set(queue) 
    steps = 1 
    while queue: 
        for _ in range(len(queue)): 
            node, status = queue.popleft() 
            for neighbor in graph[node]: 
                next_status = status | (1 << neighbor) 
                if next_status == final_status: 
                    return steps 
                 
                if (neighbor, next_status) not in seen: 
                    seen.add((neighbor, next_status)) 
                    queue.append((neighbor, next_status)) 
         
        steps += 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.

BFS

This question is very similar to 787. Cheapest Flights Within K Stops

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        from collections import deque
        
        # irow, icol, steps, number of obstacle removal
        dq = deque([(0, 0, 0, 0)])
        
        m, n = len(grid), len(grid[0])
        
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        lowest = [[float('inf')] * n for _ in range(m)] # The minimum number of obstacles that need to be removed
        lowest[0][0] = 0
        
        def getNeighbors(r, c):
            for dx, dy in dirs:
                newr, newc = r + dx, c + dy
                if 0 <= newr < m and 0 <= newc < n:
                    yield newr, newc
        
        while dq:
            r, c, nstep, nremoval = dq.popleft()
            if r == m - 1 and c == n - 1:
                return nstep
            
            for newr, newc in getNeighbors(r, c):
                if grid[newr][newc] and nremoval == k:
                    continue
                nremoval_new = nremoval + grid[newr][newc]
                if lowest[newr][newc] > nremoval_new:
                    lowest[newr][newc] = nremoval_new
                    dq.append((newr, newc, nstep + 1, nremoval_new))
                
        return -1

1192. Critical Connections in a Network (Hard)

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.

Tarjan's algorithm

def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
    
    dic = collections.defaultdict(list)
    for c in connections:
        u, v = c
        dic[u].append(v)
        dic[v].append(u)
        
    timer = 0
    
    depth, lowest, parent, visited = [float("inf")]*n, [float("inf")]*n, [float("inf")]*n, [False]*n
    res = []
    
    def find(u):
        
        nonlocal timer
        
        visited[u] = True
        depth[u], lowest[u] = timer, timer
        timer += 1
        
        for v in dic[u]:
            if not visited[v]:
                parent[v] = u
                find(v)
                if lowest[v] > depth[u]:
                    res.append([u,v])
            
            if parent[u] != v:
                lowest[u] = min(lowest[u], lowest[v])
            
    find(0)
    return res

1928. Minimum Cost to Reach Destination in Time

There is a country of n cities numbered from 0 to n - 1 where all the cities are connected by bi-directional roads. The roads are represented as a 2D integer array edges where edges[i] = [xi, yi, timei] denotes a road between cities xi and yi that takes timei minutes to travel. There may be multiple roads of differing travel times connecting the same two cities, but no road connects a city to itself.

Each time you pass through a city, you must pay a passing fee. This is represented as a 0-indexed integer array passingFees of length n where passingFees[j] is the amount of dollars you must pay when you pass through city j.

In the beginning, you are at city 0 and want to reach city n - 1 in maxTime minutes or less. The cost of your journey is the summation of passing fees for each city that you passed through at some moment of your journey (including the source and destination cities).

Given maxTime, edges, and passingFees, return the minimum cost to complete your journey, or -1 if you cannot complete it within maxTime minutes.

Modified Dijkstra

def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:  
    from heapq import heapify, heappush, heappop  
    h = [(passingFees[0], 0, 0)]  
    n = len(passingFees)  
      
    g = collections.defaultdict(list)  
    for a, b, time in edges:  
        g[a].append((b, time))  
        g[b].append((a, time))  
      
    mintime = [float('inf')] * n  
    minfee = [float('inf')] * n  
      
    while h:  
        curfee, curtime, city = heappop(h)  
        if city == n - 1:  
            return curfee  
          
        for dst, time in g[city]:  
            fee = passingFees[dst]  
            if curtime + time > maxTime:  
                continue  
            if curtime + time < mintime[dst] or curfee + fee < minfee[dst]:  
                # Because the cities are arranged based on cost, the city with low cost will always be encountered first. The only way we will see the city the second time is when the time is smaller  
                heappush(h, (curfee + fee, curtime + time, dst))  
                mintime[dst] = curtime + time  
                minfee[dst] = curfee + fee 
                  
    return -1

2076. Process Restricted Friend Requests

You are given an integer n indicating the number of people in a network. Each person is labeled from 0 to n - 1.

You are also given a 0-indexed 2D integer array restrictions, where restrictions[i] = [xi, yi] means that person xi and person yi cannot become friends,either directly or indirectly through other people.

Initially, no one is friends with each other. You are given a list of friend requests as a 0-indexed 2D integer array requests, where requests[j] = [uj, vj] is a friend request between person uj and person vj.

A friend request is successful if uj and vj can be friends. Each friend request is processed in the given order (i.e., requests[j] occurs before requests[j + 1]), and upon a successful request, uj and vj become direct friends for all future friend requests.

Return a boolean array result, where each result[j] is true if the jth friend request is successful or false if it is not.

Note: If uj and vj are already direct friends, the request is still successful.

def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:          
    uf = UnionFind(n) 
        
    restrictions = set([tuple(x) for x in restrictions]) 
                
    for a, b in requests: 
        pa, pb = uf.find(a), uf.find(b) 
        copy = list(restrictions)  # This is an optimization to shorten the restriction list 
        for c, d in copy: 
            pc, pd = uf.find(c), uf.find(d) 
            restrictions.remove((c, d))  # Need to remove first then add in case (c, d)== (pc, pd) 
            restrictions.add((pc, pd)) 
            if (pa, pb) == (pc, pd) or (pa, pb) == (pd, pc): 
                res.append(False) 
                break 
        else: 
            res.append(True) 
            uf.union(a, b) 
                                
    return res

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different. It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Use dynamic programming

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:    
    dp = [[] for _ in range(target + 1)]  
    dp[0] = [[]] 
     
    for c in candidates: # It is not ok to reverse the inner and outer loop here
        for j in range(c, target + 1): 
            for x in dp[j - c]: 
                dp[j].append(x + [c]) 
                 
    return dp[-1]

Use backtrack

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: 
    stack = [] 
    res = [] 
    candidates.sort()  # Need to sort here
    def backtrack(remain, startidx): 
        for i in range(startidx, len(candidates)): 
            if candidates[i] > remain: 
                break
            elif candidates[i] == remain: 
                res.append(stack + [candidates[i]]) 
                break
            else: 
                stack.append(candidates[i]) 
                backtrack(remain - candidates[i], i) 
                stack.pop() 
                 
    backtrack(target, 0) 
    return res

51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

def solveNQueens(self, n: int) -> List[List[str]]: 
    def could_place(row, col): 
        return not (cols[col] + hill_diagonals[row - col] + dale_diagonals[row + col]) 
        
    def place_queen(row, col): 
        queens.add((row, col)) 
        cols[col] = 1 
        hill_diagonals[row - col] = 1 
        dale_diagonals[row + col] = 1 
        
    def remove_queen(row, col): 
        queens.remove((row, col)) 
        cols[col] = 0 
        hill_diagonals[row - col] = 0 
        dale_diagonals[row + col] = 0 
        
    def add_solution(): 
        solution = [] 
        for _, col in sorted(queens): 
            solution.append('.' * col + 'Q' + '.' * (n - col - 1)) 
        output.append(solution) 
        
    def backtrack(row = 0): 
        for col in range(n): 
            if could_place(row, col): 
                place_queen(row, col) 
                if row + 1 == n: 
                    add_solution() 
                else: 
                    backtrack(row + 1) 
                remove_queen(row, col) 
        
    cols = [0] * n 
    hill_diagonals = [0] * (2 * n - 1) 
    dale_diagonals = [0] * (2 * n - 1) 
    queens = set() 
    output = [] 
    backtrack() 
    return output

72. Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character

This is Levenshtein distance (https://en.wikipedia.org/wiki/Levenshtein_distance)

def minDistance(self, word1: str, word2: str) -> int: 
    m, n = len(word1), len(word2) 
        
    dp = [[0] * (n + 1) for _ in range(m + 1)] 
        
    for i in range(m + 1): 
        dp[i][0] = i 
            
    for j in range(n + 1): 
        dp[0][j] = j 
                
    for i in range(1, m + 1): 
        for j in range(1, n + 1): 
            if word1[i - 1] == word2[j - 1]: 
                dp[i][j] = dp[i - 1][j - 1] 
            else: 
                dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) 
                    
    return dp[-1][-1]

78. Subsets

Please check this link

97. Interleaving String

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ... Note: a + b is the concatenation of strings a and b.

A straightforward version

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        N1 = len(s1)
        N2 = len(s2)
        
        if N1 + N2 != len(s3):
            return False
        
        dp = [[False] * (N2 + 1) for _ in range(N1 + 1)]
                
        for i in range(N1 + 1):
            for j in range(N2 + 1):
                dp[i][j] = (i == j == 0) or \
                (i == 0 and dp[i][j - 1] and s2[j - 1] == s3[j - 1]) or \
                (j == 0 and dp[i - 1][j] and s1[i - 1] == s3[i - 1]) or \
                (i > 0 and dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or \
                (j > 0 and dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
                
        return dp[-1][-1]

A compact version

def isInterleave(self, s1, s2, s3): 
    r, c, l= len(s1), len(s2), len(s3) 
    if r+c != l: 
        return False 
    stack, visited = [(0, 0)], set((0, 0)) 
    while stack: 
        x, y = stack.pop() 
        if x+y == l: 
            return True 
        if x+1 <= r and s1[x] == s3[x+y] and (x+1, y) not in visited: 
            stack.append((x+1, y)); visited.add((x+1, y)) 
        if y+1 <= c and s2[y] == s3[x+y] and (x, y+1) not in visited: 
            stack.append((x, y+1)); visited.add((x, y+1)) 
    return False

188. Best Time to Buy and Sell Stock IV

def maxProfit(self, k: int, prices: List[int]) -> int: 
    # DP 
    # O(nk)time O(k)space 
    if k==0 or len(prices)<=1: 
        return 0 
    #Q2 Approach 3 
    if 2*k >= len(prices): 
        profit = 0 
        for i in range(1, len(prices)): 
            if prices[i]>prices[i-1]: 
                profit += prices[i]-prices[i-1] 
        return profit 
    #Q3 Approach 2 extension 
    costs = [float('inf')] * k 
    profits = [0] * k 
    costs[0] = prices[0] 
    for i in range(1, len(prices)): 
        for j in range(k): 
            if j==0: 
                costs[j] = min(costs[j], prices[i]) #buy  
                profits[j] = max(profits[j], prices[i]-costs[j]) #sell  
            else: 
                costs[j] = min(costs[j], prices[i]-profits[j-1]) #buy # the minimum cost for jth buy at location i 
                profits[j] = max(profits[j], prices[i]-costs[j]) #sell # the maximum cost for jth sell at location i 
    return profits[k-1]

Use Kadane's algorithm

def maxProfit(self, k: int, prices: List[int]) -> int: 
    N = len(prices) 
        
    if N <= 1: 
        return 0 
        
    if N <= 2 * k: 
        return sum([max(0, prices[i] - prices[i - 1]) for i in range(1, N)]) 
        
    pnl = [0] * N 
    price_diff = [prices[i] - prices[i - 1] for i in range(1, N)] 
        
    for _ in range(k): 
        val = 0 
        for i in range(1, N): 
            val = max(pnl[i], val + price_diff[i - 1]) 
            pnl[i] = max(pnl[i - 1], val) 
                
    return pnl[-1]

def maxProfit(self, k: int, prices: List[int]) -> int: 
    N = len(prices) 
        
    @cache 
    def partialMaxProfit(i, maxTimes): 
                    
        if N - i <= 1: 
            return 0 
            
        if maxTimes == 0: 
            return 0 
            
        if N - i <= 2 * maxTimes: 
            return sum([max(0, prices[j] - prices[j - 1]) for j in range(i + 1, N)]) 
            
        res = partialMaxProfit(i + 1, maxTimes) 
        for j in range(i + 1, N): 
            res = max(res, prices[j] - prices[i] + partialMaxProfit(j + 1, maxTimes - 1)) 
            
        return res 
            
    return partialMaxProfit(0, k)

282. Expression Add Operators

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

class Solution: 
    def addOperators(self, num, target): 
        self.res, self.target = [], target 
        self.num = num 
        self.N = len(self.num) 
        for i in range(1, len(num)+1): 
            if i == 1 or (i > 1 and num[0] != "0"): # prevent "00*" as a number 
                self.dfs(i, num[:i], int(num[:i]), int(num[:i])) # this step put first number in the string 
        return self.res 
    def dfs(self, idx, exp, cur, last): 
        N = self.N 
        if idx == N: 
            if cur == self.target: 
                self.res.append(exp) 
            return 
        for i in range(idx + 1, N + 1): 
            s = self.num[idx:i] 
            val = int(s) 
            if i == idx + 1 or (i > idx + 1 and self.num[idx] != "0"): # prevent "00*" as a number 
                self.dfs(i, exp + "+" + s, cur + val, val) 
                self.dfs(i, exp + "-" + s, cur - val, -val) 
                self.dfs(i, exp + "*" + s, cur - last + last * val, last * val)

309. Best Time to Buy and Sell Stock with Cooldown

State Machine Method

class Solution(object): 
    def maxProfit(self, prices): 
        """ 
        :type prices: List[int] 
        :rtype: int 
        """ 
        sold, held, reset = float('-inf'), float('-inf'), 0 
        for price in prices: 
            # Alternative: the calculation is done in parallel. 
            # Therefore no need to keep temporary variables 
            #sold, held, reset = held + price, max(held, reset-price), max(reset, sold) 
            pre_sold = sold 
            sold = held + price 
            held = max(held, reset - price) 
            reset = max(reset, pre_sold) 
        return max(sold, reset)

Dynamic Programming

class Solution(object): 
    def maxProfit(self, prices): 
        """ 
        :type prices: List[int] 
        :rtype: int 
        """ 
        L = len(prices) 
        # padding the array with additional zero to simply the logic 
        MP = [0] * (L + 2) 
        for i in range(L-1, -1, -1): 
            C1 = 0 
            # Case 1). buy and sell the stock 
            for sell in range(i + 1, L): 
                profit = (prices[sell] - prices[i]) + MP[sell + 2] 
                C1 = max(profit, C1) 
            # Case 2). do no transaction with the stock p[i] 
            C2 = MP[i + 1] 
            # sum up two cases 
            MP[i] = max(C1, C2) 
        return MP[0]

312. Burst Balloons

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

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

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) 
        def dp(left, right): 
            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)

322. Coin Change

You are given an integer array coinsrepresenting coins of different denominations and an integer amountrepresenting a total amount of money. Return 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. You may assume that you have an infinite number of each kind of coin.

def coinChange(self, coins: List[int], amount: int) -> int:
        inf = float('inf')
        dp = [inf] * (amount + 1)
        dp[0] = 0
        
        for i in range(len(dp)):
            for c in coins:
                if i - c < 0:
                    continue
                dp[i] = min(dp[i], 1 + dp[i - c])
                
        return dp[-1] if dp[-1] != inf else -1

410. Split Array Largest Sum

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Binary search

def splitArray(self, nums: List[int], m: int) -> int: 
    def canSplit(maxsum): 
        ct = 1 
        cur = nums[0] 
        for x in nums[1:]: 
            if x + cur > maxsum: 
                ct += 1 
                if ct > m: 
                    return False 
                cur = x 
            else: 
                cur += x 
                 
        return True 
     
    low = max(nums) 
    high = sum(nums) 
     
    res = float('inf') 
    while low <= high: 
        mid = low + (high - low) // 2 
        if canSplit(mid): 
            res = mid 
            high = mid - 1 
        else: 
            low = mid + 1 
             
    return res

dynamic programming or backtracking (high time complexity)

class Solution: 
    def splitArray(self, nums: List[int], m: int) -> int: 
        n = len(nums) 
        memo = [[0] * (m + 1) for _ in range(n)] 
         
        prefix_sum = [0] + list(itertools.accumulate(nums)) 
         
        for subarray_count in range(1, m + 1): 
            for curr_index in range(n): 
                # Base Case: If there is only one subarray left, then all of the remaining numbers 
                # must go in the current subarray. So return the sum of the remaining numbers. 
                if subarray_count == 1: 
                    memo[curr_index][subarray_count] = prefix_sum[n] - prefix_sum[curr_index] 
                    continue 
                # Otherwise, use the recurrence relation to determine the minimum largest subarray sum 
                # between curr_index and the end of the array with subarray_count subarrays remaining. 
                minimum_largest_split_sum = prefix_sum[n] 
                for i in range(curr_index, n - subarray_count + 1): 
                    # Store the sum of the first subarray. 
                    first_split_sum = prefix_sum[i + 1] - prefix_sum[curr_index] 
                    # Find the maximum subarray sum for the current first split. 
                    largest_split_sum = max(first_split_sum, memo[i + 1][subarray_count - 1]) 
                    # Find the minimum among all possible combinations. 
                    minimum_largest_split_sum = min(minimum_largest_split_sum, largest_split_sum) 
                    if first_split_sum >= minimum_largest_split_sum: 
                        break 
             
                memo[curr_index][subarray_count] = minimum_largest_split_sum 
         
        return memo[0][m]

489. Robot Room Cleaner

You are controlling a robot that is located somewhere in a room. The room is modeled as an m x n binary grid where 0 represents a wall and 1 represents an empty slot.

The robot starts at an unknown location in the root that is guaranteed to be empty, and you do not have access to the grid, but you can move the robot using the given API Robot.

You are tasked to use the robot to clean the entire room (i.e., clean every empty cell in the room). The robot with the four given APIs can move forward, turn left, or turn right. Each turn is 90 degrees.

When the robot tries to move into a wall cell, its bumper sensor detects the obstacle, and it stays on the current cell.

Design an algorithm to clean the entire room using the following APIs:

interface Robot { // returns true if next cell is open and robot moves into the cell. // returns false if next cell is obstacle and robot stays on the current cell. boolean move();

// Robot will stay on the same cell after calling turnLeft/turnRight. // Each turn will be 90 degrees. void turnLeft(); void turnRight();

// Clean the current cell. void clean(); }

def cleanRoom(self, robot): 
    """ 
    :type robot: Robot 
    :rtype: None 
    """ 
    def go_back(): 
        robot.turnRight() 
        robot.turnRight() 
        robot.move() 
        robot.turnRight() 
        robot.turnRight() 
            
    def backtrack(cell = (0, 0), d = 0): 
        visited.add(cell) 
        robot.clean() 
        # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left' 
        for i in range(4): 
            new_d = (d + i) % 4 
            new_cell = (cell[0] + directions[new_d][0], \ 
                        cell[1] + directions[new_d][1]) 
                
            if not new_cell in visited and robot.move(): 
                backtrack(new_cell, new_d) 
                go_back() 
            # turn the robot following chosen direction : clockwise 
            robot.turnRight() 
    
    # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left' 
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)] 
    visited = set() 
    backtrack()

516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

def longestPalindromeSubseq(self, s: str) -> int: 
    N = len(s) 
    dp = [[0] * N for _ in range(N)] 
    for i in range(N): 
        dp[i][i] = 1 
     
    for L in range(2, N + 1): 
        for i in range(N - L + 1): 
            j = i + L - 1 
            if s[i] == s[j]: 
                dp[i][j] = dp[i + 1][j - 1] +2 
            else: 
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 
                 
    return dp[0][-1]

518. Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

def change(self, amount: int, coins: List[int]) -> int: 
    dp = [0] * (amount + 1) 
    dp[0] = 1 
        
    for coin in coins: 
        for x in range(coin, amount + 1): 
            dp[x] += dp[x - coin] 
    return dp[amount]

629. K Inverse Pairs Array

For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].

Given two integers n and k, return the number of different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 109 + 7.

First version

@cache
def kInversePairs(self, n: int, k: int) -> int:
    M = 1000000007
    if n == 0:
        return 0
    if k == 0:
        return 1
    res = 0
    # first is the first value in the array
    for first in range(1, min(n + 1, k + 2)):
        res += self.kInversePairs(n - 1, k - first + 1) % M
    return res % M

Optimized based on this link

dp[n][k] = dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]+dp[n-1][k-n+1]
It's possible that some where in the right hand side the second array index become negative, since we cannot generate negative inverse pairs we just treat them as 0, but still leave the item there as a place holder.
dp[n][k] = dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]+dp[n-1][k-n+1]
dp[n][k+1] = dp[n-1][k+1]+dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n+1]
so by deducting the first line from the second line, we have dp[n][k+1] = dp[n][k]+dp[n-1][k+1]-dp[n-1][k+1-n]

@cache
def kInversePairs(self, n: int, k: int) -> int:
    M = 1000000007
    if n == 0:
        return 0
    if n == 1 and k > 0:
        return 0
    if k == 0:
        return 1
    if k < 0:
        return 0
    return (self.kInversePairs(n, k - 1) + self.kInversePairs(n - 1, k) - self.kInversePairs(n - 1, k - n)) % M

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.

def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: 
    target = sum(nums) // k 
    nums.sort(reverse=True) 
    if sum(nums) % k > 0: 
        return False 
     
    if nums[0] > target: 
        return False 
     
    groupsum = [0] * k 
    found = False 
     
    def backtrack(idx): 
        nonlocal found 
         
        if found: 
            return 
                    
        for i in range(k): 
            if found: 
                return 
             
            if nums[idx] + groupsum[i] <= target: 
                groupsum[i] += nums[idx] 
                if idx == len(nums) - 1: 
                    found = True 
                    return 
                 
                backtrack(idx + 1) 
                 
                groupsum[i] -= nums[idx] 
                 
                if groupsum[i] == 0: 
                    break 
                     
    backtrack(0)     
    return found

714. Best Time to Buy and Sell Stock with Transaction Fee

State Machine

class Solution: 
    def maxProfit(self, prices, fee): 
        hold = -prices[0] 
        unhold = 0 
         
        for price in prices: 
            hold_old = hold 
            hold = max(hold, unhold - price) 
            unhold = max(hold_old + price - fee, unhold) 
             
        return unhold

Simulation

class Solution:
    def maxProfit(self, prices, fee):
        n = len(prices)
        if n < 2:
             return 0
        ans = 0
        minimum = prices[0]
        for i in range(1, n):
            if prices[i] < minimum:
                minimum = prices[i]

            elif prices[i] > minimum + fee:
                ans += prices[i] - fee - minimum
                minimum = prices[i] - fee

        return ans

718. Maximum Length of Repeated Subarray

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

def findLength(self, A, B):
    memo = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
    for i in range(len(A) - 1, -1, -1):
        for j in range(len(B) - 1, -1, -1):
            if A[i] == B[j]:
                memo[i][j] = memo[i + 1][j + 1] + 1
    return max(max(row) for row in memo)

Rolling hash

def findLength(self, nums1: List[int], nums2: List[int]) -> int: 
    m, n = len(nums1), len(nums2) 
    BASE, MOD = 101, 1_000_000_000_001 
    hash1, hash2, POW = [0] * (m + 1), [0] * (n + 1), [1] * (max(m, n) + 1) 
    for i in range(max(m, n)): POW[i + 1] = POW[i] * BASE % MOD  # Compute POW of BASE 
    for i in range(m): hash1[i + 1] = (hash1[i] * BASE + nums1[i]) % MOD  # Compute hashing values of nums1 
    for i in range(n): hash2[i + 1] = (hash2[i] * BASE + nums2[i]) % MOD  # Compute hashing values of nums2 
    def getHash(h, left, right):  # 0-based indexing, right inclusive 
        return (h[right + 1] - h[left] * POW[right - left + 1] % MOD + MOD) % MOD 
    def foundSubArray(size): 
        seen = defaultdict(list) 
        for i in range(m - size + 1): 
            h = getHash(hash1, i, i + size - 1) 
            seen[h].append(i) 
        for i in range(n - size + 1): 
            h = getHash(hash2, i, i + size - 1) 
            if h in seen: 
                for j in seen[h]:  # Double check - This rarely happens when collision occurs -> No change in time complexity 
                    if nums1[j:j + size] == nums2[i:i + size]: 
                        return True 
        return False 
    left, right, ans = 1, min(m, n), 0 
    while left <= right: 
        mid = (left + right) // 2 
        if foundSubArray(mid): 
            ans = mid  # Update answer 
            left = mid + 1  # Try to expand size 
        else: 
            right = mid - 1  # Try to shrink size 
    return ans

740. Delete and Earn

You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:

Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1. Return the maximum number of points you can earn by applying the above operation some number of times.

def deleteAndEarn(self, nums: List[int]) -> int: 
    m = max(nums) 
    cum = [0] * (m + 1) 
    for x in nums: 
        cum[x] += x 
        
    two_back, one_back = 0, cum[1] 
        
    for i in range(2, m + 1): 
        two_back, one_back = one_back, max(one_back, two_back + cum[i]) 
    return one_back

818. Race Car

Your car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions 'A' (accelerate) and 'R' (reverse):

When you get an instruction 'A', your car does the following: position += speed speed *= 2 When you get an instruction 'R', your car does the following: If your speed is positive then speed = -1 otherwise speed = 1 Your position stays the same. For example, after commands "AAR", your car goes to positions 0 --> 1 --> 3 --> 3, and your speed goes to 1 --> 2 --> 4 --> -1.

Given a target position target, return the length of the shortest sequence of instructions to get there.

Dynamic Programming with breadth-first search

class Solution:
    def racecar(self, target: int) -> int:
        dist = {(0, 1): 0}
        
        from collections import deque
        
        dq = deque([(0, 1)])
        
        while dq:
            pos, speed = dq.popleft()
            if pos == target:
                return dist[(pos, speed)]
            neighbors = [(pos, -speed // abs(speed)), (pos + speed, 2 * speed)]
            for nei in neighbors:
                if nei not in dist:
                    dq.append(nei)
                    dist[nei] = dist[(pos, speed)] + 1

Dynamic Programming combined with Greedy (Time O(TlogT), Space O(T))

class Solution:
    @cache
    def racecar(self, target: int) -> int:
        n = target.bit_length()
        
        # Just use consecutive A and you will get there
        if (target + 1) & target == 0:  # This is the binary trick to see if target + 1 is a power of 2
            return n
        
        # Go past the target, then come back.
        result = self.racecar(2 ** n - 1 - target) + n + 1 # The "n" mean first use n consecutive A, then "1" means use 1 R
        
        # Go as long as you do not pass the target. Then come back several steps. Then go ahead.
        for m in range(n - 1):
            result = min(result,  + self.racecar(target - (2 ** (n - 1) - 2 ** m)) + n - 1 + 1 + m + 1) # The "n - 1" means first use (n - 1) A, then use 1 R, then use m A, m will be smaller than n - 1, then use 1 R
        
        return result

1320. Minimum Distance to Type a Word Using Two Fingers

def minimumDistance(self, word: str) -> int: 
    orda = ord('A') 
    pos = {} 
    for i in range(26): 
        pos[chr(orda + i)] = divmod(i, 6) 
         
    N = len(word) 
     
    def dist(i, j): 
        if i == 0 or j == 0: 
            return 0 
        a, b = word[i - 1], word[j - 1] 
        i1, j1 = pos[a] 
        i2, j2 = pos[b] 
        return abs(i1 - i2) + abs(j1 - j2) 
     
    dp = [[0] * (N + 1) for _ in range(N + 1)] 
     
    # Because of symmetry, dp[i][j] represent the minimum total distance when the current position is at i (so one finger must be at i-th letter) and another figure is at j-th letter. Here we label the first letter in the sequence as 1. So the maximum value of i is N. 0 is reserved for the initial state. 
    # The distance value become positive only from the 2nd letter 
    for i in range(2, N + 1): 
        c = word[i - 1] 
         
        # To get to the state of (i, j) where j = 0, 1, ..., i - 2, the only possible way is to move from the figure at i - 1 to i  
        for j in range(i - 1): 
            dp[i][j] = dp[i - 1][j] + dist(i, i - 1) 
        # To get to the state of (i, i - 1), the last state can be (i - 1, k) where k can be 0, 1, ..., i - 2  
        dp[i][i - 1] = min([(dp[i - 1][k] + dist(i, k)) for k in range(i - 1)]) 
         
    # dp[N][N] is not a valid state 
    return min(dp[-1][:N])

1340. Jump Game V

Given an array of integers arr and an integer d. In one step you can jump from index i to index:

i + x where: i + x < arr.length and 0 < x <= d.
i - x where: i - x >= 0 and 0 < x <= d. In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).

You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        stack = []
        
        dp = [1] * (len(arr) + 1)
        
        for i, v in enumerate(arr + [float('inf')]):
            # This is using "<", not "<=", because if there are several same numbers, others can jump to either of them and either has a chance to be the optimal step. For different numbers within range, it is always good to jump to a larger number
            while stack and arr[stack[-1]] < v:
                last = stack.pop()
                L = [last]
                while stack and arr[stack[-1]] == arr[last]:
                    L.append(stack.pop())
                
                for j in L:
                    if i - j <= d:
                        dp[i] = max(dp[i], dp[j] + 1)
                
                    if stack and j - stack[-1] <= d:
                        dp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)
            stack.append(i)
                    
        dp[-1] = 0
        return max(dp)

1799. Maximize Score After N Operations

You are given nums, an array of positive integers of size 2 * n. You must perform n operations on this array.

In the ith operation (1-indexed), you will:

Choose two elements, x and y.
Receive a score of i * gcd(x, y).
Remove x and y from nums.
Return the maximum score you can receive after performing n operations.

The function gcd(x, y) is the greatest common divisor of x and y.

def maxScore(self, nums: List[int]) -> int:
    @lru_cache(None)
    def gcd(x, y):
        if x < y:
            x, y = y, x
        
        while True:
            if x % y == 0:
                return y
            x, y = y, x % y
        
    def setbit(x, n): # Cannot directly set because int is immutable
        return x | 1 << n
        
    def getbit(x, n):
        return 1 & (x >> n)
    
    @lru_cache(None)
    def dfs(mask, seq):
        if seq == len(nums) // 2 + 1:
            return 0
        res = 0
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if getbit(mask, i) == 0 and getbit(mask, j) == 0:
                    newmask = setbit(setbit(mask, i), j)
                    res = max(res, gcd(nums[i], nums[j]) * seq + dfs(newmask, seq + 1))
        
        return res
        
        return dfs(0, 1)

1931. Painting a Grid With Three Different Colors

You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted.

Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 109 + 7.

A detailed version

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        from collections import defaultdict
        MOD = 1000000007

        table = ['123', '132', '213', '231', '312', '321']

        def createByTable(s):
            for t in table:
                res = []
                for c in s:
                    res.append(t[ord(c) - ord('1')])
                yield ''.join(res)

        def compatible(s1, s2):
            for c1, c2 in zip(s1, s2):
                if c1 == c2:
                    return False
            return True

        if m == 1:
            return 3 * 2 ** (n - 1) % MOD

        elif m == 2:
            patterns = ['12']
            # return 6 * 3 ** (n - 1) % MOD

        elif m == 3:
            patterns = ['121', '123']

            # a121, a123 = 6, 6
            # for i in range(n - 1):
            # a121, a123 = a121 * 3 + a123 * 2, a121 * 2 + a123 * 2
            # return (a121 + a123) % mod

        elif m == 4:
            patterns = ['1212', '1213', '1231', '1232']

        elif m == 5:
            patterns = ['12121', '12123', '12131', '12132', '12312', '12313', '12321', '12323']

        d = defaultdict(int)

        for p in patterns:
            d[p] = 6

        stringsByPattern = defaultdict(list)
        for p in patterns:
            stringsByPattern[p] = list(createByTable(p))
            # print(p, stringsByPattern[p])

        N = len(patterns)

        matrix = [[0] * N for _ in range(N)]

        for i in range(N):
            for j in range(N):
                pat1 = stringsByPattern[patterns[i]][0]
                for pat2 in stringsByPattern[patterns[j]]:
                    if compatible(pat1, pat2):
                        matrix[i][j] += 1

        for i in range(n - 1):
            dcopy = d.copy()
            d.clear()
            for j in range(N):
                for i in range(N):
                    d[patterns[j]] += matrix[i][j] * dcopy[patterns[i]]

        return sum(d.values()) % MOD

A concise version

class Solution: 
    def colorTheGrid(self, m, n): 
        C = [c for c in product([0,1,2], repeat = m) if all(x!=y for x,y in zip(c, c[1:]))] 
        MOD, dp, d = 10**9 + 7, Counter(C), defaultdict(list) 
        for c1, c2 in product(C, C): 
            if all(x != y for x, y in zip(c1, c2)): 
                d[c1].append(c2) 
        for _ in range(n-1): 
            dp2 = Counter() 
            for c1 in C: 
                for c2 in d[c1]: 
                    dp2[c2] = (dp2[c2] + dp[c1]) % MOD 
            dp = dp2 
        return sum(dp.values()) % MOD

1937. Maximum Number of Points with Cost

You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix.

To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score.

However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score.

Return the maximum number of points you can achieve.

def maxPoints(self, points: List[List[int]]) -> int:
    m, n = len(points), len(points[0])
    
    dp_prev = points[0]
    dp = [0] * n
    
    for r in range(1, m):            
        leftMax = [dp_prev[0]]
        for i in range(1, n):
            leftMax.append(max(dp_prev[i], leftMax[-1] - 1))
        
        rightMax = [dp_prev[-1]]
        for i in range(n - 2, -1, -1):
            rightMax.append(max(dp_prev[i], rightMax[-1] - 1))
        rightMax = rightMax[::-1]
        
        for i in range(n):
            dp[i] = max(leftMax[i], rightMax[i]) + points[r][i]
                
        dp_prev = dp[:]
    return max(dp_prev)

1997. First Day Where You Have Been in All the Rooms

There are n rooms you need to visit, labeled from 0 to n - 1. Each day is labeled, starting from 0. You will go in and visit one room a day.

Initially on day 0, you visit room 0. The order you visit the rooms for the coming days is determined by the following rules and a given 0-indexed array nextVisit of length n:

Assuming that on a day, you visit room i,
if you have been in room i an odd number of times (including the current visit), on the next day you will visit the room specified by nextVisit[i] where 0 <= nextVisit[i] <= i;
if you have been in room i an even number of times (including the current visit), on the next day you will visit room (i + 1) mod n.

Return the label of the first day where you have been in all the rooms. It can be shown that such a day exists. Since the answer may be very large, return it modulo 109 + 7.

class Solution: 
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int: 
        M = 1000000007 
        dp = [0] * len(nextVisit) # The first day to reach i 
         
        for i in range(1, len(nextVisit)): 
            dp[i] = (2 * dp[i - 1] - dp[nextVisit[i - 1]] + 2) % M 
         
        return dp[-1] % M

29. Divide Two Integers

def divide(self, dividend: int, divisor: int) -> int: 
    # Constants. 
    MAX_INT = 2147483647        # 2**31 - 1 
    MIN_INT = -2147483648       # -2**31 
    HALF_MIN_INT = -1073741824  # MIN_INT // 2 
    # Special case: overflow. 
    if dividend == MIN_INT and divisor == -1: 
        return MAX_INT 
    # We need to convert both numbers to negatives. 
    # Also, we count the number of negatives signs. 
    negatives = 2 
    if dividend > 0: 
        negatives -= 1 
        dividend = -dividend 
    if divisor > 0: 
        negatives -= 1 
        divisor = -divisor 
    # In the first loop, we simply find the largest double of divisor 
    # that fits into the dividend. 
    # The >= is because we're working in negatives. In essence, that 
    # piece of code is checking that we're still nearer to 0 than we 
    # are to INT_MIN. 
    highest_double = divisor 
    highest_power_of_two = -1 
    while highest_double >= HALF_MIN_INT and dividend <= highest_double + highest_double: 
        highest_power_of_two += highest_power_of_two 
        highest_double += highest_double 
    # In the second loop, we work out which powers of two fit in, by 
    # halving highest_double and highest_power_of_two repeatedly. 
    # We can do this using bit shifting so that we don't break the 
    # rules of the question :-) 
    quotient = 0 
    while dividend <= divisor: 
        if dividend <= highest_double: 
            quotient += highest_power_of_two 
            dividend -= highest_double 
        # We know that these are always even, so no need to worry about the 
        # annoying "bit-shift-odd-negative-number" case. 
        highest_power_of_two >>= 1 
        highest_double >>= 1 
    # If there was originally one negative sign, then 
    # the quotient remains negative. Otherwise, switch 
    # it to positive. 
    return quotient if negatives == 1 else -quotient

67. Add Binary

Given two binary strings a and b, return their sum as a binary string.

def addBinary(self, a, b) -> str: 
    x, y = int(a, 2), int(b, 2) 
    while y: 
        x, y = x ^ y, (x & y) << 1 
    return bin(x)[2:]

136. Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. Implement a solution with a linear runtime complexity and without using extra memory.

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

137. Single Number II

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

See this post.

260. Single Number III

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        auto temp = 0;
        for (auto num : nums)
            temp = temp ^ num;
        
        int position = temp & (-temp);
        
        int ans1 = 0;
        
        for (auto num : nums)
        {
            if (position & num)
            {
                ans1 = ans1 ^ num;
            }
        }
        
        return vector<int>{ans1, ans1 ^ temp};
    }
};

1401. Circle and Rectangle Overlapping

You are given a circle represented as (radius, xCenter, yCenter) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the rectangle.

Return true if the circle and rectangle are overlapped otherwise return false. In other words, check if there is any point (xi, yi) that belongs to the circle and the rectangle at the same time.

def checkOverlap(self, radius: int, x_center: int, y_center: int, x1: int, y1: int, x2: int, y2: int) -> bool: 
        
    if x1 <= x_center <= x2: 
        distx = 0 
    else: 
        distx = min(abs(x1 - x_center), abs(x2 - x_center)) 
            
    if y1 <= y_center <= y2: 
        disty = 0 
    else: 
        disty = min(abs(y1 - y_center), abs(y2 - y_center)) 
            
    return distx **2 + disty ** 2 <= radius ** 2

1242. Web Crawler Multithreaded

Given a url startUrl and an interface HtmlParser, implement a Multi-threaded web crawler to crawl all links that are under the same hostname as startUrl.

Return all urls obtained by your web crawler in any order.

Your crawler should:

Start from the page: startUrl
Call HtmlParser.getUrls(url) to get all urls from a webpage of given url.
Do not crawl the same link twice.
Explore only the links that are under the same hostname as startUrl.

As shown in the example url above, the hostname is example.org. For simplicity sake, you may assume all urls use http protocol without any port specified. For example, the urls http://leetcode.com/problems and http://leetcode.com/contest are under the same hostname, while urls http://example.org/test and http://example.com/abc are not under the same hostname.

The HtmlParser interface is defined as such:

interface HtmlParser { // Return a list of all urls from a webpage of given url. // This is a blocking call, that means it will do HTTP request and return when this request is finished. public List getUrls(String url); } Note that getUrls(String url) simulates performing a HTTP request. You can treat it as a blocking function call which waits for a HTTP request to finish. It is guaranteed that getUrls(String url) will return the urls within 15ms. Single-threaded solutions will exceed the time limit so, can your multi-threaded web crawler do better?

Follow up:

Assume we have 10,000 nodes and 1 billion URLs to crawl. We will deploy the same software onto each node. The software can know about all the nodes. We have to minimize communication between machines and make sure each node does equal amount of work.

How would your web crawler design change?
What if one node fails or does not work?
How do you know when the crawler is done?

from concurrent import futures

class Solution:
    def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
        hostname = lambda url: url.split('/')[2]
        seen = {startUrl}
    
        with futures.ThreadPoolExecutor(max_workers=16) as executor:
            tasks = deque([executor.submit(htmlParser.getUrls, startUrl)])
            while tasks:
                for url in tasks.popleft().result():
                    if url not in seen and hostname(startUrl) == hostname(url):
                        seen.add(url)
                        tasks.append(executor.submit(htmlParser.getUrls, url))
        
        return list(seen)

class Solution { 
public: 
    string get_hostname(const string& url) 
    { 
        int start = url.find("/") + 2; 
        int end = url.find("/", start); 
        if (end == string::npos) 
        { 
            return url.substr(start); 
        } 
        else 
        { 
            return url.substr(start, end - start); 
        } 
    } 
     
    void work(HtmlParser& htmlParser) 
    { 
        while (true) 
        { 
            unique_lock<mutex> lk(m); 
            cv.wait(lk, [&](){ 
                return done || !s.empty(); 
                }); 
            if (done) 
            { 
                return; 
            } 
            string cur = s.top(); 
            s.pop(); 
            working++; 
            lk.unlock(); 
            cv.notify_all(); 
            vector<string> urls = htmlParser.getUrls(cur); 
             
            lk.lock(); 
            for (const auto& url : urls) 
            { 
                if (target_hostname == get_hostname(url) && seen.find(url) == seen.end()) 
                { 
                    seen.insert(url); 
                    s.push(url); 
                } 
            } 
             
            working--; 
            if (working == 0 && s.empty()) 
            { 
                done = true; 
            } 
             
            lk.unlock(); 
            cv.notify_all(); 
        } 
    } 
     
    vector<string> crawl(string startUrl, HtmlParser htmlParser) { 
         
        seen.insert(startUrl); 
        s.push(startUrl); 
        target_hostname = get_hostname(startUrl); 
         
        vector<thread> threads; 
        int num_threads = 16; 
         
        for (size_t i = 0; i < num_threads; ++i) 
        { 
            threads.emplace_back(&Solution::work, this, ref(htmlParser));
        } 
         
        for (size_t i = 0; i < num_threads; ++i) 
        { 
            threads[i].join(); 
        } 
         
        return vector(seen.begin(), seen.end()); 
    } 
private: 
    mutex m; 
    int working = 0; 
    bool done = false;     
    condition_variable cv; 
    stack<string> s; 
    unordered_set<string> seen; 
    string target_hostname{}; 
};

398. Random Pick Index

Given an integer array nums with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Implement the Solution class:

Solution(int[] nums) Initializes the object with the array nums.
int pick(int target) Picks a random index i from nums where nums[i] == target. If there are multiple valid i's, then each index should have an equal probability of returning.

Reservoir Sampling

def __init__(self, nums): 
    self.nums = nums 
     
def pick(self, target): 
    res = None 
    count = 0 
    for i, x in enumerate(self.nums): 
        if x == target: 
            count += 1 
            chance = random.randint(1, count) 
            if chance == count: 
                res = i 
    return res

587. Erect the Fence

You are given an array trees where trees[i] = [xi, yi] represents the location of a tree in the garden.

You are asked to fence the entire garden using the minimum length of rope as it is expensive. The garden is well fenced only if all the trees are enclosed.

Return the coordinates of trees that are exactly located on the fence perimeter.

Convex Hull

def outerTrees(self, trees: List[List[int]]) -> List[List[int]]: 
    def ccw(p1, p2, p3): 
        v1x = p2[0] - p1[0] 
        v1y = p2[1] - p1[1] 
        v2x = p3[0] - p2[0] 
        v2y = p3[1] - p2[1] 
            
        res = (v1x * v2y - v2x * v1y)  
        if res > 0: 
            return 1 
        elif res == 0: 
            return 0 
        else: 
            return -1 
        
    trees.sort() 
        
    def compute_hull(target): 
        upper = [] 
        for i in range(len(trees)): 
            upper.append(i) 
            while len(upper) >= 3 and ccw(trees[upper[-3]], trees[upper[-2]], trees[upper[-1]]) not in target: 
                last = upper.pop() 
                upper.pop() 
                upper.append(last) 
                
        return upper 
        
    upper = compute_hull([0, -1]) 
    lower = compute_hull([0, 1]) 
        
    lower.reverse() 
                    
    return [trees[i] for i in set(upper + lower[1:-1])]

GitHub Useful Repos

===================

Most Starred List

CS Learning Materials

doocs / technical-books

😆 国内外互联网技术大牛们都写了哪些书籍：计算机基础、网络、前端、后端、数据库、架构、大数据、深度学习...

Developer-Y / cs-video-course

List of Computer Science courses with video lectures.

sdmg15 / Best-websites-a-programmer-should-visit

🔗 Some useful websites for programmers.

ossu / computer-science

🎓 Path to a free self-taught education in Computer Science!

freeCodeCamp / freeCodeCamp

freeCodeCamp.org's open-source codebase and curriculum. Learn to code for free.

CyC2018 / CS-Notes

📚 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计

bregman-arie / devops-exercises

Linux, Jenkins, AWS, SRE, Prometheus, Docker, Python, Ansible, Git, Kubernetes, Terraform, OpenStack, SQL, NoSQL, Azure, GCP, DNS, Elastic, Network, Virtualization. DevOps Interview Questions

EbookFoundation / free-programming-books

📚 Freely available programming books

kamranahmedse / developer-roadmap

Roadmap to becoming a web developer in 2021

jwasham / coding-interview-university

A complete computer science study plan to become a software engineer.

imarvinle / awesome-cs-books

经典编程书籍大全，涵盖：计算机系统与网络、系统架构、算法与数据结构、前端开发、后端开发、移动开发、数据库、测试、项目与团队、程序员职业修炼、求职面试等

Cheat Sheets

LeCoupa / awesome-cheatsheets

👩‍💻👨‍💻 Awesome cheatsheets for popular programming languages, frameworks and development tools. They include everything you should know in one single file.

ikatyang / emoji-cheat-sheet

A markdown version emoji cheat sheet

FavioVazquez / ds-cheatsheets

List of Data Science Cheatsheets to rule the world

Engineering Practices

google / eng-practices

Google's Engineering Practices documentation

Front End, Back End, Full Stack

microsoft / Web-Dev-For-Beginners

24 Lessons, 12 Weeks, Get Started as a Web Developer

frank-lam / fullstack-tutorial

🚀 fullstack tutorial 2021，后台技术栈/架构师之路/全栈开发社区，春招/秋招/校招/面试

xingshaocheng / architect-awesome

后端架构师技术图谱

yongxinz / backend-interview

后端面试题汇总（Python、Redis、MySQL、PostgreSQL、Kafka、数据结构、算法、编程、网络）

phodal / growth-ebook

Growth Engineering: The Definitive Guide。全栈增长工程师指南

LeetCode & Algorithms

labuladong / fucking-algorithm

刷算法全靠套路，认准 labuladong 就够了！English version supported! Crack LeetCode, not only how, but also why.

youngyangyang04 / leetcode-master

LeetCode 刷题攻略：200道经典题目刷题顺序，共60w字的详细图解，视频难点剖析，50余张思维导图，支持C++，Java，Python，Go，JavaScript等多语言版本，从此算法学习不再迷茫！🔥🔥 来看看，你会发现相见恨晚！🚀

keon / algorithms

Minimal examples of data structures and algorithms in Python

TheAlgorithms / Python

All Algorithms implemented in Python

TheAlgorithms / C++

All Algorithms implemented in C++

TheAlgorithms

All Algorithms implemented in different languages

MisterBooo / LeetCodeAnimation

Demonstrate all the questions on LeetCode in the form of animation.（用动画的形式呈现解LeetCode题目的思路）

gzc / CLRS

📓Solutions to Introduction to Algorithms

trekhleb / javascript-algorithms

📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings

halfrost / LeetCode-Go

✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% / LeetCode 题解

Learn Design Patterns

DovAmir / awesome-design-patterns

Unstar

A curated list of software and architecture related design patterns.

iluwatar / java-design-patterns

Design patterns implemented in Java

Interview Preparation

viraptor / reverse-interview

Questions to ask the company during your interview

awesome-interview-questions

A curated list of lists of technical interview questions.

Resources

huggingface / datasets

🤗 The largest hub of ready-to-use datasets for ML models with fast, easy-to-use and efficient data manipulation tools

chinese-poetry / chinese-poetry

The most comprehensive database of Chinese poetry 🧶最全中华古诗词数据库, 唐宋两朝近一万四千古诗人, 接近5.5万首唐诗加26万宋诗. 两宋时期1564位词人，21050首词。

public-apis / public-apis

A collective list of free APIs

Learn C++

huihut / interview

📚 C/C++ 技术面试基础知识总结，包括语言、程序库、数据结构、算法、系统、网络、链接装载库等知识及面试经验、招聘、内推等信息。This repository is a summary of the basic knowledge of recruiting job seekers and beginners in the direction of C/C++ technology, in…

jobbole / awesome-cpp-cn

C++ 资源大全中文版，标准库、Web应用框架、人工智能、数据库、图片处理、机器学习、日志、代码分析等。由「开源前哨」和「CPP开发者」微信公号团队维护更新。

Learn Python

jackfrued / Python-100-Days

Python - 100天从新手到大师

Pierian-Data / Complete-Python-3-Bootcamp

Course Files for Complete Python 3 Bootcamp Course on Udemy

maicss / PyQt5-Chinese-tutorial

PyQt5中文教程

PyQt5 / PyQt

PyQt Examples（PyQt各种测试和例子） PyQt4 PyQt5

pyqt / examples

Learn to create a desktop app with Python and Qt

nedbat / byterun

A Python implementation of a Python bytecode runner

pythonguis / 15-minute-apps

15 minute (small) desktop apps built with PyQt

mpld3 / mpld3

D3 Renderings of Matplotlib Graphics

Learn Java

hollischuang / toBeTopJavaer

To Be Top Javaer - Java工程师成神之路

itwanger / JavaBooks

Java 程序员常读书单整理，附下载地址，助力构建最强知识体系。但不限于 Java，包括设计模式、计算机网络、操作系统、数据库、数据结构与算法、大数据、架构、面试等等。

dunwu / javacore

☕ JavaCore 是对 Java 核心技术的经验总结。

DuGuQiuBai / Java

27天成为Java大神

Snailclimb / JavaGuide

「Java学习+面试指南」一份涵盖大部分 Java 程序员所需要掌握的核心知识。准备 Java 面试，首选 JavaGuide！

doocs / advanced-java

😮 Core Interview Questions & Answers For Experienced Java(Backend) Developers | 互联网 Java 工程师进阶知识完全扫盲：涵盖高并发、分布式、高可用、微服务、海量数据处理等领域知识

doocs / source-code-hunter

😱 从源码层面，剖析挖掘互联网行业主流技术的底层实现原理，为广大开发者 “提升技术深度” 提供便利。目前开放 Spring 全家桶，Mybatis、Netty、Dubbo 框架，及 Redis、Tomcat 中间件等

Learn Linux

jlevy / the-art-of-command-line

Master the command line, in one page

ohmyzsh / ohmyzsh

A delightful community-driven (with 1900+ contributors) framework for managing your zsh configuration. Includes 300+ optional plugins (rails, git, OSX, hub, docker, homebrew, node, php, python, e…

Learn AWS

open-guides / og-aws

📙 Amazon Web Services — a practical guide

awsdocs / aws-doc-sdk-examples

Welcome to the AWS Code Examples Repository. This repo contains code examples used in the AWS documentation, AWS SDK Developer Guides, and more. For more information, see the Readme.rst file below.

donnemartin / awesome-aws

A curated list of awesome Amazon Web Services (AWS) libraries, open source repos, guides, blogs, and other resources. Featuring the Fiery Meter of AWSome.

aws / aws-cdk

The AWS Cloud Development Kit is a framework for defining cloud infrastructure in code

aws / serverless-application-model

AWS Serverless Application Model (SAM) is an open-source framework for building serverless applications

aws / aws-cli

Universal Command Line Interface for Amazon Web Services

Learn Docker

https://github.com/veggiemonk/awesome-docker

Classical Projects

torvalds / linux

Linux kernel source tree

protocolbuffers / protobuf

Protocol Buffers - Google's data interchange format

facebook / folly

An open-source C++ library developed and used at Facebook.

spring-projects / spring-boot

Spring Boot

google / googletest

GoogleTest - Google Testing and Mocking Framework

microsoft / terminal

The new Windows Terminal and the original Windows console host, all in the same place!

godotengine / godot

Godot Engine – Multi-platform 2D and 3D game engine

google / leveldb

LevelDB is a fast key-value storage library written at Google that provides an ordered mapping from string keys to string values.

telegramdesktop / tdesktop

Telegram Desktop messaging app

jupyter / jupyter

Jupyter metapackage for installation, docs and chat

ipython / ipython

Official repository for IPython itself. Other repos in the IPython organization contain things like the website, documentation builds, etc.

Project Ideas & Lists

florinpop17 / app-ideas

A Collection of application ideas which can be used to improve your coding skills.

practical-tutorials / project-based-learning

Curated list of project-based tutorials

Python-World / python-mini-projects

A collection of simple python mini projects to enhance your python skills

CharlesPikachu / Games

Create interesting games by pure python.

sindresorhus / awesome

😎 Awesome lists about all kinds of interesting topics

aosabook / 500lines

500 Lines or Less

danistefanovic / build-your-own-x

🤓 Build your own (insert technology here)

mahmoud / awesome-python-applications

💿 Free software that works great, and also happens to be open-source Python.

Projects

neozhaoliang / pywonderland

A tour in the wonderland of math with python.

willmcgugan / textual

Textual is a TUI (Text User Interface) framework for Python inspired by modern web development.

PeterL1n / RobustVideoMatting

Robust Video Matting in PyTorch, TensorFlow, TensorFlow.js, ONNX, CoreML!

microsoft / muzic

Muzic: Music Understanding and Generation with Artificial Intelligence

GitbookIO / gitbook

📝 Modern documentation format and toolchain using Git and Markdown

babysor / MockingBird

🚀AI拟声: 5秒内克隆您的声音并生成任意语音内容 Clone a voice in 5 seconds to generate arbitrary speech in real-time

sherlock-project / sherlock

🔎 Hunt down social media accounts by username across social networks

hardikvasa / google-images-download

Python Script to download hundreds of images from 'Google Images'. It is a ready-to-run code!

marceloprates / prettymaps

A small set of Python functions to draw pretty maps from OpenStreetMap data. Based on osmnx, matplotlib and shapely libraries.

PaddlePaddle / PaddleOCR

Awesome multilingual OCR toolkits based on PaddlePaddle （practical ultra lightweight OCR system, support 80+ languages recognition, provide data annotation and synthesis tools, support training and…

Anuken / Mindustry

A sandbox tower defense game (Java)

😮python模拟登陆一些大型网站，还有一些简单的爬虫，希望对你们有所帮助❤️，如果喜欢记得给个star哦🌟

yemount / pose-animator

CorentinJ / Real-Time-Voice-Cloning

Clone a voice in 5 seconds to generate arbitrary speech in real-time

lava / matplotlib-cpp

Extremely simple yet powerful header-only C++ plotting library built on the popular matplotlib

Code Snippets

30-seconds / 30-seconds-of-code

Short JavaScript code snippets for all your development needs

geekcomputers / Python

My Python Examples

CharlesPikachu / Tools

Some useful tools written in python.

CoreyMSchafer / code_snippets

Computational Geometry & Vision & Graphics

jslee02 / awesome-graphics-libraries

😎 A curated list of 3D graphics libraries and resources

cnr-isti-vclab / PyMeshLab

The open source mesh processing python library

cnr-isti-vclab / vcglib

The VCGlib is a C++, templated, no dependency, library for manipulation, processing and cleaning of triangle meshes

kroitor / gjk.c

Gilbert-Johnson-Keerthi (GJK) collision detection algorithm in 200 lines of clean plain C

nschloe / pygalmesh

🕸️ A Python interface to CGAL's meshing tools

pyvista / tetgen

A Python interface to the C++ TetGen library to generate tetrahedral meshes of any 3D polyhedral domains

nschloe / meshio

🕸️ input/output for many mesh formats

kornia / kornia

Open Source Differentiable Computer Vision Library

nschloe / pygmsh

🕸️ Gmsh for Python

inducer / meshpy

2D/3D simplicial mesh generator interface for Python (Triangle, TetGen, gmsh)

taichi-dev / taichi

Parallel programming for everyone.

pmp-library / pmp-library

The Polygon Mesh Processing Library

davidstutz / mesh-voxelization

C++ implementation for computing occupancy grids and signed distance functions (SDFs) from watertight meshes.

LiangliangNan / Easy3D

A lightweight, easy-to-use, and efficient C++ library for processing and rendering 3D data

juj / MathGeoLib

A C++ library for linear algebra and geometry manipulation for computer graphics.

Habrador / Computational-geometry

Computational Geometry Unity library with implementations of intersection algorithms, triangulations like delaunay, voronoi diagrams, polygon clipping, bezier curves, ear clipping, convex hulls, me…

stefankoegl / kdtree

A Python implementation of a kd-tree

erich666 / GraphicsGems

Code for the "Graphics Gems" book series

gradientspace / geometry3Sharp

C# library for 2D/3D geometric computation, mesh algorithms, and so on. Boost license.

Reservoir Simulation

equinor / ert

ERT—Ensemble based Reservoir Tool—is a tool to run ensemble based on reservoir models. ERT was originally devised as tool to do model updating (history matching) with the EnKF method, now the prima…

shaffer1 / RVA

Reservoir Visualization and Analysis

OPM / opm-core

Collection of utilities, solvers and other components.

OPM / opm-tests

Data sets intended for integration and regression testing reservoir simulations

OPM / opm-parser

OPM / ResInsight

3D viewer and post processing of reservoir models

OPM / opm-simulators

Simulator programs and utilities for automatic differentiation.

Optimization

CMA-ES / pycma

Python implementation of CMA-ES

Trading

quantopian / zipline

Zipline, a Pythonic Algorithmic Trading Library

Jake0303 / RobinHood-RSI-Trading-Bot

A Robinhood stock trading bot in Python using the RSI indicator https://youtu.be/kSLkRXY3NPQ

microsoft / qlib

Qlib is an AI-oriented quantitative investment platform, which aims to realize the potential, empower the research, and create the value of AI technologies in quantitative investment. With Qlib, yo…

Interesting

Chakazul / Lenia

Lenia - Mathematical Life Forms

System Design Important Materials

Designing Data-Intensive Applications

Book Refs

DDIA Reading Note

timilearning.com/posts/ddia/notes/

github.com/keyvanakbary/learning-notes/blob/master/books/designing-data-intensive-applications.md

The Architecture of Open Source Applications

https://www.aosabook.org/en/index.html

https://www.aosabook.org/en/distsys.html

Grokking the System Design Interview

Book

awesome-scalability

System Design Interview

checkcheckzz / system-design-interview

Grokking System Design Grokking System Design

System Design Primer

donnemartin / system-design-primer

Learn how to design large-scale systems. Prep for the system design interview. Includes Anki flashcards.

ByteByteGo System Design 101

ByteByteGoHq/system-design-101

A Senior Engineer's Guide to the System Design Interview

国外知名互联网公司的系统设计和推荐算法汇总

infoq.cn/article/psaujpy1lsz2axmfqym8

System Design Interview Book by Alex Xu

Book Vol 1

Links Vol 1 Links Vol 2

Separate Materials

YouTube Channel

System Design Interview

Scott Shi

Gaurav Sen

Alex Xu

System Design Cheat Sheet

gist.github.com/vasanthk/485d1c25737e8e72759f

Cloud Reference Architecture

AWS Reference Architecture Diagrams

Azure Cloud Architecture Design Patterns

Machine Learning Important Materials

ML Training/Inference

How to Scale Your Model: A Systems View of LLMs on TPUs

The Ultra-Scale Playbook: Training LLMs on GPU Clusters

Machine Learning Engineering Open Book

An open collection of methodologies, tools and step-by-step instructions to help with successful training and fine-tuning of large language models and multi-modal models and their inference.

TPU

tiny-tpu

A minimal tensor processing unit (TPU), inspired by Google's TPU V2 and V1.

LLM

The Illustrated Transformer

The Illustrated Stable Diffusion

nanochat

A full-stack implementation of an LLM like ChatGPT in a single, clean, minimal, hackable, dependency-lite codebase

vllm

A high-throughput and memory-efficient inference and serving engine for LLMs.

Learning On the Way

Euclidean algorithm (The time complexity of this algorithm is O(log(min(a, b)))