Coding Interview Preparation

December 15, 2021

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.

  1. keeping the required value and the current index in a hash table.
  2. using two pointers.
  3. 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.

  1. We find out the length of the longer string and iterate over it.
  2. We add the corresponding digits of the two strings and carry the 1 if necessary.
  3. We append the result to the result array.
  4. 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.

  1. 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.
  2. 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 < n a, 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


Profile picture

Written by Liu Yongliang who lives in Singapore. Also on Dev.to, LinkedIn, GitHub

© Copyright 2022 Liu Yongliang