6-9 2023 review deck Flashcards
19: Remove Nth Node From End of List
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
21: Merge Two Sorted Lists
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
206: Reverse Linked List
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
121: Best Time to Buy and Sell Stock
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
- Linked List Cycle
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.
- Linked List Cycle II
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
- Intersection of Two Linked Lists
Understand both set() and two pointers solution, 2 pointers is more optimal in term of using less space while set is easier to understand
86.Partition List
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
876.Middle of the Linked List
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
23.Merge k Sorted Lists
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
- Remove Duplicates from Sorted Array
fast slow pointer, when fast pointer reach the end, return slow + 1 for the total number of unique element
83.Remove Duplicates from Sorted List
same concept like 26, expect it is for linked-list, need to remember edge case and point the slow.next = None to avoid error
27.Remove Element
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
283.Move zeros
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
- Reverse String
- 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]
- Two Sum II - input array is sorted
the array is sorted, then we can use 2 pointers left and right to find the index
- Longest Substring Without Repeating Characters
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
665.Non-decreasing Array
need to consider the modify the left or right value, to make the whole array non-decreasing
- Container With Most Water
area min(height_left, height_right) * right - left, move left if left <= right, other wise move right
- Valid Palindrome
classic 2 pointers, key is move l or r when the char is not alphanumeric first
- Angle Between Hands of a Clock
calc the hr degree and min degree, if the angle greater than 180, use 360 - result to get the smaller angle
- Two Sum
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
- Valid Parentheses
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
- Roman to Integer
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 +
122.Best Time to Buy and Sell Stock II
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
14.Longest Common Prefix
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
- Rotate Array
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
- Group Anagrams
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
- Is Subsequence
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)
- Happy Number
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
209.Minimum Size Subarray Sum
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
80.Remove Duplicates from Sorted Array II
2 pointers problem, the trick is we can do at most swap twice
76.Minimum Window Substring
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
- Find Peak Element
find peak element, return index, peak element mean the current element is larger than the next one, it would return any peak, binary search
35.Search Insert Position
classic binary search, l = mid + 1, r = mid - 1, return l
- Gas Station
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
128.Longest Consecutive Sequence
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
- Kth Largest Element in an Array
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
112.Path Sum
since we need to the end of leaf node, we are doing inorder DFS, use recursion. helper function would be helpful too
