lengthOfLongestSubstring (cache) O(n)

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

Example 1:

1
2
3

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.

Example 2:

1
2
3

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols and spaces.

设两个指针 i 和 j：i 指向滑动窗口起点，j 指向终点。
先把 j 向右移动，遇到重复字符就停下，计算当前长度。
然后把 i 向右移动以越过那个重复字符。
用一个字典记录每个字符出现的位置。

# O(kn)
def solution(a):
    i, j = 0, 0
    indice = {}
    ret = 0
    while j < len(a):
        if a[j] in indice:
            i = indice[a[j]]
            # reconstruct the indice map
            indice = {a[k]: k for k in range(i+1, j+1)}
        else:
            # only add the current element
            indice[a[j]] = j
        ret = max(ret, len(indice))
        j += 1
    return ret

# O(n)
def solution2(a):
    i, j = 0, 0
    indice = {}
    ret = 0
    while j < len(a):
        if a[j] in indice:
            # once we find a duplicate key
            # then valid path must be the length between these two key minus 1
            i = max(indice[a[j]], i)
        ret = max(ret, j-i+1)
        indice[a[j]] = j+1
        j += 1
    return ret


print(solution2("abcabcbb"))

findMedianSortedArrays (binary search) O(log(m+n))

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

Example 1:

1
2
3

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

1
2
3

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6
```
    left_part          |        right_part
```
A[0], A[1], …, A[i-1] | A[i], A[i+1], …, A[m-1]
B[0], B[1], …, B[j-1] | B[j], B[j+1], …, B[n-1]

我们用 i 和 j 把数组 A、B 各切两半。当下面三个条件同时满足时即可拿到中位数：
- len(left_part)=len(right_part)
- max(left_part)≤min(right_part)
- median = (max(left_part) + min(right_part)) / 2

可以化简为：
- B[j−1]≤A[i] 且 A[i−1]≤B[j]
- j=(m+n+1)/2-i

对 i 做二分搜索：
- 若 B[j−1]≤A[i] 且 A[i−1]≤B[j]，找到中位数
- 若 B[j−1]>A[i]，需要把 i 向右移（二分）
- 若 A[i−1]>B[j]，需要把 i 向左移（二分）

注意：
- imin, imax, half_len = 0, m, (m+n+1)//2
- i = (imin+imax)//2, j = half_len – i
- if i < m and nums2[j-1] > nums1[i]: imin = i + 1 # binary search
- elif i > 0 and nums1[i-1] > nums2[j]: imax = i - 1 # binary search

def solution(nums1, nums2):
    m, n = len(nums1), len(nums2)
    if m > n:
        nums1, nums2, m, n = nums2, nums1, n, m
    imin, imax, half_len = 0, m, (m + n + 1) // 2
    while imin <= imax:
        i = (imin + imax) // 2
        j = half_len - i
        if i > 0 and nums1[i - 1] > nums2[j]:
            imax = i - 1
        elif i < m and nums1[i] < nums2[j - 1]:
            imin = i + 1
        else:
            if i == 0:
                max_of_left = nums2[j - 1]
            elif j == 0:
                max_of_left = nums1[i - 1]
            else:
                max_of_left = max(nums1[i - 1], nums2[j - 1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m:
                min_of_right = nums2[j]
            elif j == n:
                min_of_right = nums1[i]
            else:
                min_of_right = min(nums1[i], nums2[j])

            return (max_of_left + min_of_right) / 2.

longestPalindrome (dp) O(N^2)

Given a string s, return the longest palindromic substring in s.

Example 1:

1
2
3

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

1 2	Input: s = "cbbd" Output: "bb"

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

设两个下标，i 表示窗口长度，j 表示窗口起点，状态转移方程：

P(i, j) = P(i+1, j-1) + 2, if s[i] == s[j].

注意：

P(i, i) = 1
‘aa’ 也是回文，所以 P(i, i+1) = 2 if s[i] = s[i+1]

# O(n^2)
def solution(s):
    n = len(s)
    dp = [[0] * n for i in range(n+1)]
    ret = ""
    max_len = 0
    # i is the length, j is the start position
    for i in range(1, len(s)+1):
        for j in range(len(s)-i+1):
            # case 1, single char
            if i == 1:
                dp[i][j] = 1
            # case 2, continuous smae char
            elif i == 2:
                if s[j] == s[j+1]:
                    dp[i][j] = 2
            else:
                if dp[i-2][j+1] > 0 and s[j] == s[j+i-1]:
                    dp[i][j] = dp[i-2][j+1] + 2
            if dp[i][j] > max_len:
                max_len = dp[i][j]
                ret = s[j:j+i]
    return ret

isMatch (recursive with memo) O(MN)

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.

Return a boolean indicating whether the matching covers the entire input string (not partial).

Example 1:

1
2
3

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

1
2
3

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

Example 3:

1
2
3

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Constraints:

1 <= s.length <= 20
1 <= p.length <= 20
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and '*'.
It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

加备忘录避免重复检查。

def solution(s, p):
    memo = {}
    m, n = len(s), len(p)

    def recursive(i, j):
        if (i, j) not in memo:
            if j == n:
                ans = i == m
            else:
                first_match = i < m and p[j] in (s[i], '.')
                if j + 1 < n and p[j + 1] == '*':
                    ans = recursive(
                        i, j + 2) or first_match and recursive(i + 1, j)
                else:
                    ans = first_match and recursive(i + 1, j + 1)
            memo[i, j] = ans
        return memo[i, j]

    return recursive(0, 0)

maxArea (trick) O(n)

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

1
2
3

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

1 2	Input: height = [1,1] Output: 1

Constraints:

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

令 i = 0，j = len(heights)-1。每次把较矮的那一根向中间移动，重新计算最大面积。因为如果下一根比当前还矮，宽度变小、高度也没增加，体积不可能更大。

注意：这题不能用 dp，因为没有最优子结构。

这个 trick 之所以成立：我们从两端往里收，宽度一直在减小，只有高度变大才有机会出现更大面积。而之所以移动较矮的那根：如果固定较矮的、移动较高的，min 高度仍然是较矮那根，面积只会随宽度减小而下降。

# O(n)
def solution(height):
    i, j = 0, len(height) - 1
    ret = min(height[j], height[i]) * (j-i)
    while i < j:
        ret = max(ret, min(height[i], height[j]) * (j-i))
        if height[i] < height[j]:
            i += 1
        else:
            j -= 1
    return ret

(mark) threeSum (trick) O(n^2)

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

1
2
3

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

1
2
3

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

先排序，然后三指针 i, j, k。固定 i 后，j = i+1，k = n-1，目标是让 nums[j] + nums[k] = -nums[i]：和偏小就 j++，和偏大就 k--（因为已排序）。

# O(n^2) sort
def solution(nums):
    n = len(nums)
    nums.sort()
    ret = []
    for i in range(n-2):
        if i > 0 and nums[i] == nums[i-1]: # avoid repeat
            continue
        j, k = i+1, n-1
        while j < k:
            s = nums[i] + nums[j] + nums[k]
            if s < 0:
                j += 1
            elif s > 0:
                k -= 1
            else:
                ret.append([nums[i], nums[j], nums[k]])
                while j < k and nums[j] == nums[j+1]: # avoid repeat
                    j += 1
                while j < k and nums[k] == nums[k-1]: # avoid repeat
                    k -= 1
                j += 1
                k -= 1
    return ret

letterCombinations (full permutation), O(3^N * 4^M)

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

1 2	Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

1 2	Input: digits = "2" Output: ["a","b","c"]

Constraints:

1 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'].

直接递归：每层枚举当前数字对应的所有字符，调用下一层递归。

phone = {'2': ['a', 'b', 'c'],
         '3': ['d', 'e', 'f'],
         '4': ['g', 'h', 'i'],
         '5': ['j', 'k', 'l'],
         '6': ['m', 'n', 'o'],
         '7': ['p', 'q', 'r', 's'],
         '8': ['t', 'u', 'v'],
         '9': ['w', 'x', 'y', 'z']}


def solution(digits):
    ret = []
    if not digits:
        return ret

    def recursion(prefix, digits):
        if not digits:
            ret.append(prefix)
        else:
            for c in phone[digits[0]]:
                recursion(prefix+c, digits[1:])
    recursion("", digits)
    return ret

removeNthFromEnd (trick) O(n)

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

Example 1:

1 2	Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

Example 2:

1 2	Input: head = [1], n = 1 Output: []

Example 3:

1 2	Input: head = [1,2], n = 1 Output: [1]

Constraints:

The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

Follow up: Could you do this in one pass?

双指针 p, q：先让 p 向前走 n 步，再让两个指针一起走，当 p 走到末尾时，q 正好停在倒数第 n 个节点。

def solution(head, n):
    t = ListNode(None)
    t.next = head
    p = t
    q = t
    for _ in range(n):
        p = p.next
    while p.next:
        q = q.next
        p = p.next
    q.next = q.next.next
    return t.next

generateParenthesis (recursive) O(4^n/√2)

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

Example 1:

1 2	Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

1 2	Input: n = 1 Output: ["()"]

Constraints:

1 <= n <= 8

用计数器 n 记录还可用的左括号数量，k 记录已经放下、待匹配的左括号数量。
- n == 0 且 k == 0：输出
- n == 0 且 k > 0：recursive(n, k-1)，加 ‘)’
- n > 0 且 k == 0：recursive(n-1, k+1)，加 ‘(‘
- 否则两个分支都试：recursive(n-1, k+1) 加 ‘(‘ 和 recursive(n, k-1) 加 ‘)’

def solution(n):
    ret = []
    if n == 0:
        return ret

    def recursion(prefix, i, j):
        # i means the assigned number of "(" and don't have ")"
        # j means the available number of "("
        if i==0 and j == 0:
            ret.append(prefix)
        elif i == 0:
            recursion(prefix+"(", i+1, j-1)
        elif j == 0:
            recursion(prefix+")", i-1, j)
        else:
            recursion(prefix+"(", i+1, j-1)
            recursion(prefix+")", i-1, j)

    recursion("", 0, n)
    return ret

nextPermutation (trick), O(n)

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1:

1 2	Input: nums = [1,2,3] Output: [1,3,2]

Example 2:

1 2	Input: nums = [3,2,1] Output: [1,2,3]

Example 3:

1 2	Input: nums = [1,1,5] Output: [1,5,1]

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

j = len(n)-1，i = len(n)-2。从后往前找 i，一旦发现 n[i] < n[j]，就交换 n[i] 与 n[j]，然后把 n[i:j+1] 反转。

要点：从末尾扫描，找到第一个”变小”的位置就把这两个值之间整段反转。

def solution(nums):
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i + 1] <= nums[i]:
        i -= 1
    if i >= 0:
        j = n - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = nums[:i:-1]
    else:
        nums[::] = nums[::-1]

longestValidParentheses

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

Example 1:

1
2
3

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

1
2
3

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

1 2	Input: s = "" Output: 0

Constraints:

0 <= s.length <= 3 * 10^4
s[i] is '(', or ')'.

longestValidParentheses (stack trick) O(n)

核心想法：当遇到 ‘)’（栈非空）时，需要知道这一段合法子串从哪里开始 —— 把”开始位置”压栈即可。

每当遇到一个无效字符（仍需要 pop）或者一个 ‘(‘，就把当前位置入栈。这样以后再碰到 ‘)’，先 pop，栈顶 stack[-1] 就是当前合法子串的起点。

# dp O(n)
def solution(s):
    max_ret = 0
    stack = [-1]
    for i in range(len(s)):
        if s[i] == '(':
            stack.append(i)
        else:
            stack.pop()
            if len(stack) == 0:
                stack.append(i) # last invalid point
            else:
                max_ret = max(max_ret, i - stack[-1]) # i-stack[-1] is current valid length
    return max_ret

# dp O(n)
def solution(s):
    ret = 0
    dp = [0] * len(s)
    for i in range(1, len(s)):
        if s[i] == ")":
            if s[i - 1] == "(":
                dp[i] = (dp[i - 2] if i > 1 else 0) + 2
            elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == "(":
                dp[i] = dp[i-1] + 2 + \
                    (dp[i-dp[i-1]-2] if i-dp[i-1]-2 > 0 else 0)
        ret = max(ret, dp[i])
    return ret

(mark) longestValidParentheses (dp) O(n)

dp[i] 表示以 i 结尾的最长合法子串长度。合法子串总以 ‘)’ 结尾，所以：
- s[i-1, i] = ‘()’：dp[i] = dp[i-2] + 2（dp[i-1]=0）
- s[i-1, i] = ‘))’：检查 s[i-dp[i-1]-1]（也就是上一个合法子串前面那个字符）是否为 ‘(‘。如果是，dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2 —— 即”上一个合法子串”+”再之前的合法子串”+”配对的两个括号”。

# dp O(n)
def solution(s):
    ret = 0
    dp = [0] * len(s)
    for i in range(1, len(s)):
        if s[i] == ")":
            print(s[i], i, dp[i-1])
            if s[i-1] == "(":
                dp[i] = (dp[i-2] if i > 1 else 0) + 2
            elif i-dp[i-1] > 0 and s[i-dp[i-1]-1] == "(":
                dp[i] = dp[i-1] + 2 + \
                    (dp[i-dp[i-1]-2] if i-dp[i-1]-2 > 0 else 0)
        ret = max(ret, dp[i])
    return ret

(mark) search (binary search trick) O(log n)

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

Prior to being passed to your function, nums is possibly left rotated at an unknown 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 left rotated by 3 indices 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.

Example 1:

1 2	Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

Example 2:

1 2	Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

Example 3:

1 2	Input: nums = [1], target = 0 Output: -1

Constraints:

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10^4 <= target <= 10^4

举例：输入 [4, 5, 6, 7, 0, 1, 2]，s = 0，e = n-1，m = (s+e)//2。

考虑四种情况：
- 旋转点在右边、目标在左半段：nums[s] <= target < nums[m] → recursive(s, m-1)
- 旋转点在左边、目标在右半段：nums[m] < target <= nums[e] → recursive(s+1, m)
- 旋转点在右边、目标在右边：nums[m] > nums[e] → recursive(m+1, e)
- 旋转点在左边、目标在左边：nums[s] > nums[m] → recursive(s, m-1)

第三种情况隐含一个条件：若 nums[m] > nums[e]，则旋转点必在右边，因此 nums[s] 必小于 nums[m]。这种情况下只需检查目标是否落在右段；若落在左段，会被第一种情况捕获。第四种情况同理。

而且这种递归不会破坏旋转数组的性质。

def solution(nums, target):
    if not nums:
        return -1

    def recursion(i, j):
        if j < i:
            return -1
        m = (i+j)//2
        if nums[m] == target:
            return m
        # target locates at non-axis side (and is left side)
        elif nums[i] <= target < nums[m]:
            return recursion(i, m-1)
        # target locates at non-axis side (and is right side)
        elif nums[m] < target <= nums[j]:
            return recursion(m+1, j)
        # target locates at axis side (and is right side)
        elif nums[m] > nums[j]:
            return recursion(m+1, j)
        # target locates at axis side (and is left side)
        else:
            return recursion(i, m-1)
    return recursion(0, len(nums)-1)

searchRange (Binary Search trick) O(log n)

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

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

Example 1:

1 2	Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Example 2:

1 2	Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

Example 3:

1 2	Input: nums = [], target = 0 Output: [-1,-1]

Constraints:

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums is a non-decreasing array.
-10^9 <= target <= 10^9

两次二分：一次找左边界，一次找右边界。

魔改普通二分：找到 target 时不停下，继续向另一侧搜索。当 right_index < left_index 时，左边界搜索返回 left_index，右边界搜索返回 right_index。

def solution(nums, target):
    def recursiveLeft(s, e):
        if e < s:
            return s
        m = (s+e)//2
        if nums[m] < target:
            return recursiveLeft(m+1, e)
        else:
            return recursiveLeft(s, m-1)

    def recursiveRight(s, e):
        if e < s:
            return e
        m = (s+e)//2
        if nums[m] <= target:
            return recursiveRight(m+1, e)
        else:
            return recursiveRight(s, m-1)

    left, right = recursiveLeft(0, len(nums)-1), recursiveRight(0, len(nums)-1)
    # once we cannot found the value, the left will right-1
    return [left, right] if left <= right else [-1, -1]

combinationSum (dfs) O(exponential)

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.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

1 2	Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

1 2	Input: candidates = [2], target = 1 Output: []

Constraints:

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

外面套个 for 循环依次调用递归即可。

def solution(candidates, target):
    ret = []

    def recursion(prefix, i, target):
        if target == 0:
            ret.append(prefix)
        for i in range(i, len(candidates)):
            num = candidates[i]
            if target - num >= 0:
                recursion(prefix+[num], i, target-num)
    recursion([], 0, target)
    return ret

firstMissingPositive (trick: hash with mod position) O(n)

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

1
2
3

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

1
2
3

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

1
2
3

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

最大挑战是只能用常数额外空间，不能开 O(n) 哈希表。因此用输入数组本身充当哈希表。

做法：先把所有 <0 或 >=n 的位置置 0，然后 nums[nums[i] % n] += n，用这种方式标记某个 bin 已经出现过。最后遍历，第一个值仍小于 n 的下标就是答案。

def solution(nums):
    nums.append(0) # very important, for example, [1]
    n = len(nums)
    for i in range(n):  # delete those useless elements
        if nums[i] < 0 or nums[i] >= n:
            nums[i] = 0
    # use the index as the hash to record the frequency of each number
    for i in range(n):
        nums[nums[i] % n] += n # +n and %n to make the original value do not be overlaped
    for i in range(1, n):
        if nums[i] < n:
            return i
    return n

Trap (two dp, left and right) O(n)

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

1
2
3

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

1 2	Input: height = [4,2,0,3,2,5] Output: 9

Constraints:

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

两个 dp 数组：分别记录从左、从右两个方向看过来的最大高度。
- dp_l[i] = max(dp_l[i-1], height[i])
- dp_r[i] = max(dp_r[i+1], height[i])

每个坑的水量 = min(dp_l[i], dp_r[i]) - height[i]。

def solution(height):
    height = [0] + height + [0]
    n = len(height)
    ret = 0
    max_left = [0] * n  # record the max height from left
    max_right = [0] * n  # record the max height from right
    cur_max = height[0]
    for i in range(n):
        cur_max = max(cur_max, height[i])
        max_left[i] = cur_max
    cur_max = height[-1]
    for i in range(n-1, -1, -1):
        cur_max = max(cur_max, height[i])
        max_right[i] = cur_max
        ret += min(max_left[i], max_right[i]) - height[i]
    return ret

Permute (loop call recusive) O(2^n)

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

1 2	Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

1 2	Input: nums = [0,1] Output: [[0,1],[1,0]]

Example 3:

1 2	Input: nums = [1] Output: [[1]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

def solution(nums):
    ret = []
    n = len(nums)

    def recursion(prefix, remaining):
        if not remaining:
            ret.append(prefix)
        else:
            for k in range(len(remaining)):
                recursion(prefix+[remaining[k]], remaining[:k] + remaining[k+1:])
    recursion([], nums)
    return ret

Rotate (trick) O(n^2)

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

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

Example 2:

1 2	Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

先反转再转置（reverse + transpose）。

def solution(matrix):
    n = len(matrix)
    i, j = 0, n - 1
    # swap
    while i < j:
        matrix[i], matrix[j] = matrix[j], matrix[i]
        i += 1
        j -= 1
    # transpose
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

(mark) groupAnagrams (hash) O(m)

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Example 1:

Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]

Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

Explanation:

There is no string in strs that can be rearranged to form "bat".
The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.

Example 2:

Input: strs = [“”]

Output: [[“”]]

Example 3:

Input: strs = [“a”]

Output: [[“a”]]

Constraints:

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

用 collections.defaultdict(list)，把 tuple(sorted(s)) 作为哈希 key。

from collections import defaultdict

def solution(strs):
    ret = defaultdict(list)
    for s in strs:
        ret[tuple(sorted(s))].append(s)
    return list(ret.values())

** 必须用 sorted(s)；用 set(s) 不行（会丢失字符频次）。

(mark) maxSubArray (trick) O(n)

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

1
2
3

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

1
2
3

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

1
2
3

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

从左到右扫一遍，用一个累计 sum：只要左边累计是正的就保留，否则把累计的负值丢弃从头开始。

转移：nums[i] = max(0, nums[i-1]) + nums[i]

每段连续正子串里取最大：ret = max(ret, nums[i])。

def solution(nums):
    cur_sum = 0
    max_v = - sys.maxsize
    for num in nums:
        cur_sum = max(0, cur_sum) + num
        max_v = max(max_v, cur_sum)
    return max_v

canJump (greedy) O(n)

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true* if you can reach the last index, or false otherwise*.

Example 1:

1
2
3

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

1
2
3

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5

从左往右扫，维护”当前能到达的最远位置”。每遇到新位置就更新。能到末尾就返回 true。

def solution(nums):
    m = 0
    for i in range(0, len(nums)):
        if i > m:
            return False
        m = max(m, i+nums[i])
    return True

def solution(nums):
    i, max_i = 0, 0
    while i <= max_i and i < len(nums) and max_i < len(nums)-1:
        max_i = max(max_i, i+nums[i])
        i += 1
    return max_i >= len(nums) - 1

merge (greedy) O(n)

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

1
2
3

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

1
2
3

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Example 3:

1
2
3

Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: Intervals [1,4] and [4,7] are considered overlapping.

Constraints:

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start_i <= end_i <= 10^4

先按起点排序，然后维护一个结果数组：每次检查上一个区间的右端点是否 ≥ 当前区间的左端点，如果是就合并，否则直接 append。

def solution(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

def solution(intervals):
    intervals.sort(key=lambda x: x[0])
    ret = []
    while intervals:
        interval_1 = intervals.pop(0)
        if intervals and interval_1[1] >= intervals[0][0]:
            intervals[0][0] = interval_1[0]
            intervals[0][1] = max(intervals[0][1], interval_1[1])
        else:
            ret.append(interval_1)
    return ret

uniquePaths (dp) O(m+n)

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

Example 1:

1 2	Input: m = 3, n = 7 Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

1 <= m, n <= 100

dp[i][j] = dp[i][j-1] + dp[i-1][j]

def solution(m, n):
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i][j-1] + dp[i-1][j]
    return dp[-1][-1]

minPathSum (dp) O(mn)

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:

1
2
3

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

1 2	Input: grid = [[1,2,3],[4,5,6]] Output: 12

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + m[i][j]

def solution(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0]*n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    return dp[-1][-1]

climbStairs (dp) O(n)

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

1 <= n <= 45

dp[i] = dp[i-1] + dp[i-2], dp[0]=1, dp[1] = 1

def solution(n):
    if n == 1:
        return 1
    dp = [0] * n
    dp[0], dp[1] = 1, 2
    for i in range(2, n):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[-1]

(mark) minDistance (dc) O(mn)

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

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Constraints:

0 <= word1.length, word2.length <= 500
word1 and word2 consist of lowercase English letters.

定义递归 recursive(word1, word2, i, j, memo) 返回 word1[i:] 转成 word2[j:] 所需的最少操作数，用 memo 缓存子问题。

若 word1[i] == word2[j]：memo[i][j] = recursive(word1, word2, i+1, j+1, memo)。否则有三种操作：
- insert = 1 + recursive(word1, word2, i, j+1, memo)：在 word1[i] 前插入 word2[j]，使两端字符相等，然后比较 word1[i] 与 word2[j+1]。
- delete = 1 + recursive(word1, word2, i+1, j, memo)：删掉 word2[j]，比较 word1[i+1] 与 word2[j]。
- replace = 1 + recursive(word1, word2, i+1, j+1, memo)：用 word2[j] 替换 word1[i]，再比较 word1[i+1] 与 word2[j+1]。

memo[i][j] = min(insert, delete, replace)。

终止条件：i == m && j == n 时已处理完两个字符串，返回 0；i == m 时返回 n - j；j == n 时返回 m - i（剩下的字符全靠插入）。

def solution(word1, word2):
    memo = {}
    n, m = len(word1), len(word2)
    if m < n:
        word1, word2, m, n = word2, word1, n, m

    def recursive(i, j):
        if (i, j) not in memo:
            if i == n:
                ans = m - j
            elif j == m:
                ans = n - i
            else:
                if word1[i] == word2[j]:
                    ans = recursive(i + 1, j + 1)
                else:
                    # insert, delete, replace
                    ans = min(recursive(i, j + 1), recursive(i + 1, j),
                              recursive(i + 1, j + 1)) + 1
            memo[i, j] = ans
        return memo[i, j]

    return recursive(0, 0)

sortColors (trick) O(n)

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.

Example 1:

1 2	Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]

Example 2:

1 2	Input: nums = [2,0,1] Output: [0,1,2]

Constraints:

n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

三指针 i, j, k：i 与 j 圈定待处理范围，k 指向当前处理的值。nums[k] 三种情况：
- nums[k] == 0：交换 nums[i] 与 nums[k]，i+=1，k+=1
- nums[k] == 1：什么都不做，k+=1
- nums[k] == 2：交换 nums[j] 与 nums[k]，j-=1

实际上 i 标识 0 区间的末尾，j 标识 2 区间的开头：每次遇到 0 就把它换到 0 区间末尾，遇到 2 就换到 2 区间开头，最后中间留下的全是 1。

def solution(nums):
    n = len(nums)
    i, j, k = 0, 0, n-1
    while i <= k:
        if nums[i] == 0:
            if i != j:
                nums[i], nums[j] = nums[j], nums[i]
                j += 1
            else:
                j += 1
                i += 1
        elif nums[i] == 2:
            nums[i], nums[k] = nums[k], nums[i]
            k -= 1
        else:
            i += 1
    return nums

minWindow (trick hash) O(n)

Given two strings s and t of lengths m and n respectively, return the minimum window substring* of s such that every character in t (including duplicates) is included in the window*. If there is no such substring, return *the empty string *"".

The testcases will be generated such that the answer is unique.

Example 1:

1
2
3

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

1
2
3

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 10^5
s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

双指针 i, j 维护滑动窗口。哈希表 m 像一个”平衡钱包”：先把 T 中的字符加进去，遍历 S 时再扣除。m[c] > 0 表示这个字符还需要找；m[c] < 0 表示这个字符已经超额（出现次数比 T 中需要的还多）。再用 count = len(T) 记录还有多少字符要找。

向右移 j：m[s[j]] -= 1；只有当 m[s[j]] > 0（说明命中了一个真正需要的字符）时才 count -= 1。当 count == 0 表示窗口包含了 T 的所有字符，开始向右移 i 缩小窗口：每次 m[s[i]] += 1，若 m[s[i]] > 0（说明丢掉了一个真正需要的字符）才 count += 1。

def minWindow(self, s, t):
    """
    :type s: str
    :type t: str
    :rtype: str
    """
    import sys
    import collections
    m = collections.defaultdict(int)
    # m just like a balance wallet
    # we first add chars of T into it
    # then once we encounter chars in S
    # we minus from m
    # so for m>0 menas there is still char we need to find
    # m<0 means we remove much more than we need in T
    for c in t:
        m[c] += 1
    j = 0

    # identify how many remaining chars in T we still need to find
    count = len(t)
    minLen = sys.maxsize
    minStart = 0
    for i in range(len(s)):
        # only when m[s[i]] > 0, means remaining chars in t
        if m[s[i]] > 0:
            count -= 1
        m[s[i]] -= 1
        # we have found all chars in T, we start to move j
        while count == 0:
            if (i - j + 1) < minLen:
                minLen = i-j+1
                minStart = j
            m[s[j]] += 1
            # when m[s[i]] > 0, means we remove too much target chars
            # we increase count to mark there are chars we need to find
            if m[s[j]] > 0:
                count += 1
            j += 1

    if minLen < sys.maxsize:
        return s[minStart:minStart+minLen]
    return ""

def solution(s, t):
    from collections import Counter
    import sys

    n = len(s)
    i, j = 0, 0
    c_t = Counter(t)
    count = len(t)
    b, l = 0, sys.maxsize
    while j < n:
        if c_t[s[j]] > 0:
            count -= 1
        c_t[s[j]] -= 1

        while not count:
            if (j-i+1) < l:
                l = j-i+1
                b = i
            c_t[s[i]] += 1
            if c_t[s[i]] > 0:
                count += 1
            i += 1
        j += 1
    if l < sys.maxsize:
        return s[b:b+l]
    return ""

Subsets (dfs) O(2^n)

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

1 2	Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

1 2	Input: nums = [0] Output: [[],[0]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.

跟全排列类似，但中间节点也要输出。

def solution(nums):
    n = len(nums)
    ret = []

    def recursion(prefix, i):
        ret.append(prefix)
        for j in range(i, n):
            recursion(prefix+[nums[j]], j+1)
    recursion([], 0)
    return ret

(mark) Exist (dfs) O(mn * len(words))

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can 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.

Example 1:

1 2	Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true

Example 2:

1 2	Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true

Example 3:

1 2	Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false

Constraints:

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

定义递归 dfs(row, col, idx)：从 nums[row][col] 开始匹配 word[idx:]。遍历每个 cell，仅当其等于 word[0] 时调用 dfs。

dfs 内：若 idx == len(word) 返回 True；否则向四个方向探索，若邻居等于 word[idx] 就递归下去；都失败则返回 False。

def solution(board, word):
    m, n = len(board), len(board[0])

    def recursion(i, j, idx):
        if idx == len(word):
            return True
        board[i][j] = "#"
        if i+1 < m and board[i+1][j] == word[idx] and recursion(i+1, j, idx+1):
            return True
        if j+1 < n and board[i][j+1] == word[idx] and recursion(i, j+1, idx+1):
            return True
        if i-1 >= 0 and board[i-1][j] == word[idx] and recursion(i-1, j, idx+1):
            return True
        if j-1 >= 0 and board[i][j-1] == word[idx] and recursion(i, j-1, idx+1):
            return True
        board[i][j] = word[idx-1]
        return False

    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0] and recursion(i, j, 1):
                return True
    return False

largestRectangleArea (left and right dp) O(n)

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

1 2	Input: heights = [2,4] Output: 4

Constraints:

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

两个数组 left_min、right_min 分别记录左右两侧第一个比当前更矮的位置。每个矩形面积 = height[i] * (right_min[i] - left_min[i] - 1)。

left_min[0] = -1。计算 left_min[i] 时从 j = i-1 开始，发现 height[j] >= height[i] 就跳到 j = left_min[j]，递归往前找更矮的位置。

def solution(heights):
    heights = [0] + heights + [0]
    n = len(heights)
    min_left = [0] * n
    min_right = [0] * n
    ret = 0
    for i in range(1, n - 1):
        tmp_i = i - 1
        while tmp_i > 0 and heights[tmp_i] >= heights[i]:
            tmp_i = min_left[tmp_i]
        min_left[i] = tmp_i
    for j in range(n - 2, 0, -1):
        tmp_j = j + 1
        while tmp_j < n - 1 and heights[tmp_j] >= heights[j]:
            tmp_j = min_right[tmp_j]
        min_right[j] = tmp_j
    for i in range(1, n - 1):
        ret = max(ret, heights[i] * (min_right[i] - min_left[i] - 1))
    return ret

maximalRectangle (greedy) O(mn)

Given a rows x cols binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.

Example 1:

1
2
3

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

1 2	Input: matrix = [["0"]] Output: 0

Example 3:

1 2	Input: matrix = [["1"]] Output: 1

Constraints:

rows == matrix.length
cols == matrix[i].length
1 <= rows, cols <= 200
matrix[i][j] is '0' or '1'.

三个数组分别记录最远高度、最远左边界、最远右边界。

height：
- matrix[i][j] == ‘1’ → height[j] += 1，否则 height[j] = 0

left：
- matrix[i][j] == ‘1’ → left[j] = max(left[j], cur_left)，否则 left[j] = 0，cur_left = j+1

right：
- matrix[i][j] == ‘1’ → right[j] = min(right[j], cur_right)，否则 right[j] = n，cur_right = j

流程：先确定矩形高度，再找它的最远左右边界。cur_left 记录当前行的最远左边界，left[j] 记录所有行的最远左边界，max(left[j], cur_left) 给出当前行内矩形的最远左边界。

def solution(matrix):
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    left, right, height = [0] * n, [n] * n, [0] * n
    max_v = 0
    for i in range(m):
        cur_left, cur_right = 0, n
        for j in range(n):
            if matrix[i][j] == '1':
                height[j] += 1
                left[j] = max(left[j], cur_left)
            else:
                height[j] = 0
                left[j] = 0
                cur_left = j + 1
            j = n - j - 1
            if matrix[i][j] == '1':
                right[j] = min(right[j], cur_right)
            else:
                right[j] = n
                cur_right = j
        for j in range(n):
            max_v = max(max_v, (right[j] - left[j]) * height[j])
    return max_v

inorderTraversal (iterative) O(n)

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

Example 1:

Input: root = [1,null,2,3]

Output: [1,3,2]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,2,6,5,7,1,3,9,8]

Explanation:

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

用栈：每次 pop 一个节点，把它的子节点按 (node.left, node.val, node.right) 顺序入栈；pop 出整数就直接输出。

另一种写法：先一路把左节点压栈到最左叶子；每次 pop 一个节点输出，然后递归地把它右子节点的左链压栈。

def solution(root):
    ret = []

    def recursion(root):
        if not root:
            return
        recursion(root.left)
        ret.append(root.val)
        recursion(root.right)
    recursion(root)
    return ret


def solution(root):
    ret = []
    stack = [root]
    while stack:
        node = stack.pop()
        if not node:
            continue
        elif isinstance(node, int):
            ret.append(node)
        else:
            stack.extend([node.right, node.val, node.left])
    return ret

numTrees (dp) O(n^2)

Given an integer n, return *the number of structurally unique **BST’*s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

1 2	Input: n = 3 Output: 5

Example 2:

1 2	Input: n = 1 Output: 1

Constraints:

1 <= n <= 19

定义两个函数：
- G(n)：长度为 n 的序列能形成的 BST 数量
- F(i, n)，1 ≤ i ≤ n：以 i 为根、序列范围 1~n 的 BST 数量

那么 G(n) = F(1, n) + F(2, n) + … + F(n, n)，且 G(0) = G(1) = 1。

注意 F(i, n) = G(i-1) * G(n-i)。

合起来：

G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)。

从 G(2) 开始：G(2) = G(0) * G(1)，G(3) = G(0) * G(2) + G(1) * G(1) + G(2) * G(0)，… 最终得 G(n)。

一开始想用 2D dp，但发现起点终点不重要、只看子问题长度，所以用 1D dp 就够了。

def solution(n):
    dp = [0] * (n+1)
    dp[0] = dp[1] = 1
    for i in range(2, n+1):
        for j in range(1, i+1):
            dp[i] += (dp[j-1]*dp[i-j])
    return dp[-1]

isValidBST (post-order, dfs) O(n)

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys strictly less than the node’s key.
The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

1 2	Input: root = [2,1,3] Output: true

Example 2:

1
2
3

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
-2^31 <= Node.val <= 2^31 - 1

解法 1（自底向上）：返回每个子树的 max 和 min。合法节点要求：节点值 > 左子树 max，且 < 右子树 min。

解法 2（自顶向下）：维护合法值域 (low, upper)。进入左子树时收紧上界，进入右子树时收紧下界。

def solution(root):
    if not root:
        return True

    def recursion(root, min_v, max_v):
        if not root:
            return True
        elif root.val <= min_v or root.val >= max_v:
            return False
        else:
            return recursion(root.left, min_v, root.val) and recursion(root.right, root.val, max_v)

    return recursion(root.left, -sys.maxsize, root.val) and recursion(root.right, root.val, sys.maxsize)

(mark) isSymmetric (dfs or bfs) O(n)

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

1 2	Input: root = [1,2,2,3,4,4,3] Output: true

Example 2:

1 2	Input: root = [1,2,2,null,3,null,3] Output: false

Constraints:

The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

def solution(root):
    if not root:
        return True

    def recursion(root1, root2):
        if not root1 and not root2:
            return True
        elif root1 and root2:
            if root1.val == root2.val:
                return recursion(root1.left, root2.right) and recursion(
                    root1.right, root2.left)
            else:
                return False
        else:
            return False

    return recursion(root.left, root.right)

def solution(root):
    if not root:
        return True
    queue1 = [root.left, root.right]
    queue2 = [root.right, root.left]

    while queue1 and queue2:
        node1 = queue1.pop(0)
        node2 = queue2.pop(0)
        if not node1 and not node2:
            continue
        elif node1 and node2 and node1.val == node2.val:
            queue1.extend([node1.left, node1.right])
            queue2.extend([node2.right, node2.left])
        else:
            return False
    if not queue1 and not queue2:
        return True
    else:
        return False

(mark) buildTree (recursive) O(n)

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

1 2	Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]

Example 2:

1 2	Input: preorder = [-1], inorder = [-1] Output: [-1]

Constraints:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder and inorder consist of unique values.
Each value of inorder also appears in preorder.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.

观察：preorder 按层序给出每个根，每个根又把 inorder 切成左右两段子树。

用 dict 记录 inorder 中每个值的位置以便快速查找。然后定义 helper(start, end)：每次给它一个 inorder 区间，递归构造左右子树：
- root.left = helper(start, idx-1)
- root.right = helper(idx+1, end)

（若 start > end 返回 None）

def solution(preorder, inorder):

    inorder_dict = {v: k for k, v in enumerate(inorder)}

    def build(i, j):
        if not preorder or i > j:
            return None
        val = preorder.pop(0)
        key = inorder_dict[val]
        node = TreeNode(val)
        node.left = build(i, key - 1)
        node.right = build(key + 1, j)
        return node

    return build(0, len(inorder) - 1)

(mark) Flatten (iterative pre-order dfs) O(n)

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-order** traversal** of the binary tree.

Example 1:

1 2	Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

1 2	Input: root = [] Output: []

Example 3:

1 2	Input: root = [0] Output: [0]

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

每次找到最深的左节点，把它接到当前节点的右孩子之前；再走到原右孩子继续递归。

def solution(root):
    if not root:
        return None

    def flatten(node):
        if not node.left and not node.right:
            return node
        if node.left:
            # get the deepest left node to append to its first right node
            tmp_node = flatten(node.left)
            tmp_node.right = node.right # append it right to the deepest node's right
            node.right = node.left # append the top left to its right
            node.left = None
        if node.right:
            # return deepest right node
            return flatten(node.right)

    flatten(root)
    return root

maxProfit (trick) O(n)

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

1
2
3

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4

要找 [lowest, highest] 这种二元组，且 highest 必须出现在 lowest 之后。所以记录历史最低，每次更新：
- lowest = min(lowest, prices[i])
- profit = max(profit, prices[i] - lowest)

def solution(prices):
    cur_min = sys.maxsize
    max_profit = 0
    for p in prices:
        cur_min = min(cur_min, p)
        max_profit = max(max_profit, p - cur_min)
    return max_profit

maxPathSum (tree dp) O(n)

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.

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

Example 1:

1
2
3

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

1
2
3

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

The number of nodes in the tree is in the range [1, 3 * 10^4].
-1000 <= Node.val <= 1000

自底向上。每个节点拿到左、右子树各自能贡献的最大路径和，尝试更新全局答案 result = max(result, left_max + right_max + node.val)；返回值为 max(left_max + node.val, right_max + node.val)，表示从这个节点向上延伸的最大单链路径。注意要跟 0 比较：若小于 0 就当成不取（路径里不要这一段）。

def solution(root):
    max_v = -sys.maxsize

    def recursive(root):
        nonlocal max_v
        if not root:
            return 0
        else:
            left = recursive(root.left)
            right = recursive(root.right)
            max_v = max(max_v, left + right + root.val)
            return max(left + root.val, right + root.val, 0)

    recursive(root)
    return max_v

longestConsecutive (hash) O(n)

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.

Example 1:

1
2
3

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

Example 2:

1 2	Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9

Example 3:

1 2	Input: nums = [1,0,1,2] Output: 3

Constraints:

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

把数组转成 set。遍历时若 nums[i]-1 在 set 里就跳过；只有遇到序列起点（即没有 nums[i]-1）时才开始向后逐 +1 计数，求出连续长度。

def solution(nums):
    if not nums:
        return 0
    set_nums = set(nums)
    max_v = 0
    for num in nums:
        if num - 1 not in set_nums:
            count = 1
            while num + 1 in set_nums:
                num += 1
                count += 1
            max_v = max(max_v, count)
    return max_v

copyRandomList (hash) O(n)

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

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

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

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

1 2	Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

1 2	Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]

Example 3:

1 2	Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]

Constraints:

0 <= n <= 1000
-10^4 <= Node.val <= 10^4
Node.random is null or is pointing to some node in the linked list.

用 collections.defaultdict 记录已访问的节点。

def solution(head):
    node_dict = defaultdict(Node)

    def build(node):
        if not node:
            return None
        _node = Node(node.val)
        node_dict[node] = _node
        if node.random:
            if node.random in node_dict:
                _node.random = node_dict[node.random]
            else:
                _node.random = build(node.random)
        if node.next:
            if node.next in node_dict:
                _node.next = node_dict[node.next]
            else:
                _node.next = build(node.next)
        return _node

    return build(head)


def solution(head):
    if not head:
        return None

    node_dict = defaultdict(Node)

    _head = Node(head.val)
    node_dict[head] = _head
    ret_head = _head
    while head:
        if head.random:
            if head.random not in node_dict:
                node_dict[head.random] = Node(head.random.val)
            _head.random = node_dict[head.random]
        if head.next:
            if head.next not in node_dict:
                node_dict[head.next] = Node(head.next.val)
            _head.next = node_dict[head.next]
        head = head.next
        _head = _head.next

    return ret_head

wordbreak (dp) O(mn)

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

1
2
3

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

1 2	Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false

Constraints:

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.

dp[i] 表示 s[0:i] 是否可被切分。转移：dp[i] = True 当存在 w 使得 dp[i - len(w)] == True 且 s[i - len(w):i] == w。

def solution(s, wordDict):
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for w in wordDict:
            if i >= len(w) and dp[i - len(w)] and s[i - len(w):i] == w:
                dp[i] = True
    return dp[-1]

DetectCycle (trick) O(n)

Given the head of a linked list, return *the node where the cycle begins. If there is no cycle, return *null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1:

1
2
3

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

1
2
3

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

1
2
3

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

设头节点到环入口距离为 A，慢指针走了 A+B 与快指针相遇。快指针走了 2(A+B)。设环长 N，相遇时快指针比慢指针多走的恰好是若干圈环长。
- A+B+N = 2A+2B
- N = A+B

所以两者相遇后，再让一个新指针从 head 出发，与 slow 同步前进，相遇点就是环的入口（因为 B + A = N）。

def solution(head):
    p = head
    q = head
    t = head
    while p and q and p.next and q.next and q.next.next:
        p = p.next.next
        q = q.next
        if q == p:
            while q != t:
                q = q.next
                t = t.next
            return t
    return None

LRUCache (double linked list) O(1)

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.

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
At most 2 * 10^5 calls will be made to get and put.

用双向链表，封装两个基本操作：remove（按 id 移除节点）和 add（追加到尾部）。
- get：先 remove 再 add（提到尾部）
- put：add 到尾部；超容量时从头部 remove

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

class LRUCache(object):
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.dict = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.pre = self.head

    def get(self, key):
        if key in self.dict:
            node = self.dict[key]
            self._remove(node)
            self._add(node) 
            return node.val
        else:
            return -1

    def put(self, key, value):
        if key in self.dict:
            self._remove(self.dict[key])
        node = Node(key, value)
        self._add(node)
        self.dict[key] = node
        while len(self.dict) > self.capacity:
            tmp_node = self.head.next
            self._remove(tmp_node)
            del self.dict[tmp_node.key]

    def _remove(self, node):
        p = node.pre
        n = node.next
        p.next = n
        n.pre = p
    
    def _add(self, node):
        p = self.tail.pre
        p.next = node
        node.pre = p
        node.next = self.tail
        self.tail.pre = node

SortList (merge sort or quick sort) O(nlogn)

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

1 2	Input: head = [4,2,1,3] Output: [1,2,3,4]

Example 2:

1 2	Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5]

Example 3:

1 2	Input: head = [] Output: []

Constraints:

The number of nodes in the list is in the range [0, 5 * 10^4].
-10^5 <= Node.val <= 10^5

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

用三个子链表存放节点：以 head 为 partition 节点；left_head 存比它小的节点，right_head 存比它大的节点，middle_head 存与它相等的节点。

然后对 left_head 和 right_head 递归排序，最后把三段串起来。

def solution(head):
    if head is None:
        return None

    def recursive(head):
        if head is None:
            return None, None

        partition_node = head
        middle_head = ListNode(None)
        middle_cur = middle_head
        left_head = ListNode(None)
        left_cur = left_head
        right_head = ListNode(None)
        right_cur = right_head

        while head:
            if head.val < partition_node.val:
                left_cur.next = ListNode(head.val)
                left_cur = left_cur.next
            elif head.val > partition_node.val:
                right_cur.next = ListNode(head.val)
                right_cur = right_cur.next
            else:
                middle_cur.next = ListNode(head.val)
                middle_cur = middle_cur.next
            head = head.next
        
        left_head, left_tail = recursive(left_head.next)
        right_head, right_tail = recursive(right_head.next)

        if left_head is not None:
            left_tail.next = middle_head.next
        else:
            left_head = middle_head
        if right_head is not None:
            middle_cur.next = right_head.next
        else:
            right_tail = middle_cur

        return left_head, right_tail

    head, _ = recursive(head)
    return head.next

(mark) maxProduct (greedy) O(n)

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Note that the product of an array with a single element is the value of that element.

Example 1:

1
2
3

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

1
2
3

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

同时记录当前最大值和最小值（因为负数乘负数可能成为最大）。每步用三者 (num, b*num, s*num) 取 max/min 更新。

def solution(nums):
    maximum = b = s = nums[0]
    for num in nums[1:]:
        b, s = max(num, b * num, s * num), min(num, b * num, s * num)
        maximum = max(maximum, b)
    return maximum

MinStack (trick) O(n)

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

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int value) pushes the element value onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

-2^31 <= val <= 2^31 - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

再开一个栈记录”当前最小”。每次 push 一个新值时，与原栈顶最小比较：新值大就复制旧最小，否则把新值压入。pop 时两个栈一起 pop。

class MinStack(object):

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

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack.append(x)
        if not self.min:
            self.min.append(x)
        else:
            self.min.append(min(self.min[-1], x))

    def pop(self):
        """
        :rtype: None
        """
        self.stack.pop()
        self.min.pop()

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

    def getMin(self):
        """
        :rtype: int
        """
        return self.min[-1]

GetIntersectionNode (trick) O(m+n)

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.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
listA - The first linked list.
listB - The second linked list.
skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2^nd node in A and 3^rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3^rd node in A and 4^th node in B) point to the same location in memory.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Constraints:

The number of nodes of listA is in the m.
The number of nodes of listB is in the n.
1 <= m, n <= 3 * 10^4
1 <= Node.val <= 10^5
0 <= skipA <= m
0 <= skipB <= n
intersectVal is 0 if listA and listB do not intersect.
intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?

两条链表 p、q，把 p 接到 q 尾部、q 接到 p 尾部之后再走，两个指针相遇时即为交点。

def solution(headA, headB):
    if not headA or not headB:
        return None
    nodeA = headA
    nodeB = headB
    while nodeA is not nodeB:
        if not nodeA and nodeB:
            return None
        if nodeA.next is None:
            nodeA = headB
        else:
            nodeA = nodeA.next
        if nodeB.next is None:
            nodeB = headA
        else:
            nodeB = nodeB.next
    return nodeA


def solution(headA, headB):

    def len(head):
        ret = 0
        while head:
            ret += 1
            head = head.next
        return ret

    lenA, lenB = len(headA), len(headB)
    diff = abs(lenA - lenB)

    if lenA > lenB:
        for _ in range(diff):
            headA = headA.next
    else:
        for _ in range(diff):
            headB = headB.next

    while headA != headB:
        headA = headA.next
        headB = headB.next
    return headA

MajorityElement (trick) O(n)

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

1 2	Input: nums = [3,2,3] Output: 3

Example 2:

1 2	Input: nums = [2,2,1,1,1,2,2] Output: 2

Constraints:

n == nums.length
1 <= n <= 5 * 10^4
-10^9 <= nums[i] <= 10^9
The input is generated such that a majority element will exist in the array.

Follow-up: Could you solve the problem in linear time and in O(1) space?

Boyer-Moore 投票法。维护 value 和 count：count == 0 时把 value 置为 nums[i] 并 count += 1；nums[i] == value 则 count += 1，否则 count -= 1。

def solution(nums):
    cur_value = nums[0]
    cur_num = 1
    for num in nums[1:]:
        if num != cur_value:
            cur_num -= 1
            if cur_num == -1:
                cur_value = num
                cur_num = 1
        else:
            cur_num += 1
    return cur_value

Rob (dp) O(n)

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 400

解法 1：两个数组 max_rob、max_not_rob。max_rob[i] 表示打劫第 i 家时的最大金额，max_not_rob[i] 表示不打劫时的最大金额：
- max_rob[i] = max_not_rob[i-1] + nums[i]
- max_not_rob[i] = max(max_not_rob[i-1], max_rob[i-1])

解法 2：
- f(0) = nums[0]
- f(1) = max(num[0], num[1])
- f(k) = max(f(k-2) + nums[k], f(k-1))

def solution(nums):
    if not nums:
        return 0
    dp = [[0, 0] for _ in range(len(nums))]  # (rob, not_rob) * n
    dp[0][0], dp[0][1] = nums[0], 0
    for i in range(1, len(nums)):
        dp[i][0] = dp[i - 1][1] + nums[i]
        dp[i][1] = max(dp[i - 1])
    return max(dp[-1])


def solution(nums):
    last, now = 0, 0
    for i in nums:
        last, now = now, max(last + i, now)
    return now

numIslands (BFS DFS) O(mn)

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

双重 for 循环遍历所有 cell；遇到 ‘1’ 就 BFS（用栈/队列），把同一连通块的 ‘1’ 都改成 ‘0’。

def solution(grid):
    if not len(grid) or not len(grid[0]):
        return 0
    ret = 0
    n = len(grid)
    m = len(grid[0])
    for i in range(n):
        for j in range(m):
            if grid[i][j] == "1":
                grid[i][j] = "0"
                ret += 1
                queue = [(i, j)]
                while queue:
                    _i, _j = queue.pop(0)
                    if _i > 0 and grid[_i - 1][_j] == "1":
                        grid[_i - 1][_j] = "0"
                        queue.append((_i - 1, _j))
                    if _j > 0 and grid[_i][_j - 1] == "1":
                        grid[_i][_j - 1] = "0"
                        queue.append((_i, _j - 1))
                    if _i < n - 1 and grid[_i + 1][_j] == "1":
                        grid[_i + 1][_j] = "0"
                        queue.append((_i + 1, _j))
                    if _j < m - 1 and grid[_i][_j + 1] == "1":
                        grid[_i][_j + 1] = "0"
                        queue.append((_i, _j + 1))
    return ret

(mark) canFinish (dfs) O(n^3)

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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
All the pairs prerequisites[i] are unique.

visited 数组记录每个节点状态：初始为 0，开始递归时置 -1，递归结束置 1。递归中若发现 visited[i] == -1 直接返回 False（找到环）；若 visited[i] == 1 返回 True（已确认无环，避免重复搜索）。

def solution(numCourses, prerequisites):
    grid = [[] for _ in range(numCourses)]
    visited = [0] * numCourses

    for i, j in prerequisites:
        grid[i].append(j)

    def recusive(i):
        if visited[i] == -1:
            return False
        if visited[i] == 1:
            return True

        visited[i] = -1
        for j in grid[i]:
            if not recusive(j):
                return False

        visited[i] = 1
        return True

    for i in range(numCourses):
        if not recusive(i):
            return False
    return True

Trie (tree) O(n)

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

class TrieNode():

    def __init__(self, val):
        self.next = [None] * 26
        self.val = val


class Trie(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode(False)

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: None
        """
        node = self.root
        for w in word:
            idx = ord(w) - ord('a')
            if not node.next[idx]:
                node.next[idx] = TrieNode(False)
            node = node.next[idx]
        node.val = True

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        node = self.root
        for w in word:
            idx = ord(w) - ord('a')
            if not node.next[idx]:
                return False
            node = node.next[idx]
        return node.val

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        node = self.root
        for w in prefix:
            idx = ord(w) - ord('a')
            if not node.next[idx]:
                return False
            node = node.next[idx]
        return True

(mark) findKthLargest (heap, quickselect) O(nlogn)

Given an integer array nums and an integer k, return the k^th largest element in the array.

Note that it is the k^th largest element in the sorted order, not the k^th distinct element.

Can you solve it without sorting?

Example 1:

1 2	Input: nums = [3,2,1,5,6,4], k = 2 Output: 5

Example 2:

1 2	Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4

Constraints:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

堆解法直接用 heap。quickselect 类似快排：每次选 pivot 把数组划成两部分；若 len(left_part) == k-1 就返回 pivot；否则在大的那一部分继续找第 k 大或第 k-len(left_part)-1 大。

# O(klogk+2(n-k)logk)
def solution(nums, k):
    import heapq
    k_heap = nums[0:k]
    heapq.heapify(k_heap)
    for i in range(k, len(nums)):
        heapq.heappush(k_heap, nums[i])
        heapq.heappop(k_heap)
    return heapq.heappop(k_heap)


# O(n)
def solution(nums, k):

    def recursive(nums, k):
        pivot = nums.pop(len(nums) // 2)
        right = [num for num in nums if num > pivot]
        lr = len(right)
        if k == lr + 1:
            return pivot
        elif k < lr + 1:
            return recursive(right, k)
        else:
            left = [num for num in nums if num <= pivot]
            return recursive(left, k - lr - 1)

    return recursive(nums, k)

maximalSquare (dp) O(n^2)

Given an m x n binary matrix filled with 0‘s and 1‘s, find the largest square containing only 1‘s and return its area.

Example 1:

1 2	Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4

Example 2:

1 2	Input: matrix = [["0","1"],["1","0"]] Output: 1

Example 3:

1 2	Input: matrix = [["0"]] Output: 0

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] is '0' or '1'.
dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1，若 matrix[i][j] == ‘1’
max_v = max(max_v, dp[i][j])

def solution(matrix):
    if not matrix or not matrix[0]:
        return 0

    dp = [[int(x) for x in row] for row in matrix]
    max_v = 0
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if i == 0 or j == 0:
                max_v = max(max_v, dp[i][j])
            elif matrix[i][j] == "1":
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                max_v = max(max_v, dp[i][j])
            else:
                dp[i][j] == 0
    return max_v**2

invertTree (recursive) O(n)

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

1 2	Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]

Example 2:

1 2	Input: root = [2,1,3] Output: [2,3,1]

Example 3:

1 2	Input: root = [] Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

root.left, root.right = recursive(root.right), recursive(root.left)

def solution(root):

    def recursive(root):
        if root:
            root.left, root.right = recursive(root.right), recursive(root.left)
        return root

    return recursive(root)

isPalindrome (trick) O(n)

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

Example 1:

1 2	Input: head = [1,2,2,1] Output: true

Example 2:

1 2	Input: head = [1,2] Output: false

Constraints:

The number of nodes in the list is in the range [1, 10^5].
0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

快慢指针：fast 每次走两步、slow 每次走一步。fast 走到尾时把链表后半段反转，再与前半段逐一比较。

def solution(head):
    rev = ListNode(None)
    fast = slow = head
    while fast and fast.next:
        fast = fast.next.next
        _slow = slow
        slow = slow.next
        _slow.next = rev.next
        rev.next = _slow
    if fast:
        slow = slow.next
    rev = rev.next
    while rev and slow:
        if rev.val != slow.val:
            return False
        rev = rev.next
        slow = slow.next
    return True

lowestCommonAncestor (recursive) O(n)

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

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

1
2
3

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

1
2
3

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

1 2	Input: root = [1,2], p = 1, q = 2 Output: 1

Constraints:

The number of nodes in the tree is in the range [2, 10^5].
-10^9 <= Node.val <= 10^9
All Node.val are unique.
p != q
p and q will exist in the tree.

后序递归。count = recursive(root.left, p, q) + recursive(root.right, p, q)；若 root.val == p or == q，则 cur_count = 1 否则 0。当 count + cur_count == 2 时，记录答案。

def solution(root, p, q):
    low_desc = None

    def recursive(root):
        nonlocal low_desc
        if not root:
            return 0
        ret = recursive(root.left)
        if ret < 2:
            ret += recursive(root.right)
        if root.val in (q.val, p.val):
            ret += 1
        if ret == 2 and not low_desc:
            low_desc = root
        return ret

    recursive(root)
    return low_desc

productExceptSelf (two pointers, reverse list) O(n)

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

1 2	Input: nums = [1,2,3,4] Output: [24,12,8,6]

Example 2:

1 2	Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

两个数组：第一个记录左侧累积乘积，第二个记录右侧累积乘积，最后 result[i] = left[i] * right[i]。

def solution(nums):
    res = [1] * len(nums)
    p = 1
    for i in range(len(nums)):
        res[i] = p
        p *= nums[i]

    right = 1
    for i in range(len(nums) - 1, -1, -1):
        res[i] *= right
        right *= nums[i]
    return res

maxSlidingWindow (trick) O(n)

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.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

1 2	Input: nums = [1], k = 1 Output: [1]

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

不需要每次重算最大值。维护一个结果数组，每次：
- 新进入的值 ≥ 当前最大：直接 append 新值
- 即将出窗的值 < 当前最大：append 当前最大（不变）
- 否则才在窗口内重新求 max

def solution(nums, k):
    if not nums:
        return nums

    ret = [max(nums[:k])]
    for i in range(1, len(nums) - k + 1):
        if nums[i + k - 1] >= ret[-1]:
            ret.append(nums[i + k - 1])
        elif nums[i - 1] < ret[-1]:
            ret.append(ret[-1])
        else:
            ret.append(max(nums[i:i + k]))
    return ret

(mark) searchMatrix (trick) O(m+n)

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example 1:

1 2	Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true

Example 2:

1 2	Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 Output: false

Constraints:

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10^9 <= matrix[i][j] <= 10^9
All the integers in each row are sorted in ascending order.
All the integers in each column are sorted in ascending order.
-10^9 <= target <= 10^9

第一行从右端开始，把比 target 大的列排除，记录下当前列下标；第二行从该列继续往左排除…… 找到 target 返回 True，否则 False。

def solution(matrix, target):
    if len(matrix) == 0 or len(matrix[0]) == 0:
        return False
    j = len(matrix[0]) - 1
    for i in range(len(matrix)):
        while j >= 0 and matrix[i][j] > target:
            j -= 1
        if matrix[i][j] == target:
            return True
    return False

numSquares (dp) O(n^1.5)

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

1
2
3

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

1
2
3

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

1 <= n <= 10^4

候选范围 [1, floor(n^0.5)]。dp[i] = min(dp[i - j^2] + 1)，j 取所有候选。

import math, sys


def solution(n):
    dp = [0] * (n + 1)
    squares = [i**2 for i in range(1, int(math.sqrt(n)) + 1)]
    dp[1] = 1
    for i in range(2, n + 1):
        min_v = sys.maxsize
        for j in squares:
            if i - j < 0:
                break
            min_v = min(min_v, dp[i - j])
        dp[i] = min_v + 1
    return dp[-1]

moveZeroes (trick) O(n)

Given an integer array nums, move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

1 2	Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]

Example 2:

1 2	Input: nums = [0] Output: [0]

Constraints:

1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

Follow up: Could you minimize the total number of operations done?

每遇到非零值，就把它和”第一个 0”的位置交换。维护 index 记录第一个 0 的位置：nums[i] != 0 时 swap 并 index += 1，否则不动。

def solution(nums):
    n = len(nums)
    if n == 0 or n == 1:
        return nums
    i = 0
    while i < n and nums[i] != 0:
        i += 1
    j = i
    while True:
        while j < n and nums[j] == 0:
            j += 1
        if j >= n:
            break
        nums[i], nums[j] = nums[j], nums[i]
        i += 1


def solution(nums):
    n = len(nums)
    if n == 0 or n == 1:
        return nums
    i = 0
    while i < n and nums[i] != 0:
        i += 1
    for j in range(i + 1, n):
        if nums[j] != 0:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1

findDuplicate (trick) O(n)

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 using only constant extra space.

Example 1:

1 2	Input: nums = [1,3,4,2,2] Output: 2

Example 2:

1 2	Input: nums = [3,1,3,4,2] Output: 3

Example 3:

1 2	Input: nums = [3,3,3,3,3] Output: 3

Constraints:

1 <= n <= 10^5
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

How can we prove that at least one duplicate number must exist in nums?
Can you solve the problem in linear runtime complexity?

转化为”链表找环入口”：把下标 i 看成节点，i → nums[i]。因为有重复值，这条链一定有环；环的入口就是重复值。

def solution(nums):
    slow = nums[0]
    fast = nums[nums[0]]
    while fast != slow:
        fast = nums[nums[fast]]
        slow = nums[slow]
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

MedianFinder (trick) O(nlogn)

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Constraints:

-10^5 <= num <= 10^5
There will be at least one element in the data structure before calling findMedian.
At most 5 * 10^4 calls will be made to addNum and findMedian.

Follow up:

If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

解法 1：维护一个有序列表，每次用二分找到插入位置。

解法 2：双堆 —— 大顶堆（存较小一半）+ 小顶堆（存较大一半）。每次插入时若两堆大小相等，先入大堆再 pop 一个最大值送进小堆；否则反之。求中位数：两堆等长时取两个堆顶平均，否则取大堆堆顶。

import heapq


class MedianFinder(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.left_heap = []
        self.right_heap = []
        heapq.heapify(self.left_heap)  # big heap
        heapq.heapify(self.right_heap)  # small heap

    def addNum(self, num):
        """
        :type num: int
        :rtype: None
        """
        if len(self.left_heap) == len(self.right_heap):
            heapq.heappush(self.left_heap,
                           -heapq.heappushpop(self.right_heap, num))
        else:
            heapq.heappush(self.right_heap,
                           -heapq.heappushpop(self.left_heap, -num))

    def findMedian(self):
        """
        :rtype: float
        """
        if len(self.left_heap) == len(self.right_heap):
            return float(-self.left_heap[0] + self.right_heap[0]) / 2.
        else:
            return float(-self.left_heap[0])

Serialize (bfs) O(n)

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

1 2	Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5]

Example 2:

1 2	Input: root = [] Output: []

Constraints:

The number of nodes in the tree is in the range [0, 10^4].
-1000 <= Node.val <= 1000

按完全二叉树编号：node[i] 的子节点是 node[2i] 和 node[2i+1]。

def serialize(self, root):
    """Encodes a tree to a single string.
    
    :type root: TreeNode
    :rtype: str
    """
    if not root:
        return ''
    out = []
    queue = collections.deque([root])
    while queue:
        node = queue.popleft()
        out.append(str(node.val) if node else '#')
        if node:
            queue.append(node.left)
            queue.append(node.right)
    return ' '.join(out)

def deserialize(self, data):
    """Decodes your encoded data to tree.
    
    :type data: str
    :rtype: TreeNode
    """
    if not data:
        return None
    out = data.split()
    bfs = [TreeNode(int(i)) if i != '#' else None for i in out]
    slow_idx = 0  # the id in array nodex
    fast_idx = 1  # the id in array bfs
    root = bfs[0]
    nodes = [root]
    while slow_idx < len(nodes):
        node = nodes[slow_idx]
        slow_idx += 1  # each time we handle one node in nodes
        node.left = bfs[fast_idx]
        node.right = bfs[fast_idx + 1]
        fast_idx += 2  # each time we only handle two nodes in bfs
        if node.left:
            nodes.append(node.left)
        if node.right:
            nodes.append(node.right)
    return root

lengthOfLIS(dp)

Given an integer array nums, return *the length of the longest **strictly increasing ***subsequence.

Example 1:

1
2
3

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

1 2	Input: nums = [0,1,0,3,2,3] Output: 4

Example 3:

1 2	Input: nums = [7,7,7,7,7,7,7] Output: 1

Constraints:

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

lengthOfLIS(dp) O(n^2)

dp[i] 表示以位置 i 结尾的最长上升子序列长度。每次把当前值与之前所有值比较，若当前更大就尝试更新：

def lengthOfLIS(nums):
    if len(nums) == 0:
        return 0
    dp = [0] * len(nums)
    dp[0] = 1
    for i in range(1, len(nums)):
        max_t = 0
        for j in range(0, i):
            if nums[i] > nums[j]:
                max_t = max(max_t, dp[j]) # # longest length till now plus current 
        dp[i] = max_t + 1
    return max(dp)

(mark) lengthOfLIS(dp) O(nlogn)

dp[i] 存放当前已遍历元素能构成的”潜在上升子序列”的第 i 个位置候选值。

例：输入 [0, 8, 4, 12, 2]：
逐元素扫描，每次在 dp 里二分找到第一个 ≥ 当前值的位置替换。

0 → dp = [0]
8 → dp = [0, 8]
4 → dp = [0, 4]
12 → dp = [0, 4, 12]
2 → dp = [0, 2, 12]

注意：最终的 dp 不是真正的 LIS，但它的长度就是 LIS 长度。

为什么把 [0, 4, 12] 改成 [0, 2, 12] 仍然合法？(1) 不破坏长度本身；(2) 之后碰到比 2 大的值时，可以接在 2 后面延伸出更长的 LIS。

# o(n^2)
def solution(nums):
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)


# O(n * logn)
def solution(nums):
    dp = [0] * len(nums)
    size = 0
    for n in nums:
        i, j = 0, size
        while i != j:
            m = (i + j) // 2
            if dp[m] < n:
                i = m + 1
            else:
                j = m
        dp[i] = n
        size = max(size, i + 1)
    return size

removeInvalidParentheses(recursive) O(n^2)

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.

Example 1:

1 2	Input: s = "()())()" Output: ["(())()","()()()"]

Example 2:

1 2	Input: s = "(a)())()" Output: ["(a())()","(a)()()"]

Example 3:

1 2	Input: s = ")(" Output: [""]

Constraints:

1 <= s.length <= 25
s consists of lowercase English letters and parentheses '(' and ')'.
There will be at most 20 parentheses in s.

用计数器扫描：’(‘ 时 +1，’)’ 时 -1。一旦计数器为负，说明前缀里 ‘)’ 比 ‘(‘ 多。

要修复，需要删一个 ‘)’。删哪一个？理论上前缀里任意一个都行，但为避免重复结果（如 “())” 删 s[1] 或 s[2] 都得到 “()”），约定只删一连串 ‘)’ 中的第一个。

删完后前缀合法，再递归处理剩下部分。但还需要追加信息：上一次删除的位置。否则两次删除按不同顺序会产生重复。

所以维护两个游标：i 表示扫描到哪、j 表示从哪开始可以删 ‘)’。i 与 j 之间的每一个 ‘)’ 都尝试递归。

那 ‘(‘ 怎么办？比如 s = '(()(('。答案是从右往左做一遍。更聪明的做法：把字符串反转，复用同一段代码！

def removeInvalidParentheses(self, s):
    """
    :type s: str
    :rtype: List[str]
    """
    def removeHelper(s, output, iStart, jStart, openParen, closedParen):
        numOpenParen, numClosedParen = 0, 0
        for i in range(iStart, len(s)):
            if s[i] == openParen:
                numOpenParen += 1
            if s[i] == closedParen:
                numClosedParen += 1
            # We have only ONE extra closed paren we need to remove
            if numClosedParen > numOpenParen:
                print(s)
                if openParen == '(':
                    print("positive")
                elif openParen == ')':
                    print('negative')
                print("i=", i, numOpenParen, numClosedParen)
                # Try removing this ONE closed paren at each position, skipping duplicates
                print(jStart, i)
                # jStart: always to search the first closedParen which can be removed
                for j in range(jStart, i+1):  # <=
                    # can be the first char,
                    # or the char which previous char isn't closedParen, removing each one of the consequtive closedParen actually is the same
                    if s[j] == closedParen and (j == jStart or s[j-1] != closedParen): # since when j == jStart, there isn't j-1
                        # Recursion: iStart = i since we now have valid # closed parenthesis thru i. jStart = j prevents duplicates
                        # at the next recursion, we only need to search the iStart from the current i, and search the jStart from the current j
                        # since we found the first invalid closedParen at the i, and we have removed a closedParen at j
                        print("remove, j=", j, s[j])
                        removeHelper(s[:j]+s[j+1:], output,
                                     i, j, openParen, closedParen)
                return
        reversed = s[::-1]
        print(reversed, "now out of the loop")
        if openParen == '(':
            removeHelper(reversed, output, 0, 0, ')', '(')
        else:
            output.append(reversed)

    output = []
    removeHelper(s, output, 0, 0, '(', ')')
    return output

maxProfit(dp) O(3n)

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

1
2
3

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Example 2:

1 2	Input: prices = [1] Output: 0

Constraints:

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

stack[n][3]：stack[i][0] 记录冷冻期，stack[i][1] 记录买入，stack[i][2] 记录卖出。
- 冷冻：取前一天三种状态的最大值 stack[i][0] = max(stack[i-1])
- 买入：只能从前一天的冷冻期转过来 stack[i][1] = stack[i-1][0] - prices[i]。不会出现 [买, 冷, 买] 因为冷冻已取了 max。
- 卖出：stack[i][2] = bought + prices[i]。bought = max(bought, stack[i][1])，记录当下最便宜的买入成本。

维护 bought 是为了避免 [卖, 休, 卖] 的退化路径，每步都保最大 bought（即最小成本）。

def solution(prices):
    if not prices:
        return 0
    n = len(prices)
    buy, sell, cooldown = [0] * n, [0] * n, [0] * n
    bought = buy[0] = -prices[0]
    for i in range(1, n):
        buy[i] = cooldown[i - 1] - prices[i]
        sell[i] = bought + prices[i]
        cooldown[i] = max(buy[i - 1], sell[i - 1], cooldown[i - 1])
        bought = max(bought, buy[i])
    return max(buy[-1], sell[-1], cooldown[-1])

maxCoins(dp) O(n^3)

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 i^th 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.

Example 1:

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

Example 2:

1 2	Input: nums = [1,5] Output: 10

Constraints:

n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100

dp[i][j] 表示已经把 i 与 j 之间的气球全部戳掉后所获得的最大金币数。转移：

1 2	for k in range(i+1, j): coins = max(coins, nums[i]nums[k]nums[j] + recursion(i, k) + recursion(k, j))

含义：要让 [i, j] 之间金币最大，枚举每个气球 k 作为最后一个被戳的。也就是先把 (i, k) 和 (k, j) 之间的气球戳完，最后只剩 i、k、j 三个。

注意：在数组首尾各 append 一个 1，每次只处理 i+1 到 j（跳过哨兵）。这个 trick 保证 nums[i] * nums[k] * nums[j] 公式成立。

def solution(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    def recursive(i, j):
        if dp[i][j] or j == i + 1:
            return dp[i][j]
        coins = 0
        for k in range(i + 1, j):
            # we firstly burst (i,k) and (k,j), only leave (i,k,j) three ballons
            coins = max(
                coins,
                nums[i] * nums[k] * nums[j] + recursive(i, k) + recursive(k, j))
        dp[i][j] = coins
        return coins

    return recursive(0, n - 1)

coinChange(dp) O(nm)

You are given an integer array coins representing coins of different denominations and an integer amount representing 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.

Example 1:

1
2
3

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

1 2	Input: coins = [2], amount = 3 Output: -1

Example 3:

1 2	Input: coins = [1], amount = 0 Output: 0

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

dp[i] = min(dp[i - coin] + 1) for coin in coins。

def solution(coins, amount):
    if len(coins) == 0:
        return -1
    if amount == 0:
        return 0

    coins = sorted(set(coins), reverse=True)
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if i == c:
                dp[i] = 1
                break
            elif i > c and dp[i - c] > 0:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return -1 if dp[-1] > amount else dp[-1]

Rob(dp in a tree), O(n)

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1:

1
2
3

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

1
2
3

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
0 <= Node.val <= 10^4

def solution(root):

    def recursive(root):
        if not root:
            return 0, 0

        l_rob, l_not_rob = recursive(root.left)
        r_rob, r_not_rob = recursive(root.right)
        rob = l_not_rob + r_not_rob + root.val
        not_rob = max(l_rob, l_not_rob) + max(r_rob, r_not_rob)
        return rob, not_rob

    return max(recursive(root))

countBits(dp) O(n)

Given an integer n, return *an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1‘s in the binary representation of *i.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Constraints:

0 <= n <= 10^5

Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

f[i] = f[i // 2] + i % 2

直观上：右移一位等于减半，再加上是否末位为 1。

def solution(num):
    dp = [0] * (num + 1)
    for i in range(1, num + 1):
        dp[i] = dp[i // 2] + i % 2
    return dp

topKFrequent(heap) O(nlogn)

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

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Example 2:

Input: nums = [1], k = 1

Output: [1]

Example 3:

Input: nums = [1,2,1,2,1,2,3,1,3,2], k = 2

Output: [1,2]

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

from collections import defaultdict
import heapq


def solution(nums, k):
    hash_map = defaultdict(int)
    for num in nums:
        hash_map[num] += 1
    ret = []
    i = 0
    for key, val in hash_map.items():
        if i < k:
            heapq.heappush(ret, (val, key))
        else:
            heapq.heappushpop(ret, (val, key))
        i += 1
    return [v for k, v in ret]

decodeString(stack) O(n)

Given an encoded string, return its decoded string.

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

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 10^5.

Example 1:

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

Example 2:

1 2	Input: s = "3[a2[c]]" Output: "accaccacc"

Example 3:

1 2	Input: s = "2[abc]3[cd]ef" Output: "abcabccdcdcdef"

Constraints:

1 <= s.length <= 30
s consists of lowercase English letters, digits, and square brackets '[]'.
s is guaranteed to be a valid input.
All the integers in s are in the range [1, 300].

栈解法：遇到 ‘]’ 时 pop 出 ‘[‘ 之前的字符串，再继续 pop 数字字符拼成倍数，把字符串重复后压回栈。

def solution(s):
    stack = [""]
    num = ""
    for c in s:
        if c.isdigit():
            num += c
        elif c == "[":
            stack.extend([num, ""])
            num = ""
        elif c == "]":
            chars = stack.pop()
            n_chars = stack.pop()
            stack[-1] += chars * int(n_chars)
        else:
            stack[-1] += c
    return stack.pop()

reconstructQueue(trick) O(nlog)

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [h_i, k_i] represents the i^th person of height h_i with exactly k_i other people in front who have a height greater than or equal to h_i.

Reconstruct and return *the queue that is represented by the input array *people. The returned queue should be formatted as an array queue, where queue[j] = [h_j, k_j] is the attributes of the j^th person in the queue (queue[0] is the person at the front of the queue).

Example 1:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:

1 2	Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Constraints:

1 <= people.length <= 2000
0 <= h_i <= 10^6
0 <= k_i < people.length
It is guaranteed that the queue can be reconstructed.

先按 (-x[0], x[1]) 排序：身高降序、k 升序。

然后按每个 tuple 的第二个元素（k）作为下标插入：result.insert(p[1], p)。

原理：一个 tuple 的位置只受比它高的 tuple 影响，所以先处理高的；同身高里 k 小的先插入，能保证后续插入不打乱已经成立的”前面有几个 ≥ 自己”的条件。

def solution(people):
    people = sorted(people, key=lambda x: (-x[0], x[1]))
    ret = []
    for p in people:
        ret.insert(p[1], p)
    return ret

canPartition

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

1
2
3

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

1
2
3

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100

canPartition(dp) O(n*s), n<=200, s<=10000

矩阵 dp[n][s]，n 是元素数，s = sum(input)//2。dp[i][j] = True 表示从前 i 个数中能选出和为 j 的子集。
- 先令 dp[i][nums[i]-1] = 1，表示只选第 i 个值
- dp[i][j] 来自两种情况：不选第 i 个 dp[i-1][j]；选第 i 个 dp[i-1][j-nums[i]]

Partition(dp) O(2^n with cutting branch)

递归调用 helper(nums[i+1:], target - num) for i, num in enumerate(nums)，剪枝即可。

# O(N * S)
def solution(nums):
    sum_v = sum(nums)
    if sum_v % 2 == 1:
        return False
    if max(nums) > sum_v // 2:
        return False
    scale = sum_v // 2 + 1
    dp = [[False] * scale for _ in range(len(nums))]

    nums = sorted(nums, reverse=True)
    dp[0][nums[0]] = True
    for i in range(1, len(nums)):
        dp[i][nums[i]] = True
        for j in range(scale - 1, 0, -1):
            if dp[i - 1][j]:
                dp[i][j] = True
            if j > nums[i] and dp[i - 1][j - nums[i]]:
                dp[i][j] = True
            if dp[i][-1]:
                return True
    return dp[-1][-1]

def solution(nums):

    def recursive(nums, target):
        for i, num in enumerate(nums):
            if num > target:
                return False
            elif num == target:
                return True
            elif recursive(nums[i + 1:], target - nums[i]):
                return True
        return False

    sum_v = sum(nums)
    if sum_v % 2 == 1:
        return False
    nums = sorted(nums, reverse=True)
    return recursive(nums, sum_v // 2)

pathSum(dp) O(n)

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

Example 1:

1
2
3

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:

1 2	Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: 3

Constraints:

The number of nodes in the tree is in the range [0, 1000].
-10^9 <= Node.val <= 10^9
-1000 <= targetSum <= 1000

假设所有路径都从 root 出发。维护一个”老的累计和” oldPathSum 和当前累计和 currPathSum：当 oldPathSum == currPathSum - target 时，就找到一条满足条件的路径，因此 result += cache.get(oldPathSum, 0)。

注意：进入节点时 cache[currPathSum] = cache.get(currPathSum, 0) + 1，递归子节点；离开节点时 cache[currPathSum] -= 1。

def solution(root, target):

    def recursive(root, cur_sum):
        if root:
            nonlocal ret
            cur_sum += root.val
            ret += cache.get(cur_sum - target, 0)
            cache[cur_sum] = cache.get(cur_sum, 0) + 1
            recursive(root.left, cur_sum)
            recursive(root.right, cur_sum)
            cache[cur_sum] -= 1

    ret = 0
    cache = {0: 1}
    recursive(root, 0)
    return ret

findAnagrams(cache) O(n)

Given two strings s and p, return an array of all the start indices of p‘s anagrams in s. You may return the answer in any order.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

1 <= s.length, p.length <= 3 * 10^4
s and p consist of lowercase English letters.

用一个长度 26 的桶记录当前子串字符频次。每次滑动窗口更新桶，与 target 桶比较。

def solution(s, p):
    import collections
    ret = []
    p_counter = collections.Counter(p)
    s_counter = collections.Counter(s[:len(p) - 1])
    for i in range(len(p) - 1, len(s)):
        s_counter[s[i]] += 1
        pre_i = i - len(p) + 1
        if s_counter == p_counter:
            ret.append(pre_i)
        s_counter[s[pre_i]] -= 1
        if s_counter[s[pre_i]] == 0:
            del s_counter[s[pre_i]]
    return ret


def solution(s, p):
    l = len(p)
    p_frequency = [0] * 26
    ss_frequency = [0] * 26
    res = []
    for c in p:
        p_frequency[ord(c) - 97] += 1
    for c in s[0:l]:
        ss_frequency[ord(c) - 97] += 1
    if p_frequency == ss_frequency:
        res.append(0)

    for i in range(1, len(s) - l + 1):
        ss_frequency[ord(s[i - 1]) - 97] -= 1
        ss_frequency[ord(s[i + l - 1]) - 97] += 1
        if p_frequency == ss_frequency:
            res.append(i)

    return res

findDisappearedNumbers(trick) (n)

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

1 2	Input: nums = [4,3,2,7,8,2,3,1] Output: [5,6]

Example 2:

1 2	Input: nums = [1,1] Output: [2]

Constraints:

n == nums.length
1 <= n <= 10^5
1 <= nums[i] <= n

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

遍历数组，把”已出现”的对应位置标记为负数。最后剩下正数的下标 +1 就是缺失的数。

def solution(nums):
    n = len(nums)
    for i in range(n):
        _num = abs(nums[i])
        if _num <= n:
            nums[_num - 1] = -abs(nums[_num - 1])

    ret = []
    for i in range(n):
        if nums[i] > 0:
            ret.append(i + 1)
    return ret

findTargetSumWays(dp) O(n*2s) s=sum(nums)

dp 矩阵 dp[0:n][-s:s]：第 0 行 dp[0][±nums[0]] = 1；后续行 dp[i][j] = dp[i][j - nums[i]] + dp[i][j + nums[i]]。

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

Example 2:

1 2	Input: nums = [1], target = 1 Output: 1

Constraints:

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

def solution(nums, S):
    sum_v = sum(nums)
    if sum_v < S: 
        return 0
    n = len(nums)
    dp = [0] * (2 * sum_v + 1)
    dp[nums[0]] += 1
    dp[-nums[0]] += 1
    for n in nums[1:]:
        _dp = [0] * (2 * sum_v + 1)
        for i in range(-sum_v, sum_v + 1):
            if i + n <= sum_v:
                _dp[i] += dp[i + n]
            if i - n >= -sum_v:
                _dp[i] += dp[i - n]
        dp = _dp
    return dp[S]

diameterOfBinaryTree(tree dp) (n)

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

1
2
3

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

1 2	Input: root = [1,2] Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
-100 <= Node.val <= 100

从叶子开始，每个父节点更新 result = max(result, a + b + 1)，a/b 分别是来自左、右子树的最长路径长度。返回 max(a, b) 给上一层作为它能向上延伸的最长链。

def solution(root):

    def recusive(root):
        nonlocal ret
        if not root:
            return 0, 0

        l = recusive(root.left)
        r = recusive(root.right)
        ret = max(ret, max(l) + max(r))
        return max(l) + 1, max(r) + 1

    ret = 0
    recusive(root)
    return ret

subarraySum(hash trick) O(n)

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

1 2	Input: nums = [1,1,1], k = 2 Output: 2

Example 2:

1 2	Input: nums = [1,2,3], k = 3 Output: 2

Constraints:

1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7

跟 findTargetSumWays 思路类似：前缀和 + 哈希。

# O(n^2)
def solution(nums, k):
    n = len(nums)
    ret = 0
    dp = [[0] * (n + 1) for _ in range(n)]  # (start_pos, len)
    for i in range(1, n + 1):
        for j in range(0, n - i + 1):
            if i == 1:
                dp[j][i] = nums[j]
            else:
                dp[j][i] = nums[j] + dp[j + 1][i - 1]
            if dp[j][i] == k:
                ret += 1
    return ret

# O(n)
def solution(nums, k):
    cache = {0: 1}
    cur_sum = 0
    ret = 0
    for n in nums:
        cur_sum += n
        ret += cache.get(cur_sum - k, 0)
        cache[cur_sum] = cache.get(cur_sum, 0) + 1
    return ret

findUnsortedSubarray(trick) O(n)

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.

Example 1:

1
2
3

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Example 2:

1 2	Input: nums = [1,2,3,4] Output: 0

Example 3:

1 2	Input: nums = [1] Output: 0

Constraints:

1 <= nums.length <= 10^4
-10^5 <= nums[i] <= 10^5

Follow up: Can you solve it in O(n) time complexity?

先从左往右扫，维护当前最大值，发现 nums[i] < cur_max 就更新 right。再从右往左扫，维护当前最小值，发现 nums[i] > cur_min 就更新 left。最终结果 max(right - left + 1, 0)。

def solution(nums):
    n = len(nums)
    if n <= 1:
        return 0
    right = 0
    cur_max = nums[0]
    for i in range(1, n):
        if nums[i] < cur_max:
            right = i
        cur_max = max(cur_max, nums[i])
        

    cur_min = nums[-1]
    left = len(nums)-1
    for i in range(n - 2, -1, -1):
        if nums[i] > cur_min:
            left = i
        cur_min = min(cur_min, nums[i])
    return max(right - left + 1, 0)

mergeTrees(recursive) O(n)

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

Example 1:

1 2	Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] Output: [3,4,5,5,4,null,7]

Example 2:

1 2	Input: root1 = [1], root2 = [1,2] Output: [2,2]

Constraints:

The number of nodes in both trees is in the range [0, 2000].
-10^4 <= Node.val <= 10^4

def solution(t1, t2):

    def recursive(t1, t2):
        if not t1 and not t2:
            return None
        elif not t1:
            return t2
        elif not t2:
            return t1
        else:
            t1.left = recursive(t1.left, t2.left)
            t1.right = recursive(t1.right, t2.right)
            t1.val = t1.val + t2.val
            return t1

    return recursive(t1, t2)

leastInterval(trick) O(n)

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there’s a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU intervals required to complete all tasks.

Example 1:

Input: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2

Output: 8

Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.

After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3^rd interval, neither A nor B can be done, so you idle. By the 4^th interval, you can do A again as 2 intervals have passed.

Example 2:

Input: tasks = [“A”,”C”,”A”,”B”,”D”,”B”], n = 1

Output: 6

Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.

With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

Input: tasks = [“A”,”A”,”A”, “B”,”B”,”B”], n = 3

Output: 10

Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.

There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints:

1 <= tasks.length <= 10^4
tasks[i] is an uppercase English letter.
0 <= n <= 100

def solution(tasks, n):
    cache = [0] * 26
    for c in tasks:
        cache[ord(c) - ord('A')] += 1
    cache.sort(reverse=True)
    max_v = cache[0] - 1
    idle_slots = max_v * n
    for i in range(1, len(cache)):
        if cache[i] == 0:
            break
        idle_slots -= min(cache[i], max_v)
    return idle_slots + len(tasks) if idle_slots > 0 else len(tasks)

countSubstrings

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

1
2
3

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

1
2
3

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

1 <= s.length <= 1000
s consists of lowercase English letters.

countSubstrings() O(n^2)

n = len(s)
if n <= 1:
    return n
dp = [[0] * (n + 1) for _ in range(n)]  # (start_pos, len)
ret = 0
for i in range(1, n + 1):
    for j in range(0, n - i + 1):
        if i == 1 or (i == 2 and
                      s[j] == s[j + 1]) or (s[j] == s[j + i - 1] and
                                            dp[j + 1][i - 2]):
            dp[j][i] = 1
            ret += 1
return ret

countSubstrings(Manacher’s Algorithm?) O(n)

dailyTemperatures(stack) O(n)

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i^th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

1 2	Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]

Example 2:

1 2	Input: temperatures = [30,40,50,60] Output: [1,1,1,0]

Example 3:

1 2	Input: temperatures = [30,60,90] Output: [1,1,0]

Constraints:

1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100

单调栈。把比栈顶小的值入栈；遇到比栈顶大的就不断弹栈，把弹出位置的答案设为 current_position - popped_position。

def solution(T):
    ret = [0] * len(T)
    stack = [(T[0], 0)]
    for i in range(1, len(T)):
        top = stack[-1]
        if T[i] > top[0]:
            while stack and T[i] > stack[-1][0]:
                _t = stack.pop()
                ret[_t[1]] = i - _t[1]
        stack.append((T[i], i))
    return ret

LeetCode Top 100 刷题笔记

lengthOfLongestSubstring (cache) O(n)

findMedianSortedArrays (binary search) O(log(m+n))

longestPalindrome (dp) O(N^2)

isMatch (recursive with memo) O(MN)

maxArea (trick) O(n)

(mark) threeSum (trick) O(n^2)

letterCombinations (full permutation), O(3^N * 4^M)

removeNthFromEnd (trick) O(n)

generateParenthesis (recursive) O(4^n/√2)

nextPermutation (trick), O(n)

longestValidParentheses

longestValidParentheses (stack trick) O(n)

(mark) longestValidParentheses (dp) O(n)

(mark) search (binary search trick) O(log n)

searchRange (Binary Search trick) O(log n)

combinationSum (dfs) O(exponential)

firstMissingPositive (trick: hash with mod position) O(n)

Trap (two dp, left and right) O(n)

Permute (loop call recusive) O(2^n)

Rotate (trick) O(n^2)

(mark) groupAnagrams (hash) O(m)

(mark) maxSubArray (trick) O(n)

canJump (greedy) O(n)

merge (greedy) O(n)

uniquePaths (dp) O(m+n)

minPathSum (dp) O(mn)

climbStairs (dp) O(n)

(mark) minDistance (dc) O(mn)

sortColors (trick) O(n)

minWindow (trick hash) O(n)

Subsets (dfs) O(2^n)

(mark) Exist (dfs) O(mn * len(words))

largestRectangleArea (left and right dp) O(n)

maximalRectangle (greedy) O(mn)

inorderTraversal (iterative) O(n)

numTrees (dp) O(n^2)

isValidBST (post-order, dfs) O(n)

(mark) isSymmetric (dfs or bfs) O(n)

(mark) buildTree (recursive) O(n)

(mark) Flatten (iterative pre-order dfs) O(n)

maxProfit (trick) O(n)

maxPathSum (tree dp) O(n)

longestConsecutive (hash) O(n)

copyRandomList (hash) O(n)

wordbreak (dp) O(mn)

DetectCycle (trick) O(n)

LRUCache (double linked list) O(1)

SortList (merge sort or quick sort) O(nlogn)

(mark) maxProduct (greedy) O(n)

MinStack (trick) O(n)

GetIntersectionNode (trick) O(m+n)

MajorityElement (trick) O(n)

Rob (dp) O(n)

numIslands (BFS DFS) O(mn)

(mark) canFinish (dfs) O(n^3)

Trie (tree) O(n)

(mark) findKthLargest (heap, quickselect) O(nlogn)

maximalSquare (dp) O(n^2)

invertTree (recursive) O(n)

isPalindrome (trick) O(n)

lowestCommonAncestor (recursive) O(n)

productExceptSelf (two pointers, reverse list) O(n)

maxSlidingWindow (trick) O(n)

(mark) searchMatrix (trick) O(m+n)

numSquares (dp) O(n^1.5)

moveZeroes (trick) O(n)

findDuplicate (trick) O(n)

MedianFinder (trick) O(nlogn)

Serialize (bfs) O(n)

lengthOfLIS(dp)

lengthOfLIS(dp) O(n^2)

(mark) lengthOfLIS(dp) O(nlogn)

removeInvalidParentheses(recursive) O(n^2)

maxProfit(dp) O(3n)

maxCoins(dp) O(n^3)

coinChange(dp) O(nm)

Rob(dp in a tree), O(n)

countBits(dp) O(n)

topKFrequent(heap) O(nlogn)