Algo Solution Approaches Flashcards
Make Array Zero by Subtracting Equal Amounts
Count number of distinct non zero values and return that number since each operation removes the current smallest positive element from all.
let set = new Set(nums)
return set.has(0) ? set.size - 1 : set.size
Copy list with random pointer
Use hashmap to map original nodes to new nodes in first pass, then set next and random pointers on second pass.
while (current)
nodeMap.get(current).next = nodeMap.get(current.next) || null
nodeMap.get(current).random = nodeMap.get(current.random) || null
Reorganize string
Count character frequencies. If any character freq exceeds (n+1)/2 then return “” because not possible.
maxCount = Math.max(…freq.values()
if (maxCount > Math.ceil(s.length / 2) return “”
Push all [character, count] into heap (heapify up after each one) then while the heap has elements pop off two at a time, push both in result, then if freq - 1 is more than 0, push them back on the heap [character, count - 1)
When one char left, push to result, return result.join
Word Break II
Use backtracking and memoization/DP.
Iterate over string and when prefix matched a dictionary word recursively process the remainder and cache results.
Memo is Map() and also keep a word Set()
DFS method takes index. Base case is when index === string length return empty string. Second base case when memo has the index as a key return that value.
Otherwise initialize result array. For loop from start idx + 1 and go for length of string. Prefix variable is s.slice(start, end). If word set has that prefix then make a suffixes variable = to recursive call passing in end idx. Loop through suffixes and push to results
results.push(suffix === “” ? prefix : prefix + “ “ + suffix)
Outside of loop memo.set(start idx, results)
Return results
Outside dfs return dfs(0)
All nodes K distance in binary tree
Find target node and create parent map (map that store parents for each node) {node: parent}
const buildParentMap = (node, parent, map) => if !node return
if parent != null map.set(node, parent)
//recursive call
buildParentMap(node.left, parent, map)
buildParentMap(node.right, parent, map)
Preorder traversal
Set distance variable, queue = [target], visited set()
While queue length. If distance === k return queue.map(node => node.val (each new level is one more distance, so each loop adds one)
Set queue size and iterate through. Shift off a node and push children to visited and queue, if parent from parent map isn’t in visited, add to visited and queue. Increment distance
Rotting oranges
Multi source BFS on each rotten orange. Keep track of time and fresh as we spread rotten.
so make directions and queue, count time and number of fresh oranges. Nested loop through grid increment fresh for 1s and push rotten to queue with 2s
While fresh exist and queue has elements, set queue size and iterate through. Pop off a square [row, col] then iterate through directions and get new row and new col. if that square is 1 (fresh) then push to queue, set it to 2, decrement fresh. Outside of the for loop, increment time before next queue loop.
Return fresh === 0 ? time : -1
Integer to English Words
String formatting / divide and conquer. Keep an array of words and then break up n by groups of three
<20 [“”, “one”, “two”…”nineteen”
10s [“”, “”, “twenty”, “thirty”…”ninety”
thousands [“”, “thousand”, “million”, “billion”
Helper function with long if/else (if n < 20 do index of <20 list, if n < 100 do 10s[Math.floor n/10 + “ “ + helper(n%10), else below20[math floor n/100 + “Hundred” + helper(n%100)
Under helper function i = 0, while num>0 if num%1000 != 0 res = heloer(num%1000 + thousands[i] + “ “ + res
Num = math floor num/1000
i++
Return res.trim()
LRU Cache
See other card for Map() version. In doubly linked list version it’s the same except we use linked list methods to add and remove nodes
Max Robots within budget
Sliding window + monotonic queue (orders elements ascending or non). Use prefix sum to make prefix sum array from running costs. Then use sliding window to calculate the cost of the whole array.
First keep track of longest charge time in the window with the monotonic queue and a while loop (so only the longest charge time stays in the queue at any given time)
Set k/window size to r-l+1
Total running cost is prefix formula prefix[r+1] - prefix[l]
Cost = charge time (dequeue[0]) + k * total running
While cost > budget
If dequeue[0] < left then shift
Left++
Recalculate window size, total running cost, and cost
Still in for loop res= math max of res, left - right + 1
Outside loop return res
Find triangular sum of array
Basically while loop through creating new and smaller arrays. Can use for loop, map, or reduce
while array length > 1
newArr = []
For loop
newArr.push(arr [i] + arr[i +1])
arr = newArr
OR
arr = arr.slice(1).map((val, i) => (val + arr[i]) % 10) this removes the first element from the array each loop
OR
arr = arr.reduce((newArr, cur, i, a) => {
If i < a.length
newArr.push((cur + a[i+1]) % 10)
Return newArr }, [])
THEN return arr[0] last element
Valid Palindrome (Meta)
Two Pointers O(n), O(1)
Need to remove nonalphanumeric characters with regex (/[a-zA-Z0-9]/g) or isLetterOrDigit() method that checks character codes, then move pointers from outside to center returning false if they don’t match. Return true after they all match.
Merge Sorted Arrays (Meta)
Three Pointers O(m + n), O(1)
Three pointers at last nonzero digit of nums1, last digit of nums2, and last index of nums1. Go backward in for loop, using i the last pointer, make sure second pointer is in range then regular comparison of merge sort.
Valid Palindrome II (Meta)
Two pointers O(n), O(1)
Make a regular isPalindrome helper function. Then outside the helper, initialize two pointers and move inward (just like in helper), but when there is a mismatch, check both options (removing the element at l or the one around r) by invoking the helper function. Can also probably do recursively
Two Sum (Meta)
Cache / Hash O(n), O(n)
Create a cache to keep the numbers already seen and their indices. With each number, check if the cache has the difference of that number and the target. If so, just return the value of that entry in the cache, along with the current index i. If not, add that number to the cache as the key with it’s index as the value.
Diameter of a Binary Tree (Meta)
Post order DFS O(n) or O(log(n)), O(n)
Make a dfs helper that takes in root. No root is base case to return zero. Go in PostOrder, so recursively call left, then recursively call right, then see if left + right is greater or less than current result. Return from helper 1 + the max of left and right (because it’s the current longest path). Invoke helper with root, return res
Range Sum of BST (Meta)
Tree DFS Recursive or iterative O(n), O(n)
Can do dfs recursively or iteratively with a stack. Order doesn’t matter for this one. While the root has value or the stack has elements, you’ll see if the current node value is in between the low and high and if so add it to sum. Then for the left child you can call it recursively or push to stack if the val is of the current node is greater than low (if it’s not you know the left child will be even less). Then same for the right child.
Valid Word Abbreviation (Meta)
Two Pointers O(n + m), O(1)
Two pointers to traverse the word and abbr. While loop as long as both are less than word/abbr respectively. Check if the abbr char is a number or not with isNaN(). if it’s not a number check if it matches the corresponding word char. If not return false. If yes, increment both pointers. If the char was a number, then we check if it’s ‘0’. If so return false. If not, do while loop as long as current abbr char is a number. Add together by num = num * 10 + (parseInt(abbr[j])). Move the word pointer by num spaces. If the new pointer is longer than word length return false. If not, continue in while loop. Return true if both pointers === word and abbr lengths respectively.
Minimum Remove to Make Valid Parentheses (Meta)
Stack O(n), O(n)
“This solution needs two passes: one to validate parens and identify which need to be removed, and another to build a new string without the invalid parens. Will usually need two passes if the operation on one element depends on later elements. Do regular validation with stack, except add index instead of “”(“”. On closing paren, if stack has length, pop off, if not, add current i to a Set of indices to remove. After first pass, add the remaining indices in the stack to the Set. In second pass add characters to a new array if the Set doesn’t have their index. Join the array to a string and return. “
Binary Tree Vertical Order Traversal (Meta)
BFS / Queue O(n), O(n)
We need to traverse the BST level by level, so this is BFS with a queue. Create queue to add nodes to, and a map to match columns with values. Add each [col, node] to the queue, starting with [0, root]. For each [col, node] pair, add the col to map as a key with value of [], then push node.val to the array. Then if there is a left node, add it to queue with col - 1, if there is a right node, add it to queue, with col + 1. Use the map to make a results array in order of the map keys with the values as the result array elements.
OPTIMIZE: by using an i pointer and while (i < queue.length) instead of while (queue.length) we can avoid using the shift method. By keeping track of a minCol and maxCol and updating with each new loop we can then loop from minCol-maxCol in a for loop instead of sorting the map keys.
Basic Calculator II (Meta)
Stack O(n), O(n)
“Create a stack and a lastOperator variable set to ‘+’. Start iterating through the string, skipping whitespace. When an integer is evaluated then act based on the lastOperator. ‘+’ push to stack, ‘-‘ push negative to stack, ‘*’ pop off stack and multiply to num then push result back on stack, ‘/’ pop off stack and divide by num then push Math.trunc result back on stack. If it’s not white space or an integer, it’s an operator so set lastOperator variable. After the whole string is evaluated, sum up numbers in stack and return sum.
OPTIMIZE: can optimize space by not using a stack and instead keeping track of currentNum and lastNum, adding lastNum to a result for ‘+’ and ‘-‘, and operating on lastNum for ‘*’ and ‘/’”
Kth Largest Element in an Array (Meta)
Min Heap O(n log k), O(k)
Implement a min heap with array. Create heapifyUp and heapifyDown helper functions. Iterate through array. If min heap length is less than k, just push to heap and heapifyUp. If heap already has k elements, check if the current number is greater than minHeap[0]. If it is, replace minHeap[0] with num and heapifyDown. At the end of the loop return minHeap[0]
Lowest Common Ancestor of a Binary Tree (Meta)
Post order DFS O(n), O(n)
This one is a bit harder than for BST. We can’t automatically determine whether to go left or right so we need to keep the evaluated result of the recursive calls in left and right variables. We don’t actually need to find each node. We know they are both in the tree, so we just need to find one of them. If just one of the left or right is not null, that is the LCA so we return it. If both the left and right calls have values then that means they were found on either side of the root, so the current root is LCA.
Lowest Common Ancestor of a Binary Tree III (Meta)
Two Pointers O(n), O(n)
Since we have parents for this one, we can start at the two nodes and work up, this makes it easier. No need to do DFS, we can just set a pointer a to the p input and a pointer b to the q input. Then while they are not equal we just keep moving them up by setting the pointer to it’s parent, or if the parent is null, to the other pointers starting point (p or q). Eventually they will meet at the LCA and break the loop.
Random Pick with Weight (Meta, Google)
Prefix Sum O(log n), O(n)
For optimal use a prefix sum array for weights (no zeroth element extra) and then pick a random index between 0 and the sum of weights. Then use a binary search to find that index of the weights
Find Peak Element (Meta)
Divide and Conquer / Binary O(log n), O(1)
Needs to be O(log n) so binary is obvious approach. Since out of bounds counts as lower, we can divide by always going to the side that with a higher number than mid. If both have a number higher than mid, either will do. While the start < end you just keep doing that check. After the loop, you return start though, because it will be equal to end. Mid could be off by 1, not everytime but sometimes.
Subarray Sum Equals K (Meta)
Prefix Sum / Hash O(n), O(n)
This one can be optimized by using a prefix sum map with prefixSum as key and times we’ve seen it as value. It works similar to two sum. Initialize a running sum, a count = 0, and a new map with the first prefix sum entry map.set(0, 1). Then loop through, add current element to prefixSum. Then check if the difference (prefixSum - k) is in the map. If so, add the value of. that entry (number of times seen) to current count variable. After that, check if the prefixSum itself (not the difference) exists in the map. If so, increment it’s count/value. If not add it with a value of 1. Return count
Nested List Weight Sum (Meta)
DFS recursion or stack O(n), O(n)
“This one is DFS. Easy to solve recursively. Just have a helper function that initializes and returns a sum. Iterate through the array and add numbers * depth to sum or if the element is a nested array add the evaluated result to sum.
BUT this can be optimized iteratively using a stack. Just map the input list to a stack (nestedList.map(el => ({element: el, depth: 1}) then iterate WHILE stack has length. Each loop pop off the stack, and if integer add int * depth to sum, if nested list then loop through the nested list and push each element (int or nested list) onto the stack with depth + 1. Return sum outside of loop.
Recursive version uses the call stack to keep track of depth which can lead to stack overflow. Iterative uses it’s own stack. Recursive calls store more variables and meta data than iterative. Iterative is easier for JS engines because recursive calls involve function set up and teardown for each call. “
Pow(x, n) (Meta)
Divide and Conquer / Binary O(log n), O(log n)
“This one is easy to solve by just initializing a result variable to 1 and looping up to n from 0 and multiplying the result by x over and over. Keep track of negative and if it is, then return 1/res instead of just res.
BUT that isn’t optimal and will break with very large numbers. For O(log n) we need to divide and conquer, meaning we halve n every loop. If n is odd we multiply res by x, first. This handles the odd contribution by itself. After that conditional we square x and half n. “
Top K Frequent Element
Cache / Min Heap / Bucket Sort O(n log n), O(n)
“Simplest solution is to create a cache with the freq of each. Then use Object.values with sort (b - a) and slice (0, k) to get the topK appearances. For in loop (let key in cache) and if the topK array includes the value, push the key to an output array (don’t forget to cast as Number).
For slightly optimized time, but worse space, use a minHeap. Still do the cache, but then loop through Object.entries and add [num, freq] to heap. Then loop up to k and push the nums onto output array. O(n log k), O(n + k)
For most optimized use Bucket Sort. O(n), O(n)”
Simplify Path
Stack O(n), O(n)
Easy. Just split the path on ‘/’ then loop through the resulting array. If the element is ‘’ or ‘.’ then continue. If the element is ‘..’ the pop off the stack. Else push the element onto the stack. At the end, return ‘/’ + stack.join(‘/’)
Dot Product of Two Sparse Vectors
Iterative or 2 pointers
O(n), O(n) -or- O(k1 + k2), O(k1 + k2)
“One Pass: iterate from 0 to the length of nums/vec. if either is zero, skip, otherwise add the product of the two to a running dotProduct sum.
Two Pointers Compact Optimization: on construction reduce the nums array to an array of non zero elements and their indexes (can use reduce method). Do a while loop as long as both pointers are less than length of respective arrays. If they are same index, multiply and add to sum. If not, increment the lesser of the two until they match. This one may be better if vectors are reused a lot or are especially sparse
"”The one-pass version uses a simple linear iteration pattern. It processes both vectors simultaneously, multiplying their elements only when neither is zero. This avoids unnecessary operations but still requires visiting all indices, making it O(n) in time complexity. While efficient for a one-time computation, it doesn’t take advantage of sparsity as effectively as the compact two-pointer approach which would be O(k1 + k2) where k1 and k2 are the non zero elements in each vector”””
Binary Tree Right Side View
BFS Q / DFS recursion or stack
O(h), O(n) or
O(n), O(n)
“For BFS create a res array and a queue with the root. While queue has elements get the current queue size and iterate in for loop that many times. Shift off the node and if i == levelSize - 1 that means we’re on the last/rightmost node of that level so push the node to the res array. If not null, add left and right nodes to the queue in that order because the last element in the queue for each level is the right side (levelSize -1 )
For DFS create a res array and a dfs helper that takes in node and depth. The helper then checks the depth against the res length and if they are equal it means that level hasn’t been processed yet and we add either the right node or if it’s null the left node by calling dfs recursively with those and depth + 1. Outside the helper invoke it with (root, 0) and return res. “
Interval List Intersections
Two Pointers O(n + m), O(n)
Easy problem. Initialize 2 points for each array. While both are less than respective length, check if the max of the two starts is <= to the min of both ends. If so, that max and min point is your overlap to push to the output array. After adding overlap to the output array or determining there is no overlap increment the pointer with the smaller endpoint, if they are equal increment both
Merge Intervals
Iterative O(n log n)), O(n)
“Pretty easy one. First need to sort the array by the interval start points (index 0 of interval subarray). Have a lastInterval variable and set it to the first interval. Once sorted just iterate through. Check if the last interval overlaps with this one (is lastInterval end >= current interval start). If so then update the lastInterval endpoint to the max of lastInterval and current interval end. Sometimes the current interval is completely ““inside”” the last one, that’s why we need the max. If they don’t overlap then push lastInterval to the output array and set lastInterval to the current interval. At the end push the remaining lastInterval to the output array and return it. “
Shortest Path in Binary Matrix
BFS Q O(n), O(n)
“This is a tougher one. BFS allows us to traverse the grid level by level and explore each possible path. Check edge cases to make sure grid has values, and start and end coordinates aren’t a 1. Add all 8 directions to an array. Initialize a queue with the first coordinates and a length of 1, and a visited set with the first coordinates as a string. Then an i variable to keep track of index so we don’t have to shift off. Get current location and if is bottom right then return the length associated with it. If not loop through the directions. If out of bounds or a 1 then we continue. If a zero and it’s visited we continue. If it’s a zero and not visited we add it to visited and push that next square coordinates as a string to visited. After all direction inrement i. If while loop finishes without returning then we’ve explored all paths and can’t reach the end so we return -1.
For optimization, there are several things we can try: String concatenation for visited set keys is expensive. We could use a different format like ${x}-${y} (one concatenation instead of two) or even better, we could encode the position as a single number like x * grid.length + y. Instead of using a Set, we could modify the grid itself to mark visited cells (set them to 1) since we don’t need to preserve the original grid. We could avoid using objects in the queue and just store arrays like [x, y, length]. Instead of checking bounds for each direction separately, we could combine some checks”
Sum Root to Leaf Numbers
Tree DFS O(n), O(n)
Easy one. Initialize an array to keep tabs of the numbers of each path. Make a dfs helper that takes in a node and a current number that we’re buillding. In the helper function, first add the current value as an additional digit on the number we’re building. Then BASE CASE: if the node has neither left or right children then we are at a leaf and push num to the outer array. If there is still at least one node we continue dfs on that side or both sides. That’s the whole helper so invoke it with (root, 0) and return the sum of that array.
Copy List with Random Pointer
Linked List / Iterative
O(n), O(n)
Initialize a new hash map to map original node to new node. Set a current = head variable. TWO PASSES. First pass while current create a new node and store the original and the new one in the hash map then current = current.next. Go back to beginning by resetting current to head. Second pass get the value of current node in the node map (this will be the copied node) and set it’s next value and random pointers to the values associated with the original next and random nodes. nodeMap.get(current).next = nodeMap.get(current.next || null). Return nodeMap.get(head) which will be the copied head.
K Closest Points to Origin
Max Heap O(n log k), O(k)
Use a Max Heap / array. Do the heapify up and heapify down methods. Make a helper to calculate distance (Math.pow(x, 2) + Math.pow(y, 2)). Iterate through the points and calculate distance. Add distances and points to the heap and heapify up until it’s full, then start replacing root (Max distance) with any distance that is smaller than it and heapify down. Return only the points heap.map(x => x[1] because every heap entry is [distance, [x, y]]
Be prepared to discuss trade offs with BinarySort or QuickSelect solution which is O(n) avg, BUT O(n^2) in worst case!!!
Next Permutation
Iterative O(n + m), O(n)
Brute Force: generate and sort all permutations, iterate to the input and return permutation of next index. Way too much time
Optimal: Find pivot/break point by iterating from the end (nums.length - 2) and the first arr[i] < a[i + 1] and save idx in variable because that is the pivote point. If there is no pivote point return array reversed. If there is, iterate backward again and find the first number (from the end) that is greater than that pivot and swap that one with the pivot. After the swap just reverse the subarray in place from the pivot index to the end by using a while loop with start being the element after the pivot and end being end of array. Just keep swapping those and moving start and end closer together.
Buildings with an Ocean View
Two pointers or stack O(n), O(n)
“Easy peasy, just set a result array variable and a maxHeight variable. Iterate from right to left. If the current element is greater than the maxHeight add it to the result array and set maxLeft to that height. Return the result array reversed.
If you had to check both sides the result array would be an array of subarrays with booleans for left and right ([[true, false], [true, false], [false, true]] etc. Use two pointers on either end and move both completely to the other end. From the right check against a maxRight value, from the left check against a maxLeft value. “
LRU Cache
Hash map / cache O(1), O(1)
“Pretty easy. Cache needs capacity and cache (new Map) properties. For get method, if the cache has the key, get it’s value and set to a variable, then delete the key, then reset it in the cache, then return the value. For put method, if cache has the key, delete it, else if the cache is at capacity delete the least recently used. Outside of those conditional statements add the key and value. To get least recent:
let iterator = this.cache.keys();
let leastRecent = iterator.next().value;
Without the Map class need to use an object with doubly linked list. Use a regular object for key-value storage and a doubly linked list to maintain access order. The list tracks the most recently used (MRU) at the head and the least recently used (LRU) at the tail. On get or put, move accessed nodes to the head. If capacity is exceeded, evict the tail node. Keep a nodes object {} to map the keys to the node in the linked list for O(1) access”
Subsets
DFS / Backtracking / Decision Tree
O(n*2^n), O(n)
Brute Force: Can’t really optimize this one beyond brute force. Backtracking with DFS works well. Keep a result array and subset array, then make a helper that takes in idx. Base Case: if idx has reached end of nums, push the current subset elements to result (result.push([…subset])) and return. Recursive Logic: do a decision tree by pushing nums[i] onto subset and invoking dfs(i + 1), then popping off nums and invoking dfs(i + 1). Basically each time you’re doing the recursive call with the current element and without the current element
Rotate Array
Iterative
“(i + 2) % array.length
Optimal way is to reverse the array, then reverse back idx 0 to idx k - 1, then reverse back idx k to idx length - 1”
Rotate Image
O(n^2), O(1)
“Reverse and transpose by reversing the matrix, then nested loop of row and col to switch matrix[i][j] with matrix[j][i] and vice versa. Easier.
Other way is to rotate in place one corner at a time for each square. While loop for l < r. Then inner for loop as long as i < r - l. Get top(l) and bottom(r) variables. Save top left in variable. Move bottom left to top left, move bottom right to bottom left, move top right to bottom right, move top left variable to top right. “
Moving Average From Data Stream (Meta)
Queue O(1) for Next(), O(size)
MovingAverage constructor needs size, queue, sum. For next() method, if queue length == size then shift off the queue, if not do nothing. Then push new val to q, add new val to the sum, return sum / q.length
Remove All Adjacent Duplicates in String (Meta)
Stack O(n), O(n)
Create a stack. Iterate string. If the current character === the last character of stack then pop off stack, if not push to stack. At the end return stack.join
Find Kth Missing Positive Number (Meta)
Iterative or Binary Search
O(n), O(1)
O(log n), O(1)
“Brute Force: Keep idx variable to iterate, currentNumber to keep track of what number should be in a specific place, and missingCount to know when we’re at the kth missing number. Iterate while missingCount < k (because kth number could be outside bounds of array). If currentNum matches arr[i] then increment i. If not increment missingCount. Either way check missingCount against k then increment currentNum.
Optimal: use binary search. Basically get mid idx, then get the number of missing at that point by subtracting (mid idx + 1) from the element at mid idx. If missing is less than K move left pointer to mid, otherwise move right pointer to mid. At the end of the loop the left pointer will be at the position that the kth element should be at”
Palindrome Number (Meta)
Iterative O(n)
Just reverse the number by building digits and compare original number to reversed number
Can Place Flowers (Meta)
Iterative O(n), O(1)
Just iterate through the flowerbed. Check the current element is zero and that the ones on either side are zero or out of bounds. Decrement n and change 0 to 1 every time conditions are met. Check if n == 0 every loop and after the loop
Populate Next Right Pointers in Each Node (Meta)
BFS Queue O(n), O(1)
Make a q and add root. Need to do inner levelSize loop to process nodes and add to queue. Basically get levelSize from q.length - i, make for loop, then current is q[i]. If j < the levelSize then there are still nodes to the right andyou can set next pointer. Then if one of the children exists both do so add both to the q. Return root
Palindrome Linked List (Meta)
Two Pass or Stack
Make 2 passes. The first one push every value onto stack. The second compare every value with the stack pop
Or fast and slow pointers, reverse second half of list and the compare node by node with first half
Accounts Merge (Meta)
Union Find or Graph
“First need to implement a UnionFind class with parent array and rank array, find method, and union method.
Next map emails to a unique id in one map and emails to name in another. Then instantiate a new union find. Go through all accounts again and get a anchor email/id for each account and union it with every other email in the account.
Then iterate emailToId map and find the root and add it to a new Map rootToEmails with the array of emails associated with that root as the value.
Finally iterate through that new rootToEmails map and sort each array of emails the push to output with the email account name as the first element”
Basic Calculator (Amazon, Google)
Stack
Like Basic Calculator II except you need to push a levelStack of the current level and last operator onto the stack each ‘(‘. For each ‘)’ sum up the current levelStack, pop off the previous [stack, lastOperator] and push sum or -sum to that stack and make it the new current levelStack
Longest Substring without Repeating Characters (Meta)
Sliding Window and Map
Use a map to keep track of last idx we saw each character at. Have l and r start at 0. Move r until we see a character that is in map already. At that point move l to the max index between l and the idx after that character in the map. Set the new r character in the map. Check the maxLength against r - l + 1;
Minimum Add to Make Valid Parens (Meta)
Stack
Pretty much exactly the same as regular parens, but you push orphan closing parens to stack and only pop opening parens. Return stack length
First and Last Position of Element in Sorted Array (Meta)
Modified Binary Search
Need to do binary search twice, once for first appearance and once for last appearance. Just do a binary search helper that returns the idx (initially set to -1). Main difference is to keep a flag to show if searching left or right. Then if mid = target, you set idx to mid, but still move the pointers as you would if it didn’t match
Custom Sort String (Meta)
Hash Map
4 passes: populate map with order, update map with s char count, add char in common in order to custom arr, add remaining s characters to arr, return arr.join
All Nodes Distance K in Binary Tree (Meta)
DFS + BFS
Since there is no parent property on the nodes, we need to first do dfs to map to the parents. After that we start bfs from the target node, complete with queue and visited set. Instead of just adding children to queue, also add the parents. Queue elements are [node, distance]
Longest Palindromic Substring (Meta)
Two Pointers
Create expand helper that expands pointers outward for as long as they match. Then for each character, pass in i and i or i and i + 1
Remove Nth Node from End of List (Meta)
Two Pointers
Do two solutions: by counting length of list, subtracting n from length, then start over and go that many nodes and delete. Other way is two pointers that are n nodes apart, using a res head AND a dummy head (res head is new node and dummy is res that moves while res stays in place). Remove node from dummy and return res.next
Merge K Sorted Lists (Meta)
Min Heap
Keep a k size minheap with the root from each list. Then create a dummy head and keep adding the root of the min heap to it then heapify each time. When building the new list, order is very important: save heap root as min and min.next as next, remove min from heap by assigning root to last leaf then pop then heapify down, if next push next to heap and heapify up, set min next to null and cur next to min and cur to cur next. Return dummy.next
Minimum Window Substring (Meta)
Sliding Window and Maps
“Make two maps: one for letters in T and how many times they appear. One for letters in the window and how many times they appear. Need variable with count from TMap, Have variable for count of WinMap.
Left and right pointers. Move right pointer until have and need are equal (each character in winmap is >= each char in TMap). If equal check length of substring and replace if smaller than existing. Then move left pointer until have and need are no longer equal. Then start moving right again until they are. “
Word Break (Meta)
Trie
Do Trie, then take logic for iterating through string down trie and put it in a while loop with queue so we can bfs, basically running the logic of checking the trie starting at every element of s
