Coding Interview Preparation
P.S Future me from Dec 2022: Hi there! Since the start of 2022, I have decided to approach interview preparation with "Spaced Repetition" and doing peer interviews. You can see all my attempts and solutions (Python) to LeetCode questions that I have done here.
This is more like a note to self, because I am also tired of doing and forgetting about how to solve these coding problems. What a joke.
160. Intersection of Two Linked Lists
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
In order for two linked lists to intersect, they must have at least one node in common. That node, in particular, must be in the shorter list. Thus, the idea is to first find out the length of each list. This can be done by traversing the list and counting the number of nodes. The next step is to travel through the longer list and stop when the current node is the same as the node in the shorter list. Now, we start by traversing either list (since both are at the same length). At each step, we check if the node is the same in both lists. If they are, we return the node. Else, we reach the end and return null.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
len_A = self.findLength(headA)
len_B = self.findLength(headB)
while len_A > len_B:
headA = headA.next
len_A -= 1
while len_B > len_A:
headB = headB.next
len_B -= 1
while headA:
if headA == headB:
return headA
headA = headA.next
headB = headB.next
return None
def findLength(self, head: ListNode):
if not head:
return 0
ans = 0
while head:
ans += 1
head = head.next
return ans
101. Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
The binary tree is symmetric if the left subtree is a mirror reflection of the right subtree. Given just one root node, we can check whether the left node is the same as the right node. If the two children are not leaf nodes, we need to check whether the left node's left is the same as the right node's right. Similarly, we need to check whether the left node's right is the same as the right node's left. Traversing the tree can be done iteratively or recursively. In this case, we can do a recursive traversal to check whether the tree is symmetric.
# 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
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
return self.helper(root.left, root.right)
def helper(self, nodeLeft, nodeRight):
if nodeLeft and nodeRight:
if nodeLeft.val != nodeRight.val:
return False
return (self.helper(nodeLeft.left, nodeRight.right) and
self.helper(nodeLeft.right, nodeRight.left))
if nodeLeft == nodeRight:
return True
return False
144. Binary Tree Preorder Traversal
Given the root of a binary tree, return the preorder traversal of its nodes' values.
There are three orders of traversal: pre-order, in-order, post-order. This can be thought of as given a node, should I traverse self before the left and the right node; or left first, self and the right after; or the left, the right and then self. To do it recursively, we can add to the list in the order of traversal. To do it iteratively, we can use a list that serves as a kind of stack. Given a stack, we pop the last item off in each iteration. Whenever we see a node, we add the value to the answer list. Next, if the node has a right child node, we add that to the stack first. Then we do the same for the left child node. If there are only three nodes in total, it is quite easy to understand that the left node will then be popped, value added to the answer list, and finally the right node. This is exactly the order we want.
# 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
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
# 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
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack = [root]
ans = []
while stack:
curr = stack.pop()
ans.append(curr.val)
if curr.right:
stack.append(curr.right)
if curr.left:
stack.append(curr.left)
return ans
206. Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
When reversing a linked list, the key is to keep track of the nodes before replacing the reference. This means the previous and the next nodes need to be handled with care.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
prev = None
while head:
temp = head.next
head.next = prev
prev = head
head = temp
return prev
53. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array.
When traversing an array, sometimes it's about pointers and sub problems. In this case, we can travel through the array with a single pointer. At each point, we update the value at the index to be the maximum of the following two: the value currently at the index, or the sum of the value at the previous index and current index. This way, we have the maximum value achievable at each point. Note that this subarray is a contiguous one (no gaps). Lastly, we can find the maximum value out of all the values in the array.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
nums[i] = max(nums[i],nums[i-1]+nums[i])
return max(nums)
83. Remove Duplicates from Sorted List
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
When there is a duplicate, what we need to do is to skip it by establishing the link between the current node and the next next node instead. The catch is that if there are multiple duplicated nodes, just jumping over one node is not enough. It has to connect to the next node of the different value.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
ans = head
while head:
if head.next and head.next.val == head.val:
head.next = head.next.next
else:
head = head.next
return ans
70. Climbing Stairs
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?
An incremental problem that requires a dynamic programming solution.
- If n = 0, 1 way to climb i.e don't climb.
- n = 1, 1 way to climb i.e take 1 step.
- n = 2, 2 ways to climb i.e take 2 of 1 step or take 1 of 2 steps.
- n = 3, reachable from n-1 and n-2 stairs. Thus the number of ways is the sum of the ways at n-1 and ways at n-2.
For dynamic programming problems, we can start with a list [] and fill the list (or the table/2D array for other problems). At last, we will get the answer we want.
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return 1
dp = [1, 1]
for i in range(2, n+1):
dp.append(dp[i-1] + dp[i-2])
return dp[-1]
122. Best Time to Buy and Sell Stock II
You are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve.
In one pass, we can sell whenever there is a profit and advance if none. This way the sum of the profit is still the maximum.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans = 0
pt = 0
while pt < len(prices) - 1:
if prices[pt] < prices[pt + 1]:
ans += prices[pt + 1] - prices[pt]
pt += 1
return ans
300. Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
A subsequence is different from a continuous subarray. Another thing to note here is that it is strictly increasing. This means a duplicate sequence of numbers does not count. The idea is to use dynamic programming and break the problem down into smaller sequences. Using two pointers, we can start from the beginning with index 0 and index 1. At each index of the right pointer, we can ask if the current value is strictly larger than the values at the left pointer. If so, we can take the maximum of
- the value at the right pointer
- or the value at the left pointer add 1. Else, we advance the left pointer until it is one step away from the right pointer. If so, we then reset the left pointer to start and advance the right pointer. The dp array can be initialize with all 1s since this is the default for any value. At last, find the maximum value of the dp array.
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [1] * len(nums)
if len(nums) == 1:
return 1
pt_a = 0
pt_b = 1
while pt_b < len(nums):
pt_a = 0
while pt_a < pt_b:
if nums[pt_b] > nums[pt_a]:
dp[pt_b] = max(dp[pt_b], dp[pt_a] + 1)
pt_a += 1
pt_b += 1
return max(dp)
56. Merge Intervals
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Overlap occurs when start of one array is smaller or equal to the end of another array. We can first sort the intervals by their start values. Then, we can start merging them. For each interval, we check if the current interval overlaps with the previous interval. If so, we merge the two intervals. If not, we add the current interval to the result. We can keep a pointer to the current interval while looping through the intervals. Only when there is no overlap, we add the current interval to the result. Else we update the value of the pointer.
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if len(intervals) <= 1:
return intervals
intervals.sort(key=lambda x: x[0])
ans = [intervals[0]]
curr = intervals[0]
for i in range(1, len(intervals)):
if intervals[i][0] <= curr[1]:
curr[0] = min(curr[0], intervals[i][0])
curr[1] = max(curr[1], intervals[i][1])
else:
ans.append(intervals[i])
curr = intervals[i]
return ans
39. Combination Sum
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different. It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
This problem can be sovled by backtracking. Whenever we see a value, we ask if we can use it. If we can, we add it to the current combination and recurse. If we cannot, we backtrack. Need to be careful with the recursive function. It has to carry the information about the current combination. After computing the two situations (to take or not to take), we only extend the value into the result if the value is not an empty list.
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
return self.helper(candidates, [], target)
def helper(self, candidates, answer, target):
if target < 0 or candidates == []:
return []
elif target == 0:
return [answer]
result = []
l1 = self.helper(candidates, answer+[candidates[0]], target-candidates[0])
if l1 != []:
result.extend(l1)
l2 = self.helper(candidates[1:], answer, target)
if l2 != []:
result.extend(l2)
return result
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Doing it in one pass will require two pointers. In addition, we need a hash set to keep track of the characters we have seen (it is also the current substring). Note that when we decide to move the left pointer, we need to remove the left pointer value from the hash set. This is because we are going beyond the current substring. Keep track of the current maximum length (of the hash_set) and update it accordingly.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
curr_max = 0
pt_a = 0
pt_b = 0
hash_set = set()
while pt_b != len(s):
if s[pt_b] not in hash_set:
hash_set.add(s[pt_b])
curr_max = max(len(hash_set), curr_max)
pt_b+=1
else:
hash_set.remove(s[pt_a])
pt_a+=1
return curr_max
1. Two Sum
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.
There are a few ways to solve this.
- keeping the required value and the current index in a hash table.
- using two pointers.
- binary search.
For No1, the key is to keep track of the required value and the current index. Then, in one pass, we can check if there is a suitable match by looking at the current value against the hashmap. If there is, we return the indices.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hash_map = {}
for i in range(len(nums)):
if nums[i] in hash_map:
return [hash_map[nums[i]], i]
hash_map[target - nums[i]] = i
15. 3Sum
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.
To solve it, we can reuse the logic of twoSum. This time, every value we examine, we ask if there are two values of the list excluding current index that sum to the negative of the current value. What needs to be handled with care is that duplicate values are not allowed. This means we can first sort the list, then whenever we start our iteration, we check if the current value is not the same as the previous value. If it is, we skip it. Another important thing is that the 2sum here may have more than one solution. We need to take all unique solutions from 2sum. This means we need to update the twosum to allow more but unique solutions.
An alternative is to sort the array and use two pointers. The looping pointer starts from the beginning, then the left pointer and the right pointer are at the bound of the remaining array. Because the array is sorted, we can tell which pointer to advance by comparing the sum with 0. If it is larger than 0, it means we should reduce the right pointer. What needs to be cautious is that we need to skip duplicate values.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans = []
nums.sort()
for i in range(len(nums)):
if i == 0 or nums[i] != nums[i-1]:
remain = nums[i+1:]
combs = self.twoSum(remain, -nums[i])
if combs:
for val in combs:
ans.append([nums[i]] + val)
return ans
def twoSum(self, nums: List[int], target: int) -> List[int]:
hash_map = {}
ans = []
for i in range(len(nums)):
if nums[i] in hash_map:
if [target-nums[i], nums[i]] not in ans:
ans.append([target-nums[i], nums[i]])
hash_map[target - nums[i]] = i
return ans
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3:
return []
ans = []
nums.sort()
for i in range(len(nums)):
left = i + 1
right = len(nums) - 1
if nums[i] > 0:
break # no negative number, impossible to find solution
if i >= 1 and nums[i] == nums[i - 1]:
continue # ignore duplicate
while left < right:
a, b, c = nums[i], nums[left], nums[right]
curr = a + b + c
if curr == 0:
ans.append([a, b, c])
while left != right and nums[left] == nums[left + 1]:
left += 1
while left != right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif curr < 0 :
left += 1
else:
right -= 1
return ans
415. Add Strings
Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string. You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.
One possible solution is described below.
- We find out the length of the longer string and iterate over it.
- We add the corresponding digits of the two strings and carry the 1 if necessary.
- We append the result to the result array.
- Lastly, we join the result array together.
Note that we reverse the strings so that we can start with index zero being the rightmost digit in typical addition.
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
carry = 0
num1, num2 = (num1, num2) if len(num2) > len(num1) else (num2, num1)
num1, num2 = num1[::-1], num2[::-1]
pt = 0
ans = []
while pt < len(num2):
curr = int(num2[pt]) + (int(num1[pt]) if pt < len(num1) else 0) + carry
if curr >= 10:
carry = curr // 10
curr = curr - 10
else:
carry = 0
ans.append(str(curr))
pt+=1
if carry:
ans.append(str(carry))
return "".join(ans[::-1])
704. Binary Search
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.
There are a few things to take note when doing binary search:
- When we say the target value is within a range, is the left and right index inclusive?
- If both ends are inclusive, when we update the bound, we need to use mid+1 or mid-1.
- For an iterative solution, we need to continue the while loop util left == right (since both are inclusive and possible value)
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
# both ends inclusive
left = 0
right = len(nums) - 1
while (left <= right):
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1
27. Remove Element
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements. Return k after placing the final result in the first k slots of nums. Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
There are two ways of using two pointers to solve this problem.
- With a fast and a slow pointer, both start from the beginning of the array. We move the fast pointer and if we encounter a value that needs not be removed, we update the value at the slow pointer with the value at the fast pointer, and then move both pointers forward. Else, we simply moves the fast pointer forward. At the end, we return the slow pointer.
- Since the relative order of the elements may be changed, we can use a start and an end pointer. If the value at the start pointer needs to be removed, we can take the value at the end of the array and move it to the start. We then decrease the end pointer by one since it is as though the value at the end no longer exists. For the start pointer, we only move if the value does not need to be removed.
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow = 0
fast = 0
while fast < len(nums):
if nums[fast] != val:
nums[slow] = nums[fast]
slow+=1
fast+=1
return slow
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
st,end=0,len(nums)
while st!=end:
if nums[st]==val:
nums[st]=nums[end-1]
end-=1
else:
st+=1
return end
977. Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
A key observation is that the largest possible square values are at both ends of the array (because of negative numbers). Therefore, we can use a start and a end pointer, and update a result array from the end (by taking the largest square value in each iteration).
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
result = [0] * len(nums)
start, end, k = 0, len(nums) - 1, len(nums) - 1
while k >= 0:
if nums[start]**2 > nums[end]**2:
result[k] = nums[start]**2
start+=1
else:
result[k] = nums[end]**2
end-=1
k-=1
return result
209. Minimum Size Subarray Sum
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
This problem can be solved by using the sliding window technique. The end of the window is increased until the window contains a sum larger than or equal to target. At that point, the start of the window is moved until the window contains a sum smaller than the target.
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
result = float("inf")
start = 0
curr_sum = 0
for end in range(len(nums)):
curr_sum += nums[end]
while curr_sum >= target:
curr_sum -= nums[start]
result = min(result, end - start + 1)
start+=1
return 0 if result == float("inf") else result
59. Spiral Matrix II
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.
The key is to keep the invariant that we iterate over with inclusive start and exclusive end. Then, we can start writing the values from the outermost loop, moving inward. Note that if n is an odd number, we need to write the value at the center.
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
result = [[0] * n for _ in range(n)]
# exclusive end
left, right, top, bottom = 0, n-1, 0, n-1
curr = 1
while left < right and top < bottom:
for i in range(left, right):
result[top][i] = curr
curr += 1
for i in range(top, bottom):
result[i][right] = curr
curr += 1
for i in range(right, left, -1):
result[bottom][i] = curr
curr += 1
for i in range(bottom, top, -1):
result[i][left] = curr
curr += 1
left +=1
right -=1
top +=1
bottom -=1
if n % 2 != 0:
result[n//2][n//2] = curr
return result
203. Remove Linked List Elements
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
While the solution can simply be iterating through the linked list and removing all the nodes that have the targeted value, there are a few points to note. One common trick is to use a dummy head node that will help make the processing simpler. Another thing is that when advancing the pointer, duplicates need to be handled by only moving on after the nodes ahead with the same value have all been "removed".
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy_head = ListNode(0, head)
curr = dummy_head
while curr:
if curr.next and curr.next.val == val:
curr.next = curr.next.next
else: # dont advance until there is no duplicate
curr = curr.next
return dummy_head.next
242. Valid Anagram
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
Consider using a hash table when dealing with checking membership. Here, we first add in a hash table the frequency of the elements in the first string. Then we decrease the frequency for the elements when iterating through the second string. The resultant dictionary should have all entries with the same frequency of zero.
Note that if we know the string is only make up of the lower case letters, we can initialize the hash table with the 26 elements of the alphabet. This way the space complexity is O(1). Since alphabet can also be represented by number, it is possible to use an array as a hash table. This way we increment at the corresponding index.
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
hash_table = dict()
for i in s:
hash_table[i] = hash_table.get(i, 0) + 1
for i in t:
if i in hash_table:
hash_table[i] = hash_table.get(i) - 1
else:
return False
for i in hash_table:
if hash_table[i] != 0:
return False
return True
349. Intersection of Two Arrays
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
The part about being unqiue and finding intersection, is a good hint for the use of a set. Since the underlying structure of a set is more efficient at handling the check for intersection.
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1).intersection(set(nums2)))
202. Happy Number
Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.
There are two important things to take note. One is the way to sum the square of the digits
of a number. This can be done by finding the digit with %10 and //10 to get rid of the last digit. The second point is that the infinite loop is an indication that we can use a set to check if such an incident actually occurs.
class Solution:
def isHappy(self, n: int) -> bool:
check = set()
while True:
n = self.sumSquare(n)
if n == 1:
return True
if n in check:
return False
check.add(n)
return False
def sumSquare(self, num):
ans = 0
while num:
ans += (num % 10)**2
num //= 10
return ans
454. 4Sum II
Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:
0 <= i, j, k, l < n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
This question is slightly different from 3Sum or 4Sum. However, the logic is similar to 2Sum with the hash table approach. We can keep the sum of values in list1 and list2, and check for the difference of 0 - sum of values in list3 and list4. Note that this time we keep track of the frequency as the value of the hash table.
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
hash_map = dict()
count = 0
for x in nums1:
for y in nums2:
hash_map[x + y] = hash_map.get(x + y, 0) + 1
for h in nums3:
for k in nums4:
count += hash_map.get(0 - h - k, 0)
return count
383. Ransom Note
Given two stings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise. Each letter in magazine can only be used once in ransomNote.
This is similar to anagram checking, which is to find out if two words have letters of the same frequency but perhaps in a different order. In this case, we can construct a hash table with the frequency from magazine, and check through ransomNote to find out whether there are enough letters. To be more efficient, we can use an array as a hash table. Since we use 26 letters (slots), the space complexity is O(1).
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
if len(ransomNote) > len(magazine):
return False
record = [0] * 26
for i in magazine:
record[ord(i) - 97] +=1
for j in ransomNote:
record[ord(j) - 97]-=1
if record[ord(j) - 97] < 0:
return False
return True
344. Reverse String
Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory.
This is a two pointer reversal.
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
start = 0
end = len(s) - 1
while start < end:
s[start], s[end] = s[end], s[start]
start += 1
end -= 1
541. Reverse String II
Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string. If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.
It can be done with traversing the array by incrementing the pointer by 2*k. This way the handling of the iteration is simpler.
class Solution:
def reverseStr(self, s: str, k: int) -> str:
s = list(s)
for i in range(0, len(s), 2*k):
curr = s[i:i+k]
curr.reverse()
s[i:i+k] = curr
return "".join(s)
20. Valid Parentheses
Given a string s containing just the characters '(', ')', ', ', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order.
In this case, the parentheses are only valid if they are closed with nothing in the middle. Thus, we can use a stack solution for this. One additional trick is that we can store the required type of brackets (the right pairs) in the stack.
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for i in s:
if i == '(':
stack.append(')')
elif i == '{':
stack.append('}')
elif i == '[':
stack.append(']')
elif not stack:
return False
elif i != stack[-1]:
print('s')
return False
else:
stack.pop()
return True if not stack else False
226. Invert Binary Tree
Given the root of a binary tree, invert the tree, and return its root.
The important thing is to know how to recurse properly. The stopping condition is when the node is None. The recursion is done by inverting the left and right subtrees. Finally we return the root.
# 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
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
77. Combinations
Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]. You may return the answer in any order.
The use of backtracking can help solve this problem. For standard backtracking, we need to know three things
- think of the execution as a recursion tree, what's the leaf condition to stop?
- what's the iterative for loop to move through the values horizontally?
- how to store and update the values?
In this case, we can keep the result and temporary list in the outer function and define an inner backtracking function. Note that a copy of the path is made each time to avoid accidental mutation.
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
path = []
def backtrack(n, k, startIdx):
if len(path) == k:
result.append(path[:])
return
for x in range(startIdx, n+1):
path.append(x)
backtrack(n, k, x + 1)
path.pop()
backtrack(n, k, 1)
return result
18. 4Sum
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < na, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Similar to the 3 sum problem, we can use multiple pointers to solve this problem. The key is to know how to update the pointers and how to handle duplicates. For duplicates, we need to run on the first value in the row and skip the neighbor values.
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if len(nums) < 4:
return []
ans = []
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, len(nums)):
if j > i + 1 and nums[j] == nums[j-1]:
continue
l = j + 1
r = len(nums) - 1
while l < r:
curr = nums[i] + nums[j] + nums[l] + nums[r]
if curr < target:
l+=1
elif curr > target:
r-=1
else:
ans.append([nums[i],nums[j],nums[l],nums[r]])
while l < r and nums[r] == nums[r - 1]:
r -=1
while l < r and nums[l] == nums[l+1]:
l+=1
r-=1
l+=1
return ans
24. Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)
In order to swap nodes properly, we can use a dummy head to make processing standardized. A thing to note is that every operation affects three nodes. If we can handle the three nodes well, the rest will just follow accordingly.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(next = head)
curr = dummy
while curr.next and curr.next.next:
temp = curr.next
temp2 = curr.next.next
next_start = curr.next.next.next
curr.next = temp2
curr.next.next = temp
curr.next.next.next = next_start
curr = curr.next.next
return dummy.next
19. Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
The requirement to do it in one pass is an indication of double pointers. In this case, the fast pointer should be advanced n + 1steps ahead of the slow pointer. Then both pointers move until the fast pointer reaches the end of the list (NULL). Use a dummy head to make it easier.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(next=head)
fast = dummy
slow = dummy
for i in range(n+1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
151. Reverse Words in a String
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.
Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?
In order to do it in-place, we can use the following steps:
- remove unnecessary spaces
- reverse entire string
- reverse the words
One thing to note is the way of removing spaces. If done incorrectly, this step will be expensive. In cases where String is immutable in the language, there's no choice but to use O(n) extra space.
class Solution:
def reverseWords(self, s: str) -> str:
s = self.removeSpace(s)
s = self.reverse(list(s))
if len(s) <= 1:
return "".join(s)
l = 0
ans = []
for r in range(1, len(s)):
if s[r] == ' ':
ans.append("".join(self.reverse(list(s[l:r]))))
l = r+1
if r + 1 == len(s):
ans.append("".join(self.reverse(list(s[l:r+1]))))
l = r+1
return " ".join(ans)
def removeSpace(self, s):
# in place if string is mutable
l = 0
r = 0
s = list(s)
while r < len(s) and s[r] == ' ':
r+=1
for i in range(r, len(s)):
if i > 0 and s[i] == ' ' and s[i-1] == ' ':
continue
s[l] = s[i]
l+=1
if s[l-1] == ' ':
l-=1
s = s[:l]
return "".join(s)
def reverse(self, s):
l = 0
r = len(s) - 1
while l < r:
s[l], s[r] = s[r], s[l]
l+=1
r-=1
return s
28. Implement strStr()
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
This question can be solved by implementing KMP algorithm. The idea is to have a prefix suffix array that can be used to find the next character in the needle for comparison. This means when there is a mismatch, we use the array to hopefully start at a position away from the beginning. This can happen for cases like:
aabaab->[0,1,0,1,2,3]
When implementing the solution, one thing to note is that when there is a mismatch, we should a while loop to update the pointer.
For example, in the case of inputs being
"aabaaabaaac" "aabaaac"
Without while loop, the pattern array becomes:
[0, 1, 0, 1, 2, 0, 0]
However, the correct one should be:
[0, 1, 0, 1, 2, 2, 0]
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(needle) > len(haystack):
return -1
if len(needle) == 0:
return 0
p = self.pattern(needle)
pt = 0
for i in range(len(haystack)):
curr = haystack[i]
while pt > 0 and needle[pt] != curr:
pt = p[pt-1]
if needle[pt] == curr:
pt+=1
if pt == len(needle):
return i - len(needle) + 1
return -1
def pattern(self, needle):
ans = [0] * len(needle)
l = 0
for r in range(1, len(needle)):
while l > 0 and needle[l] != needle[r]:
l = ans[l-1]
if needle[l] == needle[r]:
ans[r] = l + 1
l+=1
return ans
459. Repeated Substring Pattern
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Using KMP again, we first need to create the helper array. After that, we can verfiy that the last element in the helper array is not zero and if the length of the original string modulo (the length of the string - number at the end of the helper) is equal to zero.
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
if len(s) == 0:
return False
p = self.pattern(s)
if p[-1] != 0 and len(s) % (len(s) - p[-1]) == 0:
return True
return False
def pattern(self, s):
ans = [0] * len(s)
if len(s) <= 1:
return ans
l = 0
for r in range(1,len(s)):
while l > 0 and s[l] != s[r]:
l = ans[l-1]
if s[l] == s[r]:
ans[r] = l+ 1
l+=1
return ans
455. Assign Cookies
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Locally, the best thing to do is to give the large cookie to the child with the maximum satisfiable greed factor. This is obviously more optimal than giving the cookie to someone who can be satisfied by a smaller cookie. With this strategy, we can achieve the global optimal solution.
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
pt = len(s) - 1
ans = 0
for i in range(len(g)-1, -1, -1):
if pt >= 0 and g[i] <= s[pt]:
ans +=1
pt-=1
return ans
239. Sliding Window Maximum
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Creating a custom data structure to help with this question. The hidden logic is the use of a queue. The queue keeps the largest element as the first element. The rest of the elements are in decreasing order. It is important to handle the adding and deleting of the elements in the queue. With the help of the queue, we can iterate the main list and get the max value in the sliding window.
class MyQueue:
def __init__(self):
self.q = deque()
def pop(self, val):
if self.q and self.q[0] == val:
self.q.popleft()
def push(self, val):
while self.q and self.q[-1] < val:
self.q.pop()
self.q.append(val)
def front(self):
return self.q[0]
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = MyQueue()
ans = []
for i in range(k):
q.push(nums[i])
ans.append(q.front())
for i in range(k, len(nums)):
q.pop(nums[i-k])
q.push(nums[i])
ans.append(q.front())
return ans
225. Implement Stack using Queues
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).
Follow-up: Can you implement the stack using only one queue?
The one queue solution works by adding the elements to the back of the queue in order to retrieve the element at the end.
from collections import deque
class MyStack:
def __init__(self):
self.queue = deque()
def push(self, x: int) -> None:
self.queue.append(x)
def pop(self) -> int:
if self.empty():
return None
if len(self.queue) == 1:
return self.queue.popleft()
for i in range(len(self.queue) - 1):
self.queue.append(self.queue.popleft())
return self.queue.popleft()
def top(self) -> int:
ans = self.pop()
self.push(ans)
return ans
def empty(self) -> bool:
return len(self.queue) == 0
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
347. Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
There is this interesting O(n) solution proposed by DBabichev in the discussion section. The gist of it is to keep buckets of elements in different frequencies. So for example an input of
[1,1,1,2,2,3]
2
The bucket would be: [[], [3], [2], [1], [], [], []]
Then we simply flattern and reverse the bucket, and finally return the first k frequency elements.
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
ans = [[] for i in range(len(nums))]
h = {}
for i in nums:
h[i] = h.get(i, 0) + 1
for key, val in h.items():
ans[val-1].append(key)
ans = [item for sublist in ans for item in sublist][::-1]
return ans[:k]
The other solution is to use a priority queue.
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
h = {}
for i in range(len(nums)):
h[nums[i]] = h.get(nums[i], 0) + 1
pq = []
for key, v in h.items():
heapq.heappush(pq, (v,key))
if len(pq) > k:
heapq.heappop(pq)
ans = []
for i in range(k):
ans.append(heapq.heappop(pq)[1])
return ans[::-1]
Binary Tree Traversal - Recursive
Doing it properly with a structured code will help with the solution.
# Preorder
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
self.helper(root, res)
return res
def helper(self, node, res):
if not node:
return
res.append(node.val)
self.helper(node.left, res)
self.helper(node.right, res)
# Postorder
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
self.helper(root, res)
return res
def helper(self, node, res):
if not node:
return
self.helper(node.left, res)
self.helper(node.right, res)
res.append(node.val)
# Inorder
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
self.helper(root, res)
return res
def helper(self, node, res):
if not node:
return
self.helper(node.left, res)
res.append(node.val)
self.helper(node.right, res)
Binary Tree Traversal - Iterative
There is a difference between preorder and the other two orders.
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
s = [root]
ans = []
while s:
p = s.pop()
if p:
ans.append(p.val)
s.append(p.right)
s.append(p.left)
return ans
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
s = []
ans = []
c = root
while c or s:
if c:
s.append(c)
c = c.left
else:
c = s.pop()
ans.append(c.val)
c = c.right
return ans
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
s = [root]
ans = []
while s:
p = s.pop()
if p:
ans.append(p.val)
s.append(p.left)
s.append(p.right)
return ans[::-1]
102. Binary Tree Level Order Traversal
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).
This is basically BFS traversal.
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
ans=[]
q = deque()
q.append(root)
while q:
s = len(q)
temp = []
for _ in range(s):
curr = q.popleft()
temp.append(curr.val)
if curr.left:
q.append(curr.left)
if curr.right:
q.append(curr.right)
ans.append(temp)
return ans
107. Binary Tree Level Order Traversal II
Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).
Similar to the original traversal, just need to reverse the result. In this case we can try out an recursive version of the solution.
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
self.helper(root, 0, ans)
return ans[::-1]
def helper(self, node, depth, ans):
if not node:
return
if len(ans) == depth:
ans.append([])
ans[depth].append(node.val)
self.helper(node.left, depth+1, ans)
self.helper(node.right, depth+1, ans)
199. Binary Tree Right Side View
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Once we know how to traverse the tree level by level, the trick is to adjust the algorithm to meet the need of the question. In this case, we can tell the rightmost element by seeing the size. Hence, a iterative solution is easier.
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
q = deque()
q.append(root)
ans = []
while q:
s = len(q)
for i in range(s):
curr = q.popleft()
if i == s-1:
ans.append(curr.val)
if curr.left:
q.append(curr.left)
if curr.right:
q.append(curr.right)
return ans
637. Average of Levels in Binary Tree
Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.
Same as above, just traverse the tree and take note of the information required to calculate the average.
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
if not root:
return []
ans = []
s = deque()
s.append(root)
ans = []
while s:
l = len(s)
temp = []
for _ in range(l):
c = s.popleft()
temp.append(c.val)
if c.left:
s.append(c.left)
if c.right:
s.append(c.right)
ans.append(sum(temp)/len(temp))
return ans
429. N-ary Tree Level Order Traversal
Given an n-ary tree, return the level order traversal of its nodes' values. Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Same as above.
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return []
ans = []
s = deque()
s.append(root)
while s:
temp = []
l = len(s)
for _ in range(l):
c = s.popleft()
temp.append(c.val)
if c.children:
for i in c.children:
s.append(i)
ans.append(temp)
return ans
515. Find Largest Value in Each Tree Row
Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).
Same as above! Just need to traverse the tree via BFS and handle the cases at each level.
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
s = deque()
s.append(root)
ans = []
while s:
l = len(s)
curr_max = float('-inf')
for _ in range(l):
c = s.popleft()
curr_max = max(curr_max, c.val)
if c.left:
s.append(c.left)
if c.right:
s.append(c.right)
ans.append(curr_max)
return ans
116. Populating Next Right Pointers in Each Node
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.
Need to take note of not assigning the last element in the level.
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return None
q = deque()
q.append(root)
while q:
l = len(q)
for i in range(l):
c = q.popleft()
if i!= l-1:
c.next = q[0]
if c.left:
q.append(c.left)
if c.right:
q.append(c.right)
return root
117. Populating Next Right Pointers in Each Node II
Given a binary tree Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.
This question differs from the above one in that the tree may not be completely filled. However, the main logic is still the same. In this working we can try the alternative approach of keeping the tail node during level traversal.
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return None
q = deque([root])
while q:
l = len(q)
tail = None
for _ in range(l):
c = q.popleft()
if tail:
tail.next = c
if c.left:
q.append(c.left)
if c.right:
q.append(c.right)
tail = c
return root
104. Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
We can still use level traversal for this. Instead doing any processing, we just increment the depth by 1 for each level.
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
ans = 0
while q:
l = len(q)
for _ in range(l):
c = q.popleft()
if c.left:
q.append(c.left)
if c.right:
q.append(c.right)
ans+=1
return ans
111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Need to be careful with the definition of depth. When there is no nodes at all, the depth is zero. When there is one node (the root), the depth is already 1.
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
dep = 1
while q:
l = len(q)
for i in range(l):
c = q.popleft()
if not c.left and not c.right:
return dep
if c.left:
q.append(c.left)
if c.right:
q.append(c.right)
dep+=1
return dep
216. Combination Sum III
Find all valid combinations of k numbers that sum up to n such that the following conditions are true: Only numbers 1 through 9 are used. Each number is used at most once. Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
The standard backtracking working can be applied here. There are a few things to do to prune the unnecessary branches.
- if the current sum is already larger than the target, return immediately
curr_sum > target
- if there are not enough number left to choose, return immediately
for i in range(startIdx, 9-(k-len(path))+2)
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
result = []
path = []
def backtrack(n, k, curr, startIdx):
if curr > n:
return
if len(path) == k:
if curr == n:
result.append(path[:])
for i in range(startIdx, 9-(k -len(path))+2):
curr+=i
path.append(i)
backtrack(n, k, curr, i+1)
path.pop()
curr-=i
backtrack(n, k, 0, 1)
return result
100. Same Tree
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
This is similar to the 101 question on symmetric tree. The only difference is that we need to check the value of the nodes on the same side.
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
return self.helper(p, q)
def helper(self, a, b):
if not a and b:
return False
elif not b and a:
return False
elif not a and not b:
return True
elif a.val != b.val:
return False
else:
l = self.helper(a.left, b.left)
r = self.helper(a.right, b.right)
return l and r
572. Subtree of Another Tree
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.
For this question, we can still use the similar logic for checking tree equality.
# 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
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if self.helper(root, subRoot):
return True
q = deque([root])
while q:
c = q.popleft()
if self.helper(c.left, subRoot) or self.helper(c.right, subRoot):
return True
if c.left:
q.append(c.left)
if c.right:
q.append(c.right)
return False
def helper(self, a, b):
if not a and b:
return False
elif not b and a:
return False
elif not a and not b:
return True
elif a.val != b.val:
return False
else:
l =self.helper(a.left, b.left)
r =self.helper(a.right, b.right)
return l and r