6-9 2023 review deck

Question 1

19: Remove Nth Node From End of List

Answer 1

For remove Nth node from the end of List, the 2 pointers allow us loop through the list once, fast and slow pointer, we need to set a dummy node before head, move fast Nth time, then move both fast and slow until we hit the end of the Linked list. Then slow should be at the Node before the Node that we need to remove

Question 2

21: Merge Two Sorted Lists

Answer 2

Merge 2 sorted List - since we need to return a new list, we should create a dummy node, then build the list of the dummy node.
Compare the 2 list value, and add one at a time, the trick to remember is we might have list 1 or list 2 still have node after the while loop (while list1 and list2). So we need to account for the remainder node. We return dummy.next at the end

Question 3

206: Reverse Linked List

Answer 3

Reverse Linked List - need to set next, prev, current pointer.
Next = current.next = prev = current = next, 4 line a circle
Return prev which the the new list beginning

Question 4

121: Best Time to Buy and Sell Stock

Answer 4

Best time to buy and sell stock. We need to find the min price, and use today’s price - min price for the max profit, use min() to keep track of the min price and use max() to keep track of the Max profit

Question 5

141. Linked List Cycle

Answer 5

2 pointers, one fast, one slow, if slow == fast, meaning there is cycle in the linked list, the key is while fast and fast.next, if fast.next = None, then fast.next.next will error out.

Question 6

142. Linked List Cycle II

Answer 6

need to return the beginning of a linked-list cycle, we can use set to add the node into the set, if the first time node appear more than once, which mean that is the beginning of the cycle. we just need to loop through the linked-list, if the linked list reach to the end and no duplicate, then return None, there is no cycle

Question 7

160. Intersection of Two Linked Lists

Answer 7

Understand both set() and two pointers solution, 2 pointers is more optimal in term of using less space while set is easier to understand

Question 8

86.Partition List

Answer 8

create 2 sublists, left list with all the lesser value, the right list with all the greater or equal value. connect the 2 lists and return at the end. one key point of the right list last node will point back to one of left list node which create a loop and error out

Question 9

876.Middle of the Linked List

Answer 9

find the middle of the linked list, if there are 2 middle node, return the 2nd one, classic 2 pointers problem, fast and slow pointer, return slow pointer

Question 10

23.Merge k Sorted Lists

Answer 10

extension of 21, merge 2 sorted list. Break the problem into 2 part, 1 helper function to merge 2 list, then try to reduce the lists in half each time. K lists, time logK * N

Question 11

26. Remove Duplicates from Sorted Array

Answer 11

fast slow pointer, when fast pointer reach the end, return slow + 1 for the total number of unique element

Question 12

83.Remove Duplicates from Sorted List

Answer 12

same concept like 26, expect it is for linked-list, need to remember edge case and point the slow.next = None to avoid error

Question 13

27.Remove Element

Answer 13

modify list in place, can modify the order, return the length of the array without the target value element, is very similar to 26, instead of remove the duplicates, now remove the target value, since we don’t need to worry about the order, we can start to swap the value as soon as we see any value difference from the target value

Question 14

283.Move zeros

Answer 14

similar to remove duplicate 26, we need to move all the non-zero element to the front and preserve the relative order, keep track on the idx, and fill the idx to len(nums) with 0

Question 15

344. Reverse String

Answer 15

• given an array with char, return the reverse version of the array - 2 pointer, l, r , swap char in place, python can do s[l], s[r] = s[r], s[l]

Question 16

167. Two Sum II - input array is sorted

Answer 16

the array is sorted, then we can use 2 pointers left and right to find the index

Question 17

3. Longest Substring Without Repeating Characters

Answer 17

sliding window, store the already visited value in a set(), if new char, make the right ++, if the not new char, remove the index l char, left ++, to move the sliding window

Question 18

665.Non-decreasing Array

Answer 18

need to consider the modify the left or right value, to make the whole array non-decreasing

Question 19

11. Container With Most Water

Answer 19

area min(height_left, height_right) * right - left, move left if left <= right, other wise move right

Question 20

125. Valid Palindrome

Answer 20

classic 2 pointers, key is move l or r when the char is not alphanumeric first

Question 21

1344. Angle Between Hands of a Clock

Answer 21

calc the hr degree and min degree, if the angle greater than 180, use 360 - result to get the smaller angle

Question 22

1. Two Sum

Answer 22

using dict as a hashmap, the key can be target - num[i], and the value can be the index, if we get a number that match the key, then return the index of the 2 element

Question 23

20. Valid Parentheses

Answer 23

use stack, if the char. is close, we can check the if the stack have anything and the last one element match with the open, when the loop is over, if the stack have anything, return false

Question 24

13. Roman to Integer

Answer 24

code is simple, just a for loop to loop through the str, just need to determine if the smaller char in front of a larger one, if so, - else, just normal +

Question 25

122.Best Time to Buy and Sell Stock II

Answer 25

buy low, sell high, so compare the curr price with the prev one, if it went up, then it is a profit, add all the profit together and return

Question 26

14.Longest Common Prefix

Answer 26

use zip(*strs) to unpack and zip each char by char, if all char is the same, the set len will be 1, add that char to res

Question 27

189. Rotate Array

Answer 27

shift the array to right by k steps, need to do it in place, so reverse the array first, then break the input array into 2 at k steps, then reverse each parts, since we use the same logic 3 times, might be good for a helper function

Question 28

49. Group Anagrams

Answer 28

group all the str that are anagram together, use defaultdict(list), create 26 0 list, map the a to index 0 , z to index 25 in the list. add the str into res when they have the same key, Note: list can’t be a key in dict, but tuple can

Question 29

392. Is Subsequence

Answer 29

use two pointer for s, and t, if 2 char is the same, add 1 to pointer s, at the end, compare if the pointer s same as the len(s)

Question 30

202. Happy Number

Answer 30

it will either get to 1 eventually or it will got to a loop, use set() to check if duplicate shows up, if so , it not happy

Question 31

209.Minimum Size Subarray Sum

Answer 31

classic two pointers, first create a window that >= than the target, then shrink the left to see if we can get a smaller window size

Question 32

80.Remove Duplicates from Sorted Array II

Answer 32

2 pointers problem, the trick is we can do at most swap twice

Question 33

76.Minimum Window Substring

Answer 33

use the sliding window frame, then process the window, create a need and window dict to keep track of what we need, and what is in the window, when we find a match update valid, when valid and the len(need) is the same, we found one potential, then we try to shrink the window, we use 2 var, start and length to keep track of when we start, and min length we need for a valid solution

Question 34

162. Find Peak Element

Answer 34

find peak element, return index, peak element mean the current element is larger than the next one, it would return any peak, binary search

Question 35

35.Search Insert Position

Answer 35

classic binary search, l = mid + 1, r = mid - 1, return l

Question 36

134. Gas Station

Answer 36

greedy, if sum(gas) >= sum(cost), we have a solution, we only have 1 solution by the question. check each different, add to total, if total even go below 0, set res = i + 1, and check the next index

Question 37

128.Longest Consecutive Sequence

Answer 37

use a set , check to see if the left element is in the set, for example, if 100 in the set, check if 101 in the set
the start of a sequence, if a element don’t have left element, then it is a start, EX.1 , 4, there is left , 3 in the set, so 4 is not the start of of a sequence

Question 38

215. Kth Largest Element in an Array

Answer 38

using heapq, then we have a min heap, after pop off len(nums) - k times, we get what we want, it will be better than the sorting, quickselect would also be another solution

Question 39

112.Path Sum

Answer 39

since we need to the end of leaf node, we are doing inorder DFS, use recursion. helper function would be helpful too