Home

55. Jump Game Solution Always check if we can arrive at the next position,i.e. curr >= idx. Keep the furthest position we can approach. If we can always approach the next position and the furthest approachable is further than the last position, then can jump. def canJump(self, nums): """ :type nums: List[int] :rtype: bool """ ...

62. Unique Paths Solution 1 For each box, there are two possible directions to approach it (from left or from top). Sum the two approaches together for the final result. Space Complexity: O(m * n) Solution 2 For each box, there are two possible directions to approach it (from left or from top). We store the number of unique paths...

91. Decode Ways Solution The decode ways depend on how many ways the previous substring can be decoded. The numbers are from 1 to 26, it is possible that one digit can be in two kind of combination. We can keep track of pre_one and pre_two. Note: When the digit is 0, its pre_one need to be erased, because it cannot be decoded a...

198. House Robber 213. House Robber II Solution If we rob the curr house, we cannot rob curr-1 house. Keep max_2_house_before as the amount we can get if we do NOT rob curr-1, i.e. we can rob curr. Keep adjacent as the amount we can get if we rob curr-1, i.e. we cannot rob curr. Althouge we can rob curr, we do NOT necessarily rob it. We c...

377. Combination Sum IV Solution - Memoization def combinationSum4(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ if target == 0: return 1 if target < 0: return 0 res = 0 for num in nums: if target - num in self.dict: res += self.di...

300. Longest Increasing Subsequence Solution 1 - Recursion with Memoization Remove redudancy by store information in memo. memo: memo[i][j] represents the length of the LIS possible using nums[i] as the previous element considered to be included/not included in the LIS, with nums[j] as the current element considered to be include...

322. Coin Change Solution 1 - DP Solution 2 - Optimal DFS Sort the coins in decreasing order, so that we always check larger coins first. Keep current minimum number of coins needed. Check if it is possible to change the amount within the remaining allowance, i.e. number of coins. If it is impossible, early terminate. def coinChange(...

70. Climbing Stairs Solution Keep the number of distinct ways to climb n stairs. dict[n] = dict[n-1] + dict[n-2] Similar to induction, base case: n = 1 and n = 2