Dynamic Programming
Climbing Stairs (Easy)
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?
def climbStairs(n: int) -> int: if n <= 1: return 1 # memo[i] = (memo[i - 1] solutions plus 1 step) + (memo[i - 2] solutions plus 2 steps) memo = [0] * (n + 1) memo[1] = 1 memo[2] = 2 for i in range(3, n + 1): memo[i] = memo[i - 1] + memo[i - 2] return memo[n]
Time: O(n)
Space: O(n)
Alternative solution:
def climbStairs(n: int) -> int: if n < 3: return n # Don't need list because don't need to save old calculations prev = 1 curr = 2 for _ in range(3, n + 1): # Same as using temp variable curr += prev prev = curr - prev return curr
Time: O(n)
Space: O(1)
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.
def rob(nums: List[int]) -> int: # Track max stolen value up to previous two houses oneBack = twoBack = 0 for num in nums: # Two choices for current index: # Ignore current house, keep oneBack value -OR- # Steal from current house, add to twoBack curr = max(num + twoBack, oneBack) twoBack = oneBack oneBack = curr return curr
Time: O(n)
Space: O(1)
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.
def wordBreak(s: str, wordDict: List[str]) -> bool: wordDict = set(wordDict) memo = [False] * (len(s) + 1) memo[0] = True # Base case: empty string for i in range(1, len(s) + 1): # Nested loop to check current substring for prevChar in range(i): # s[i] corresponds with memo[i + 1] if memo[prevChar] and s[prevChar:i] in wordDict: memo[i] = True break return memo[-1]
Time: O(n3), n = len(s)
Space: O(n + m), m = wordDict size
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.
def coinChange(coins: List[int], amount: int) -> int: memo = [float("inf")] * (amount + 1) memo[0] = 0 for amnt in range(1, amount + 1): # Coin values are index differences for coin in coins: # Boundary check if amnt - coin >= 0: memo[amnt] = min(memo[amnt], memo[amnt - coin] + 1) return memo[-1] if memo[-1] != float("inf") else -1
Time: O(n * m), n = len(coins), m = amount
Space: O(m)
Longest Increasing Subsequence (Medium)
Given an integer array nums, return the length of the longest strictly increasing subsequence.
def lengthOfLIS(nums: List[int]) -> int: memo = [1] * (len(nums)) for i in range(1, len(nums)): for j in range(i): if nums[j] < nums[i]: memo[i] = max(memo[i], memo[j] + 1) return max(memo)
Time: O(n2)
Space: O(n)
Alternative solution:
def lengthOfLIS(nums: List[int]) -> int: # Build longest subsequence sub = [] for num in nums: # Current num can be added to subsequence if not sub or num > sub[-1]: sub.append(num) else: # Native function: bisect_left(sorted_list, val) # Binary search to find leftmost index for inserting val # Replace an element in subsequence instead of appending sub[bisect_left(sub, num)] = num # sub may no longer hold a valid subsequence. Does not matter because # length is preserved and appending only requires checking last element return len(sub)
Time: O(n * log n)
Space: O(n)
Triangle (Medium)
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
# Example: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] # 2 # 3 4 # 6 5 7 # 4 1 8 3 # Output = 11
def minimumTotal(triangle: List[List[int]]) -> int: # Bottom-up DP, modify triangle in-place instead of memoizing # Find path starting from bottom row up to root # Starting from root is also possible, but must handle boundaries for row in range(len(triangle) - 1, 0, -1): # Current row index is used to loop through upper row # Each element in upper row can choose from two elements in current row for col in range(row): triangle[row - 1][col] += min(triangle[row][col], triangle[row][col + 1]) return triangle[0][0]
Time: O(n2)
Space: O(1)
Follow-up: Solve using O(n) space, n = len(triangle)
def minimumTotal(triangle: List[List[int]]) -> int: # Bottom-up DP, storing path sums in 1D array # Can also just modify triangle in-place memo = triangle[-1][:] for row in range(len(triangle) - 2, -1, -1): for col in range(len(triangle[row])): memo[col] = triangle[row][col] + min(memo[col], memo[col + 1]) # The last element in memo is discarded as rows move up # This pop is unnecessary, but illustrates how memo is used memo.pop() return memo[0]
Time: O(n2)
Space: O(n)
Minimum Path Sum (Medium)
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.
You can only move either down or right at any point in time.
def minPathSum(grid: List[List[int]]) -> int: # First row and column only have one possible path for col in range(1, len(grid[0])): grid[0][col] += grid[0][col - 1] for row in range(1, len(grid)): grid[row][0] += grid[row - 1][0] for row in range(1, len(grid)): for col in range(1, len(grid[0])): # Current square can only be reached from left or top grid[row][col] += min(grid[row - 1][col], grid[row][col - 1]) return grid[-1][-1]
Time: O(m * n)
Space: O(1)
Unique Paths II (Medium)
You are given an m x n integer array grid. There is a robot 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.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
def uniquePathsWithObstacles(obstacleGrid: List[List[int]]) -> int: # Can also use 1D array starting with first row, or modify in-place memo = [[0] * len(obstacleGrid[0]) for _ in obstacleGrid] memo[0][0] = 1 if obstacleGrid[0][0] == 0 else 0 for row in range(len(obstacleGrid)): for col in range(len(obstacleGrid[0])): if obstacleGrid[row][col] == 1: continue # Check left and top squares. Obstacles are marked as 0 in memo memo[row][col] += memo[row][col - 1] if col - 1 >= 0 else 0 memo[row][col] += memo[row - 1][col] if row - 1 >= 0 else 0 return memo[-1][-1]
Time: O(m * n)
Space: O(m * n)
Longest Palindromic Substring (Medium)
Given a string s, return the longest palindromic substring in s.
def longestPalindrome(s: str) -> str: # 2D array representing substring window indices # memo[left][right] = True --> s[left:right + 1] is palindrome memo = [[False for _ in s] for _ in s] answerStart = answerEnd = 0 for right in range(len(s)): # Single char is always palindrome memo[right][right] = True for left in range(right): # If outer chars are equal: # (right - left <= 2) string of 3 or less chars is always palindrome # OR check if substring without outer chars is palindrome if s[left] == s[right] and (right - left <= 2 or memo[left + 1][right - 1]): memo[left][right] = True if right - left > answerEnd - answerStart: answerStart, answerEnd = left, right return s[answerStart:answerEnd + 1]
Time: O(n2)
Space: O(n2)
Alternative solution:
def longestPalindrome(s: str) -> str: def expand(left, right): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return left + 1, right - 1 answerStart = answerEnd = 0 # Find largest palindrome using every char as center for i in range(len(s)): # single char center oddL, oddR = expand(i, i) if answerEnd - answerStart < oddR - oddL: answerStart, answerEnd = oddL, oddR # two char center evenL, evenR = expand(i, i + 1) if answerEnd - answerStart < evenR - evenL: answerStart, answerEnd = evenL, evenR return s[answerStart: answerEnd + 1]
Time: O(n2)
Space: O(1)
Interleaving String (Medium)
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- The interleaving is
s1 + t1 + s2 + t2 + s3 + t3 + ...ort1 + s1 + t2 + s2 + t3 + s3 + ...
def isInterleave(s1: str, s2: str, s3: str) -> bool: if len(s1) + len(s2) != len(s3): return False # 2D array of indices for s1 and s2, including empty string # memo[i][j] = True --> s1[:i] and s2[:j] make s3[:i+j] memo = [[False for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)] memo[0][0] = True # Fill first row (when s1 is empty) and first column (when s2 is empty) for col in range(1, len(memo[0])): prev = col - 1 memo[0][col] = memo[0][prev] and s2[prev] == s3[prev] for row in range(1, len(memo)): prev = row - 1 memo[row][0] = memo[prev][0] and s1[prev] == s3[prev] # Inner grid. row for s1, col for s2 # Incrementally add chars from s1/s2 to previously solved substrings for row in range(1, len(memo)): for col in range(1, len(memo[0])): # New char must be equal to cumulative index in s3 memo[row][col] = ( (memo[row - 1][col] and s1[row - 1] == s3[row + col - 1]) or (memo[row][col - 1] and s2[col - 1] == s3[row + col - 1]) ) return memo[-1][-1]
Time: O(m * n), m = len(s1), n = len(s2)
Space: O(m * n)
Alternative solution:
def isInterleave(s1: str, s2: str, s3: str) -> bool: if len(s1) + len(s2) != len(s3): return False # Same solution as previous, but using 1D array # because only previous row in 2D array is needed memo = [False] * (len(s1) + 1) memo[0] = True for i in range(1, len(memo)): memo[i] = memo[i - 1] and s1[i - 1] == s3[i - 1] for i in range(1, len(s2) + 1): memo[0] = memo[0] and s2[i - 1] == s3[i - 1] for j in range(1, len(memo)): memo[j] = ( (memo[j] and s2[i - 1] == s3[i + j - 1]) or (memo[j - 1] and s1[j - 1] == s3[i + j - 1]) ) return memo[-1]
Time: O(m * n), m = len(s1), n = len(s2)
Space: O(m)
Edit Distance (Medium)
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:
Input: word1 = "horse", word2 = "ros"
Output: 3
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
def minDistance(word1: str, word2: str) -> int: # memo[i][j] --> minimum operations for word1[:i] to word2[:j] # memo can be collapsed into 1D array and temp variable memo = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)] # Handle first row (word1 always empty string) for col in range(1, len(memo[0])): memo[0][col] = col for row in range(1, len(memo)): # Handle first column (word2 always empty string) memo[row][0] = row # row for word1, col for word2 for col in range(1, len(memo[0])): # If matching char, no operation needed if word1[row - 1] == word2[col - 1]: memo[row][col] = memo[row - 1][col - 1] else: # Top: Delete # Left: Insert # Top-left: Replace memo[row][col] = 1 + min( memo[row - 1][col], memo[row][col - 1], memo[row - 1][col - 1] ) return memo[-1][-1]
Time: O(m * n), m = len(word1), n = len(word2)
Space: O(m * n)
Alternative solution:
def minDistance(word1: str, word2: str) -> int: # Top-down recursive DP, starting with full strings # memo holds word1 and word2 indices { tuple(int, int): int } # Value: (i1, i2) --> word1[i1:], word2[i2:] # Key: minimum operations for current substrings memo = {} def helper(i1, i2): if (i1, i2) in memo: return memo[(i1, i2)] # If other word is equal/more chars left, must insert remainder if i1 == len(word1): return len(word2) - i2 if i2 == len(word2): return len(word1) - i1 if word1[i1] == word2[i2]: memo[(i1, i2)] = helper(i1 + 1, i2 + 1) else: memo[(i1, i2)] = 1 + min( helper(i1, i2 + 1), # Insert helper(i1 + 1, i2), # Delete helper(i1 + 1, i2 + 1) # Replace ) return memo[(i1, i2)] # Answer is stored in memo[(0, 0)] return helper(0, 0)
Time: O(m * n), m = len(word1), n = len(word2)
Space: O(m * n)
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.
def maximalSquare(matrix: List[List[str]]) -> int: # Bottom-up DP, starting with base case of 1x1 square # memo[i][j] contains length of largest valid square, # where memo[i][j] is bottom right corner of square # memo contains extra row and column padding to handle boundaries # memo can be collapsed into 1D array and temp variable memo = [[0 for _ in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)] answer = 0 for row in range(1, len(memo)): for col in range(1, len(memo[0])): if matrix[row - 1][col - 1] == "1": # Check top, left, and top-left squares memo[row][col] = 1 + min( memo[row - 1][col], memo[row][col - 1], memo[row - 1][col - 1] ) answer = max(answer, memo[row][col]) return answer * answer # area of square
Time: O(m * n)
Space: O(m * n)