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.

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