Table of Contents
Merge Sorted ArrayProblem Description:Solution:AnalysisClimbing StairsProblem Description:Solution1:AnalysisSolution2:AnalysisHouse RobberProblem Description:Idea:Solution—my ver.:AnalysisSolution—official1:Solution—official2:Word BreakProblem Description:Solution—Top-Down DP:Solution—Bottom-Up DP:Valid PalindromeProblem Description:Solution—2 pointers:Container with most waterProblem Description:Solution—2 pointers:Ransom NoteProblem Description:Solution—defaultdict:Two SumTwo Sum 2 (sorted)3 Sumsort +1 outer for-loop + two pointerHast set + sortingHash Set no sorting3 Sum closest4 SumLargest Rectangle in HistogramMaximal RectangleNumber of IslandsTarget SumProblem DescriptionSolution: dp top downSolution: dp bottom upSolution: freq. mapLargest Divisible SubsetProblem DescriptionSolution — DPPath With Maximum ProbabilityProblem DescriptionDijkstra (min-heap) + log(x)Majority ElementProblem DescriptionSolution — Boyer-Moore Voting Algorithm
Merge Sorted Array
Problem Description:
You are given two integer arrays
nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.Merge
nums1 and nums2 into a single array sorted in non-decreasing order.The final sorted array should not be returned by the function, but instead be stored inside the array
nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.Solution:
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ # Set p1 and p2 to point to the end of their respective arrays. p1 = m - 1 p2 = n - 1 # And move p backward through the array, each time writing # the largest value pointed at by p1 or p2. for p in range(n + m - 1, -1, -1): if p2 < 0: break if p1 >= 0 and nums1[p1] > nums2[p2]: nums1[p] = nums1[p1] p1 -= 1 else: nums1[p] = nums2[p2] p2 -= 1
Analysis
- time complexity: O(m+n)
- space complexity: O(1)
- Algo category: 3 pointers
Climbing Stairs
Problem Description:
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?Solution1:
class Solution: def climbStairs(self, n: int) -> int: # fib x, y = 1,2 if n == 1: return 1 elif n==2: return 2 for i in range(n-2): tmp_y = y y = x + y x = tmp_y return y
Analysis
- time complexity: O(n)
- space complexity: O(1)
- Algo category: Fib fast
Solution2:
class Solution: def climbStairs(self, n: int) -> int: q = [[1, 1], [1, 0]] res = self.pow(q, n) return res[0][0] def pow(self, a: [[int]], n: int) -> [[int]]: ret = [[1, 0], [0, 1]] while n > 0: if (n & 1) == 1: ret = self.multiply(ret, a) n >>= 1 a = self.multiply(a, a) return ret def multiply(self, a: [[int]], b: [[int]]) -> [[int]]: c = [[0, 0], [0, 0]] for i in range(2): for j in range(2): c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] return c
Analysis
- time complexity: O(log(n))
- space complexity: O(1)
- Algo category: Binets Method, Use Matrix
House Robber
Problem Description:
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.Idea:
it’s a DP question. Transition Function:
Solution—my ver.:
class Solution: def rob(self, nums: List[int]) -> int: memo = nums if len(nums) == 1: return nums[0] elif len(nums) == 2: return max(nums[0], nums[1]) memo[1] = max(nums[0], nums[1]) for i in range(2, len(nums)): memo[i] = max(memo[i-1], memo[i-2]+nums[i]) return memo[-1]
Analysis
- time complexity: O(n)
- space complexity: O(n)
- Algo category: DP, memoization
Solution—official1:
class Solution: def rob(self, nums: List[int]) -> int: # Special handling for empty case. if not nums: return 0 maxRobbedAmount = [None for _ in range(len(nums) + 1)] N = len(nums) # Base case initialization. maxRobbedAmount[N], maxRobbedAmount[N - 1] = 0, nums[N - 1] # DP table calculations. for i in range(N - 2, -1, -1): # Same as recursive solution. maxRobbedAmount[i] = max( maxRobbedAmount[i + 1], maxRobbedAmount[i + 2] + nums[i] ) return maxRobbedAmount[0]
Same as my code, just more elegant with addition 0 at the end.
Solution—official2:
class Solution: def rob(self, nums: List[int]) -> int: # Special handling for empty case. if not nums: return 0 N = len(nums) rob_next_plus_one = 0 rob_next = nums[N - 1] # DP table calculations. for i in range(N - 2, -1, -1): # Same as recursive solution. current = max(rob_next, rob_next_plus_one + nums[i]) # Update the variables rob_next_plus_one = rob_next rob_next = current return rob_next
Simplify Space complexity to O(1). Only need to keep track of 2 previous values.
Word Break
Problem Description:
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.
Solution—Top-Down DP:
class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: @cache def dp(i): if i < 0: return True for word in wordDict: if s[i - len(word) + 1 : i + 1] == word and dp(i - len(word)): return True return False return dp(len(s) - 1)
Solution—Bottom-Up DP:
class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: dp = [False] * len(s) for i in range(len(s)): for word in wordDict: # Handle out of bounds case if i < len(word) - 1: continue if i == len(word) - 1 or dp[i - len(word)]: if s[i - len(word) + 1 : i + 1] == word: dp[i] = True break return dp[-1]
Valid Palindrome
Problem Description:
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string
s, return true if it is a palindrome, or false otherwise.Solution—2 pointers:
class Solution: def isPalindrome(self, s: str) -> bool: s = s.lower() print(s) a, b = 0, len(s)-1 while a < b: while a < b and not s[a].isalnum(): a += 1 while a < b and not s[b].isalnum(): b -= 1 if s[a] != s[b]: return False a += 1 b -= 1 return True
Container with most water
Problem Description:
You are given an integer array
height of length n. There are n vertical lines drawn such that the two endpoints of the ith 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.
Solution—2 pointers:
class Solution: def maxArea(self, height: List[int]) -> int: maxarea = 0 left = 0 right = len(height) - 1 while left < right: width = right - left maxarea = max(maxarea, min(height[left], height[right]) * width) if height[left] <= height[right]: left += 1 else: right -= 1 return maxarea
Idea: just always move the shorter one closer.
Ransom Note
Problem Description:
Given two strings
ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and falseotherwise.Each letter in
magazine can only be used once in ransomNote.Solution—defaultdict:
class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: from collections import defaultdict maga = defaultdict(int) for x in magazine: maga[x] += 1 for x in ransomNote: maga[x] -= 1 for x in maga: if maga[x] < 0: return False return True
Two Sum
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hashmap = {} for i in range(len(nums)): complement = target - nums[i] if complement in hashmap: return [i, hashmap[complement]] hashmap[nums[i]] = i # Return an empty list if no solution is found return []
Use a hash table. O(n) time, O(n) space.
Two Sum 2 (sorted)
class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: low = 0 high = len(numbers) - 1 while low < high: sum = numbers[low] + numbers[high] if sum == target: return [low + 1, high + 1] elif sum < target: low += 1 else: high -= 1 # In case there is no solution, return [-1, -1]. return [-1, -1]
Use two pointers. Left and right. O(n) time, O(1) space.
3 Sum
sort +1 outer for-loop + two pointer
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: res = [] nums.sort() for i in range(len(nums)): if nums[i] > 0: break if i == 0 or nums[i - 1] != nums[i]: self.twoSumII(nums, i, res) return res def twoSumII(self, nums: List[int], i: int, res: List[List[int]]): lo, hi = i + 1, len(nums) - 1 while lo < hi: sum = nums[i] + nums[lo] + nums[hi] if sum < 0: lo += 1 elif sum > 0: hi -= 1 else: res.append([nums[i], nums[lo], nums[hi]]) lo += 1 hi -= 1 while lo < hi and nums[lo] == nums[lo - 1]: lo += 1
time O(n^2), space O(n)
Hast set + sorting
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: res = [] nums.sort() for i in range(len(nums)): if nums[i] > 0: break if i == 0 or nums[i - 1] != nums[i]: self.twoSum(nums, i, res) return res def twoSum(self, nums: List[int], i: int, res: List[List[int]]): seen = set() j = i + 1 while j < len(nums): complement = -nums[i] - nums[j] if complement in seen: res.append([nums[i], nums[j], complement]) while j + 1 < len(nums) and nums[j] == nums[j + 1]: j += 1 seen.add(nums[j]) j += 1
O(n^2), O(n)
Hash Set no sorting
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: res, dups = set(), set() seen = {} for i, val1 in enumerate(nums): if val1 not in dups: dups.add(val1) for j, val2 in enumerate(nums[i + 1 :]): complement = -val1 - val2 if complement in seen and seen[complement] == i: res.add(tuple(sorted((val1, val2, complement)))) seen[val2] = i return [list(x) for x in res]
O(n^2), O(n)
3 Sum closest
class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: diff = float("inf") nums.sort() for i in range(len(nums)): lo, hi = i + 1, len(nums) - 1 while lo < hi: sum = nums[i] + nums[lo] + nums[hi] if abs(target - sum) < abs(diff): diff = target - sum if sum < target: lo += 1 else: hi -= 1 if diff == 0: break return target - diff
O(n^2), O(n)
4 Sum
class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: def kSum(nums: List[int], target: int, k: int) -> List[List[int]]: res = [] # If we have run out of numbers to add, return res. if not nums: return res # We cannot obtain a sum of target if the smallest value # in nums is greater than target // k or if the largest # value in nums is smaller than target // k. average_value = target // k if average_value < nums[0] or nums[-1] < average_value: return res if k == 2: return twoSum(nums, target) for i in range(len(nums)): if i == 0 or nums[i - 1] != nums[i]: for subset in kSum(nums[i + 1 :], target - nums[i], k - 1): res.append([nums[i]] + subset) return res def twoSum(nums: List[int], target: int) -> List[List[int]]: res = [] lo, hi = 0, len(nums) - 1 while lo < hi: curr_sum = nums[lo] + nums[hi] if curr_sum < target or (lo > 0 and nums[lo] == nums[lo - 1]): lo += 1 elif curr_sum > target or ( hi < len(nums) - 1 and nums[hi] == nums[hi + 1] ): hi -= 1 else: res.append([nums[lo], nums[hi]]) lo += 1 hi -= 1 return res nums.sort() return kSum(nums, target, 4)
Largest Rectangle in Histogram
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.
class Solution: def largestRectangleArea(self, heights: List[int]) -> int: stack = [-1] max_area = 0 for i in range(len(heights)): while stack[-1] != -1 and heights[stack[-1]] >= heights[i]: current_height = heights[stack.pop()] current_width = i - stack[-1] - 1 max_area = max(max_area, current_height * current_width) stack.append(i) while stack[-1] != -1: current_height = heights[stack.pop()] current_width = len(heights) - stack[-1] - 1 max_area = max(max_area, current_height * current_width) return max_area
First thing to note is that there are N rectangles that need to be considered. This isn't immediately obvious, it helps to draw them out on a piece of paper. But once you see that there are N rectangles, the problem simply boils down to iterating through each one, which of course is linear.
How do we iterate through N rectangles? The obvious approach would be to scan left-to-right and have the index represent the right side of the rectangle. To derive the left side / height, we need a data structure to keep track of columns we've already seen. A stack is usually the choice for these increasing / decreasing columns type of problems.
So we know we're gonna scan left-to-right and keep putting something or other on the stack. Now to work out the specifics.
The column heights in the example are [6, 7, 5, ...]. What happens when we get to 5? The thing to note is that from perspective of any columns to the right of it, 6 and 7 don't matter. The height will be 5 or smaller. So come 5, that's the only thing that should be on the stack.
What about 6 and 7? It looks like we'll need both on the stack, cause we'll need to consider rectangles of heights 6 and 7. We don't know how far to the right those rectangles will extend, so we'll just put (column, height) onto the stack. Once we see 5, that's the right-hand border for these rectangles and that's when we can consider them.
So the algorithm boils down to:
- Maintain a stack such that heights are always in increasing order.
- When we see a column that's lower than what's on the stack
- Use it as the right side and compute all the possible rectangles using what's on the stack to derive left side and height.
- Remove each considered rectangle / column from the stack
Maximal Rectangle
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:
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.
class Solution: # Get the maximum area in a histogram given its heights def leetcode84(self, heights): stack = [-1] maxarea = 0 for i in range(len(heights)): while stack[-1] != -1 and heights[stack[-1]] >= heights[i]: maxarea = max( maxarea, heights[stack.pop()] * (i - stack[-1] - 1) ) stack.append(i) while stack[-1] != -1: maxarea = max( maxarea, heights[stack.pop()] * (len(heights) - stack[-1] - 1) ) return maxarea def maximalRectangle(self, matrix: List[List[str]]) -> int: if not matrix: return 0 maxarea = 0 dp = [0] * len(matrix[0]) for i in range(len(matrix)): for j in range(len(matrix[0])): # update the state of this row's histogram using the last row's histogram # by keeping track of the number of consecutive ones dp[j] = dp[j] + 1 if matrix[i][j] == "1" else 0 # update maxarea with the maximum area from this row's histogram maxarea = max(maxarea, self.leetcode84(dp)) return maxarea
Here just use the solution of the last problem.
Number of Islands
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.
class Solution: def numIslands(self, grid): if not grid: return 0 num_islands = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == "1": self.dfs(grid, i, j) num_islands += 1 return num_islands def dfs(self, grid, r, c): if ( r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] != "1" ): return grid[r][c] = "0" self.dfs(grid, r - 1, c) self.dfs(grid, r + 1, c) self.dfs(grid, r, c - 1) self.dfs(grid, r, c + 1)
O(m*n), O(m*n)
Target Sum
Problem Description
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'+'before2and a'-'before1and concatenate them to build the expression"+2-1".
Return the number of different expressions that you can build, which evaluates to
target.Solution: dp top down
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: @lru_cache(maxsize=None) def check(idx, target): if idx == 0: return int(target == nums[0]) + int(target == -nums[0]) value = nums[idx] return check(idx-1, target - value)+check(idx-1, target + value) return check(len(nums)-1, target)
Solution: dp bottom up
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: total_sum = sum(nums) dp = [[0] * (2 * total_sum + 1) for _ in range(len(nums))] # Initialize the first row of the DP table dp[0][nums[0] + total_sum] = 1 dp[0][-nums[0] + total_sum] += 1 # Fill the DP table for index in range(1, len(nums)): for sum_val in range(-total_sum, total_sum + 1): if dp[index - 1][sum_val + total_sum] > 0: dp[index][sum_val + nums[index] + total_sum] += dp[ index - 1 ][sum_val + total_sum] dp[index][sum_val - nums[index] + total_sum] += dp[ index - 1 ][sum_val + total_sum] # Return the result if the target is within the valid range return ( 0 if abs(target) > total_sum else dp[len(nums) - 1][target + total_sum] )
Solution: freq. map
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: d = defaultdict(int) d[0] = 1 for num in nums: dp = defaultdict(int) for k, v in d.items(): dp[k + num] += v dp[k - num] += v d = dp return d[target]
Largest Divisible Subset
Problem Description
Given a set of distinct positive integers
nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:answer[i] % answer[j] == 0, or
answer[j] % answer[i] == 0
If there are multiple solutions, return any of them.
也就是，先sort，然后找最长的整除链。
Solution — DP
def largestDivisibleSubset(nums): if not nums: return [] nums.sort() n = len(nums) dp = [1] * n # 每个数至少能形成一个长度为1的链 prev = [-1] * n # 记录前驱索引 max_len = 1 max_index = 0 for i in range(n): for j in range(i): if nums[i] % nums[j] == 0: if dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 prev[i] = j if dp[i] > max_len: max_len = dp[i] max_index = i # 回溯构造结果 res = [] while max_index != -1: res.append(nums[max_index]) max_index = prev[max_index] return res[::-1]
关键点是有一个前驱。
Path With Maximum Probability
Problem Description
You are given an undirected weighted graph of
n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].Given two nodes
start and end, find the path with the maximum probability of success to go from start to end and return its success probability.If there is no path from
start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.Dijkstra (min-heap) + log(x)
import math import heapq from collections import defaultdict class Solution: def maxProbability(self, n, edges, succProb, start, end): graph = defaultdict(list) for (a, b), p in zip(edges, succProb): if p > 0: w = -math.log(p) graph[a].append((b, w)) graph[b].append((a, w)) dist = [float('inf')] * n dist[start] = 0.0 heap = [(0.0, start)] while heap: cur_cost, node = heapq.heappop(heap) if node == end: return math.exp(-cur_cost) if cur_cost > dist[node]: continue for nei, w in graph[node]: new_cost = cur_cost + w if new_cost < dist[nei]: dist[nei] = new_cost heapq.heappush(heap, (new_cost, nei)) return 0.0
Majority Element
Problem Description
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.Solution — Boyer-Moore Voting Algorithm
class Solution: def majorityElement(self, nums): count = 0 candidate = None for num in nums: if count == 0: candidate = num count += 1 if num == candidate else -1 return candidate