Algo Solution Approaches

Question 1

Make Array Zero by Subtracting Equal Amounts

Answer 1

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

Question 2

Copy list with random pointer

Answer 2

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

Question 3

Reorganize string

Answer 3

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

Question 4

Word Break II

Answer 4

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)

Question 5

All nodes K distance in binary tree

Answer 5

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

Question 6

Rotting oranges

Answer 6

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

Question 7

Integer to English Words

Answer 7

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()

Question 8

LRU Cache

Answer 8

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

Question 9

Max Robots within budget

Answer 9

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

Question 10

Find triangular sum of array

Answer 10

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

Question 11

Valid Palindrome (Meta)

Answer 11

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.

Question 12

Merge Sorted Arrays (Meta)

Answer 12

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.

Question 13

Valid Palindrome II (Meta)

Answer 13

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

Question 14

Two Sum (Meta)

Answer 14

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.

Question 15

Diameter of a Binary Tree (Meta)

Answer 15

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

Question 16

Range Sum of BST (Meta)

Answer 16

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.

Question 17

Valid Word Abbreviation (Meta)

Answer 17

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.

Question 18

Minimum Remove to Make Valid Parentheses (Meta)

Answer 18

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. “

Question 19

Binary Tree Vertical Order Traversal (Meta)

Answer 19

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.

Question 20

Basic Calculator II (Meta)

Answer 20

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 ‘/’”

Question 21

Kth Largest Element in an Array (Meta)

Answer 21

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]

Question 22

Lowest Common Ancestor of a Binary Tree (Meta)

Answer 22

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.

Question 23

Lowest Common Ancestor of a Binary Tree III (Meta)

Answer 23

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.

Question 24

Random Pick with Weight (Meta, Google)

Answer 24

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

Question 25

Find Peak Element (Meta)

Answer 25

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.

Question 26

Subarray Sum Equals K (Meta)

Answer 26

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

Question 27

Nested List Weight Sum (Meta)

Answer 27

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. "

Question 28

Pow(x, n) (Meta)

Answer 28

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. "

Question 29

Top K Frequent Element

Answer 29

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)"

Question 30

Simplify Path

Answer 30

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('/')

Question 31

Dot Product of Two Sparse Vectors

Answer 31

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"""

Question 32

Binary Tree Right Side View

Answer 32

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. "

Question 33

Interval List Intersections

Answer 33

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

Question 34

Merge Intervals

Answer 34

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. "

Question 35

Shortest Path in Binary Matrix

Answer 35

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"

Question 36

Sum Root to Leaf Numbers

Answer 36

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.

Question 37

Copy List with Random Pointer

Answer 37

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.

Question 38

K Closest Points to Origin

Answer 38

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!!!

Question 39

Next Permutation

Answer 39

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.

Question 40

Buildings with an Ocean View

Answer 40

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. "

Question 41

LRU Cache

Answer 41

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"

Question 42

Subsets

Answer 42

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

Question 43

Rotate Array

Answer 43

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"

Question 44

Rotate Image

Answer 44

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. "

Question 45

Moving Average From Data Stream (Meta)

Answer 45

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

Question 46

Remove All Adjacent Duplicates in String (Meta)

Answer 46

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

Question 47

Find Kth Missing Positive Number (Meta)

Answer 47

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"

Question 48

Palindrome Number (Meta)

Answer 48

Iterative O(n) Just reverse the number by building digits and compare original number to reversed number

Question 49

Can Place Flowers (Meta)

Answer 49

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

Question 50

Populate Next Right Pointers in Each Node (Meta)

Answer 50

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

Question 51

Palindrome Linked List (Meta)

Answer 51

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

Question 52

Accounts Merge (Meta)

Answer 52

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"

Question 53

Basic Calculator (Amazon, Google)

Answer 53

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

Question 54

Longest Substring without Repeating Characters (Meta)

Answer 54

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;

Question 55

Minimum Add to Make Valid Parens (Meta)

Answer 55

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

Question 56

First and Last Position of Element in Sorted Array (Meta)

Answer 56

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

Question 57

Custom Sort String (Meta)

Answer 57

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

Question 58

All Nodes Distance K in Binary Tree (Meta)

Answer 58

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]

Question 59

Longest Palindromic Substring (Meta)

Answer 59

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

Question 60

Remove Nth Node from End of List (Meta)

Answer 60

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

Question 61

Merge K Sorted Lists (Meta)

Answer 61

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

Question 62

Minimum Window Substring (Meta)

Answer 62

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. "

Question 63

Word Break (Meta)

Answer 63

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