High Frequency

See notes how I got this list.

import IPython; IPython.display.HTML('''<script>code_show=true; function code_toggle() { if (code_show){ $('div.nbinput').show(); } else { $('div.nbinput').hide(); } code_show = !code_show} $( document ).ready(code_toggle);</script><form action="javascript:code_toggle()"><input type="submit" value="Click here to toggle on/off the raw code."></form>''')

題目名稱	難度	Freq	ZXI	BL75	LC75	LC150
1. Two Sum	Easy	4	o	o	o	o
121. Best Time to Buy and Sell Stock	Easy	4	o	o	o	o
20. Valid Parentheses	Easy	4	o	o	o	o
21. Merge Two Sorted Lists	Easy	4	o	o	o	o
242. Valid Anagram	Easy	4	o	o	o	o
226. Invert Binary Tree	Easy	4	o	o	o	o
141. Linked List Cycle	Easy	4	o	o	o	o
206. Reverse Linked List	Easy	4	o	o	o	o
53. Maximum Subarray	Medium	4	o	o	o	o
238. Product of Array Except Self	Medium	4	o	o	o	o
102. Binary Tree Level Order Traversal	Medium	4	o	o	o	o
56. Merge Intervals	Medium	4	o	o	o	o
33. Search in Rotated Sorted Array	Medium	4	o	o	o	o
3. Longest Substring Without Repeating Characters	Medium	4	o	o	o	o
139. Word Break	Medium	4	o	o	o	o
207. Course Schedule	Medium	4	o	o	o	o
125. Valid Palindrome	Easy	3	o	o	_	o
217. Contains Duplicate	Easy	3	o	o	_	o
70. Climbing Stairs	Easy	3	o	o	o	_
252. Meeting Rooms	Easy	3	o	o	o	_
253. Meeting Rooms II	Medium	3	o	o	o	_
49. Group Anagrams	Medium	3	o	o	_	o
5. Longest Palindromic Substring	Medium	3	o	o	_	o
647. Palindromic Substrings	Medium	3	o	o	_	o
271. Encode and Decode Strings	Medium	3	_	o	o	o
230. Kth Smallest Element in a BST	Medium	3	o	o	_	o
235. Lowest Common Ancestor of BST	Medium	3	o	o	_	o
208. Implement Trie	Medium	3	o	o	_	o
211. Add and Search Word	Medium	3	o	o	_	o
347. Top K Frequent Elements	Medium	3	o	o	_	o
322. Coin Change	Medium	3	o	o	o	_
198. House Robber	Medium	3	o	o	o	_
62. Unique Paths	Medium	3	o	o	o	_
55. Jump Game	Medium	3	o	o	o	_
133. Clone Graph	Medium	3	o	o	o	_
200. Number of Islands	Medium	3	o	o	o	_
261. Graph Valid Tree	Medium	3	o	o	o	_
57. Insert Interval	Medium	3	o	o	o	_
435. Non-overlapping Intervals	Medium	3	o	o	o	_
212. Word Search II	Hard	3	o	o	_	o
295. Find Median from Data Stream	Hard	3	o	o	_	o
269. Alien Dictionary	Hard	3	o	o	o	_

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        cur = self
        vals = []
        while cur:
            vals.append(cur.val)
            cur = cur.next
        return str(vals)

class List:
    def __init__(self, vals):
        if not vals:
            raise ValueError('Must initialize List with a non-empty array. ')
        cur = self.head = ListNode(vals[0])
        for val in vals[1:]:
            cur.next = ListNode(val)
            cur = cur.next

    def __repr__(self):
        return str(self.head)

print(List([1, 2, 3]).head)
print(List([1, 2, 3]))

[1, 2, 3]
[1, 2, 3]

1. Two Sum

Easy

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

nums = [2, 7, 11, 15]
target = 9

def twoSum(nums, target):
    d = {}
    for idx, n in enumerate(nums):
        if target - n in d:
            return [d[target - n], idx]
        else:
            d[n] = idx

twoSum(nums, target)

[0, 1]

121. Best Time to Buy and Sell Stock

Easy

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

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example:

Input: [7,1,5,3,6,4]
Output: 5

from math import inf

def maxProfit(prices):
    cur_min = inf
    max_profit = 0
    for price in prices:
        cur_min = min(cur_min, price)
        max_profit = max(max_profit, price - cur_min)

    return max_profit


prices = [7, 1, 5, 3, 6, 4]

maxProfit(prices)

5

20. Valid Parentheses

Easy

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if: 1. Open brackets must be closed by the same type of brackets, 2. Open brackets must be closed in the correct order, and 3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

# best solution by AI
# 遇 closing 時 stack 最上層必需是 matching open

def isValid(s):
    stack = []
    match = {')': '(',
             ']': '[',
             '}': '{'}

    for c in s:
        if c in match:
            if not stack or stack[-1] != match[c]:
                return False
            stack.pop()
        else:
            stack.append(c)

    return not stack

isValid('([)]')

False

21. Merge Two Sorted Lists

Easy

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Constraints:

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both l1 and l2 are sorted in non-decreasing order.

# 有可能 l1 l2 都是 empty 所以要用 dummy node

def mergeTwoLists(l1, l2):
    dummy = cur = ListNode()
    while l1 and l2:
        if l1.val < l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next

        cur = cur.next

    if not l1:
        cur.next = l2
    if not l2:
        cur.next = l1

    return dummy.next


lst1 = List([1, 2, 4])
lst2 = List([1, 3, 4])
mergeTwoLists(lst1.head, lst2.head)

[1, 1, 2, 3, 4, 4]

242. Valid Anagram

Easy

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Constraints:

1 <= s.length, t.length <= 5 * 104
s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

from collections import Counter

def isAnagram(s, t):
    return Counter(s) == Counter(t)

s = "anagram"
t = "nagaram"

isAnagram(s, t)

True

226. Invert Binary Tree

Easy

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

Example 1:

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

Constraints:

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

Trivia: This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

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

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

141. Linked List Cycle

Easy

Given head, the head of a linked list, determine if the linked list has a cycle in it.

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. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

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

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?

def hasCycle(head):
    fast = slow = head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast is slow:
            return True

    return False

206. Reverse Linked List

Easy

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

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

Constraints:

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

# Hannah's solution：不改指標而是倒著長一個新的 list
# 實測比改指標用到更多 memory

def reverseList(head):
    res = None
    while head:
        res = ListNode(val=head.val, next=res)
        head = head.next
    return res

lst = List([1, 2, 3, 4, 5])
reverseList(lst.head)

[5, 4, 3, 2, 1]

# 改指標；迴圈裡用 tmp 寫比較直觀 readable
# 雖然也可以用 tuple unpacking 寫成 cur.next, prev, cur = prev, cur, cur.next

def reverseList(head):
    prev = None
    cur = head
    while cur:
        tmp = cur.next
        cur.next = prev
        prev = cur
        cur = tmp

    return prev

lst = List([1, 2, 3, 4, 5])
reverseList(lst.head)

[5, 4, 3, 2, 1]

# recursive solution from the repo
# 遞迴呼叫完成時的狀態是 1 -> 2 <- 3 <- 4 <- 5，head 是 1

def reverseList(head):
    if head is None or head.next is None:
        return head

    reverse = reverseList(head.next)
    head.next.next = head
    head.next = None

    return reverse

lst = List([1, 2, 3, 4, 5])
reverseList(lst.head)

[5, 4, 3, 2, 1]

53. Maximum Subarray

Medium

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

Example 1:

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:

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

Constraints:

1 <= nums.length <= 105
-104 <= nums[i] <= 104

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.

# Kadane's algorithm: Maximum subarray ending $n_i$ is either [n_i], or the maximum subarray ending n_{i-1}, with n_i

def maxSubArray(nums):
    curr_max = global_max = nums[0]
    for n in nums[1:]:
        curr_max = max(n, curr_max + n)
        global_max = max(curr_max, global_max)

    return global_max

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
maxSubArray(nums)

6

238. Product of Array Except Self

Medium

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:

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

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

Constraints:

2 <= nums.length <= 105
-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.)

# 兩次遍歷陣列，分別計算每個位置左側與右側的乘積並將結果相乘

def productExceptSelf(nums):
    n = len(nums)
    res = [1] * n

    # 左側乘積
    left = 1
    for i in range(n):
        res[i] = left
        left *= nums[i]

    # 右側乘積
    right = 1
    for i in range(n - 1, -1, -1):
        res[i] *= right
        right *= nums[i]

    return res

nums = [1, 2, 3, 4]

productExceptSelf(nums)

[24, 12, 8, 6]

102. Binary Tree Level Order Traversal

Medium

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Constraints:

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

# BFS

from collections import deque

def levelOrder(root):
    q = deque()
    if root:
        q.append(root)

    res = []
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

        res.append(level)
    return res

151. Reverse Words in a String

Medium

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"
Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.


Constraints:

1 <= s.length <= 104
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.


Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

import re

def reverseWords(s):
    return ' '.join(re.sub(r'\s{2,}', ' ', s).strip().split(' ')[::-1])

s = "the sky is blue"
reverseWords(s)

'blue is sky the'

# python string split 如果不 specify sep，就會自己抓連續空白字元當作 separator，不需要 re.sub

def reverseWords(s):
    return ' '.join(s.strip().split()[::-1])

s = "the sky is blue"
reverseWords(s)

'blue is sky the'

139. Word Break

Medium

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:

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:

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.

# memoized version by AI, accepted on leetcode

def wordBreak(s, wordDict, memo=None):
    if memo is None:
        memo = {}

    if s in memo:
        return memo[s]

    if not s:
        return True

    for word in wordDict:
        if s.startswith(word):
            if wordBreak(s[len(word):], wordDict, memo):
                memo[s] = True
                return True

    memo[s] = False
    return False

s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
wordBreak(s, wordDict)

False

198. House Robber

Medium

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

def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]

    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[-1]


nums = [2, 7, 9, 3, 1]

rob(nums)

12

200. Number of Islands

Medium

Given an m x n 2d grid 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","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'.

# 遇到 1 就 dfs 把週圍都塗成 0 然後 counter 加 1
# 很容易忘記 grid 裡是 char 而不是 int 然後寫成 if grid[i][j] == 1

def numIslands(grid):
    def dfs(grid, i, j):
        if grid[i][j] == '0':
            return
        else:
            grid[i][j] = '0'

            if i+1 <= len(grid)-1:
                dfs(grid, i+1, j)
            if i-1 >= 0:
                dfs(grid, i-1, j)
            if j+1 <= len(grid[0])-1:
                dfs(grid, i, j+1)
            if j-1 >= 0:
                dfs(grid, i, j-1)

    counter = 0

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                counter += 1
                dfs(grid, i, j)

    return counter


grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

numIslands(grid)

1

221. Maximal Square

Medium

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:

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:

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

Example 3:

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


Constraints:

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

def maximalSquare(matrix):
    m = len(matrix)
    n = len(matrix[0])

    max_len = 0
    dp = [[0 for j in range(n)] for i in range(m)]

    for i in range(m):
        for j in range(n):
            if i==0 or j==0:
                dp[i][j] = int(matrix[i][j])
                max_len = max(dp[i][j], max_len)
            else:
                if matrix[i][j] == '0':
                    dp[i][j] = 0
                else:
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                    max_len = max(dp[i][j], max_len)

    return max_len**2


matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"]]

maximalSquare(matrix)

4

322. Coin Change

Medium

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:

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

Example 2:

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

Example 3:

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


Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

# my logic but polished by AI

from functools import cache

def coinChange(coins, amount):
    @cache
    def dp(remain):
        if remain == 0:
            return 0
        if remain < 0:
            return float('inf')

        return min(dp(remain - coin) + 1 for coin in coins)

    res = dp(amount)
    return res if res != float('inf') else -1


coins = [1, 2, 5]
amount = 11

coinChange(coins, amount)

3