result = []def backtrack(path, choices): if satisfies end condition: result.add(path) return for choice in choices: make the choice backtrack(path, choices) withdraw the choice
"""Permutations using backtrack"""def permute(nums: list[int]) -> list[list[int]]: ans = [] track = [] used = [False] * len(nums) def backtrack(nums, track, used): if len(track) == len(nums): ans.append(track.copy()) for i, num in enumerate(nums): if used[i]: continue track.append(num) used[i] = True backtrack(nums, track, used) track.pop() used[i] = False backtrack(nums, track, used) return ans
Caution
Since lists are mutable in Python, when we append a track to result list,
avoid appending a reference to the same list track by enforcing a deepcopy with track[:] or track.copy().
Otherwise, when track is modified in subsequent iterations, it also changes the list in ans.
Generate Parentheses
Some pruning conditions:
left and right represent the number of parentheses that can still be used.
If at some point left is greater than right, it means there are more ) than ( in the track, which is invalid.
If at any point left or right is less than 0, it means we have used more parentheses than allowed, which is invalid.
Solution:
def generateParenthesis(n: int) -> list[str]: def backtrack(track: str, left: int, right: int): if left == 0 and right == 0: ans.append(track[:]) if left > right: return if left < 0 or right < 0: return track += "(" backtrack(track, left-1, right) track = track[:-1] track += ")" backtrack(track, left, right-1) track = track[:-1] ans = [] backtrack("", n, n) return ans
class Solution: def numsSameConsecDiff(self, n: int, k: int) -> List[int]: ans = [] def backtrack(track: int, num_digit: int): if num_digit == n: ans.append(track) return for i in range(10): if track == 0 and i == 0: continue if track > 0 and abs((track % 10) - i) != k: continue track = track * 10 + i num_digit += 1 backtrack(track, num_digit) track = (track - track % 10) // 10 num_digit -= 1 backtrack(0, 0) return ans
Binary Search
Search For A Single Number
Search with closed interval on both ends[left, right].
class Solution: def binary_search(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 return -1
Tip
Note that left + right might overflow. Use left + (right - left) // 2 instead.
class Solution: def binary_search(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left < right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 return left if nums[left] == target else -1
Search For A Range
Search for the left bound of the target:
class Solution: def search_left_bound(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 elif nums[mid] == target: right = mid - 1 if left >= len(nums) or nums[left] != target: return -1 return left
Search for the right bound of the target:
class Solution: def search_right_bound(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 elif nums[mid] == target: left = mid + 1 if right < 0 or nums[right] != target: return -1 return right
Binary Tree Traversal
The binary tree node is defined as follows:
class TreeNode: def __init__(self, x: int): self.val = x self.left = None self.right = None
Inorder Traversal
In inorder traversal, the parent node is in between its left and right child nodes.
The idea is to first traverse to the leftmost node and then process the node itself,
followed by processing its right child node.
def inorder(root): ans = [] stack = [] cur = root while stack or cur: # iterate through the tree until reaching the leftmost node while cur: stack.append(cur) cur = cur.left cur = stack.pop() ans.append(cur.val) cur = cur.right return ans
Preorder Traversal
In preorder traversal, the parent node is processed first followed by its left and right child nodes.
node→left→right
We can implement it using a stack. As we iterate through the tree, first process the node itself,
then append its child nodes to the stack. Note that in order to ensure the left child node is processed first,
we need to append the right child node first.
def preorder(root): ans = [] if root is None: return ans stack = [root] while stack: cur = stack.pop() ans.append(cur.val) # append right child first so that left child is processed first if cur.right: stack.append(cur.right) if cur.left: stack.append(cur.left) return ans
Postorder Traversal
Postorder traversal can be implemented in a similar fashion as preorder traversal.
Notice that in preorder traversal, we process the node itself followed by its left and right child nodes.
node→left→right
In postorder traversal, we process its left and right child nodes first, followed by the node itself.
left→right→node
Therefore we can reuse the implementation of preorder traversal,
and the only difference is that we need to reverse the order when recording values.
One way to do so is, instead of appending the node value at the end of the result list,
we insert it at the beginning.
def postorder(root): if not root: return [] stack = [root] result = [] while stack: node = stack.pop() result.insert(0, node.val) # reverse the process of preorder # append left child first so that right child is processed first if node.left: stack.append(node.left) if node.right: stack.append(node.right) return result
Or process the values first and then reverse the result list at the end.
def postorder(root): if not root: return [] stack = [root] result = [] while stack: node = stack.pop()- result.insert(0, node.val) # reverse the process of preorder+ result.append(node.val) # append left child first so that right child is processed first if node.left: stack.append(node.left) if node.right: stack.append(node.right)- return result+ return result[::-1]
Approach: *There are two cases for the center of a palindrome:
The palindrome has odd length, i.e., the center is a single character.
The palindrome has even length, i.e., the center is two identical characters.
For each character in the string, we treat it as the center and expand outwards on both sides
to find the longest palindrome centered at it and update the answer.*
Example:
Input: s = “babad” Output: “bab” Explanation: “aba” is also a valid answer.
Solution:
class Solution: def longestPalindrome(self, s: str) -> str: ans = "" for i in range(len(s)): # odd length case cur = self.findPalindrome(s, i, i) if len(cur) > len(ans): ans = cur # even length case # if s[i] and s[i+1] are not identical, it will return "" cur = self.findPalindrome(s, i, i+1) if len(cur) > len(ans): ans = cur return ans def findPalindrome(self, s: str, left: int, right: int): """ Find the longest palindrome by starting from `left` and `right` and going outwards. """ while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return s[left+1: right]
Approach:Use a fast pointer j to iterate through the array, and a slow pointer i to keep track of update progress.
If the current iterated element is equal to the previous one, skip it.
Otherwise, update the slow pointer with the current element and move to the next position.
Solution:
class Solution: def removeDuplicates(self, nums: List[int]) -> int: i = 0 for j in range(len(nums)): if j > 0 and nums[j] == nums[j-1]: continue nums[i] = nums[j] i += 1 return i
Note
For the skip condition highlighted above,
if j > 0 and nums[j] == nums[i-1]
also works (passes Leetcode) and might be more intuitive. At the beginning of each loop for j,
check if the current iterated element is the same as the last updated element, i.e., nums[i-1].
Approach:Use a fast pointer j to iterate through the array, and a slow pointer i to keep track of the position to place the next unique element.
Similar approach to the previous problem but beware of the wrong solution below, which yields wrong answer [1,1,2,3,_,_] for the example above.
That is because in this problem we need to keep at most two of the duplicates and nums[j-2] is possible to have been updated already (when j-2<=i).
Solution:
class Solution: def removeDuplicates(self, nums: List[int]) -> int: i = 0 for j in range(len(nums)):- if j > 1 and nums[j] == nums[j-2]:+ if j > 1 and nums[j] == nums[i-2]: continue nums[i] = nums[j] i += 1 return i
Note
For the skip condition above, the following two versions both pass Leetcode:
You are given a list of days which you are traveling on. To travel you are required to buy a ticket for each day,
there are three types of ticket passes with different costs that you can buy, each pass covers your travel for a consecutive number of days:
1-day pass(costs[0])
7-day pass(costs[1])
30-day pass(costs[2])
The goal is the find the minimum cost to be able to travel on all the given days.
Example:
Input: days = [1,4,6,7,8,20], costs = [2,7,15] Output: 11
You buy a 1-day pass for day 1, a 7-day pass(covering day 4 through day 10) for days 4,6,7,8 and a 1-day pass for day 20.
Solution:
Approach:DP with memoization. Define an array dp where dp[i] represents the minimum cost to travel each day
in the given list of days AND not later than day i.
For example, in the above example, dp[4] and dp[5] are both the minimum cost required to travel on days=[1,4].
The final answer is equal to dp[365] or dp[max(days)].
class Solution: def mincostTickets(self, days: List[int], costs: List[int]) -> int: # The minimum cost required to travel each day # in the given list of days AND not later than day i. # The final answer is equal to dp[365] or dp[max(days)] dp = [0] * 366 for i in range(1, 366): dp[i] = dp[i-1] if i in days: dp[i] = min(dp[i-1]+costs[0], dp[max(0,i-7)]+costs[1], dp[max(0, i-30)]+costs[2]) return dp[365]
class Solution: def findMaxLength(self, nums: List[int]) -> int: ans = 0 memo = {} presum = [0] * len(nums) for i in range(len(nums)): if i > 0: presum[i] += presum[i-1] if nums[i] == 1: presum[i] += 1 else: presum[i] += -1 if presum[i] not in memo: memo[presum[i]] = i if presum[i] == 0: ans = max(ans, i+1) if presum[i] in memo: ans = max(ans, i - memo[presum[i]]) return ans
Optimization:
As a matter of fact, we don’t need to use an array to store the prefix sum.
Note that in the previous solution, only presum[i] is used in each iteration,
so we can simply use a variable to store the latest prefix sum.
There is also another trick to simplify the code.
Notice that the if presum[i] == 0 was used to check the current prefix sum is 0.
This particaular case can be merged by initializing memo with memo = {0: -1}.
In this case presum[i] == 0 is equivalent to presum[i] in memo and i+1 is identical to i - memo[presum[i]].
The final version
class Solution: def findMaxLength(self, nums: List[int]) -> int: ans = 0 memo = {0: -1} total = 0 for i in range(len(nums)): if nums[i] == 1: total += 1 else: total += -1 if total not in memo: memo[total] = i ans = max(ans, i - memo[total]) return ans
Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
Example 2:
Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
Example 3:
Input: nums = [23,2,6,4,7], k = 13
Output: false
Approach:
class Solution: def checkSubarraySum(self, nums: List[int], k: int) -> bool: total = 0 memo = {0: -1} for i in range(len(nums)): total += nums[i] total %= k if total not in memo: memo[total] = i elif i - memo[total] >= 2: return True return False