coding misc Flashcards
https://leetcode.com/problems/valid-parentheses/
don’t code; review logic
At closing bracket, must check if stack is empty
syntax for PQ that returns coordinate farthest from origin when you poll
PriorityQueue<int[]> maxPQ =
new PriorityQueue<>
(new Comparator<int[]>() {
public int compare(int[] left, int[] right) { return getEuclidDist(right) - getEuclidDist(left); }
});
https://leetcode.com/problems/design-twitter/description/
don’t code; review logic
follows map is { followerId : hash set of followees }
tweets map is ( userId : list of (timestamp, tweetId) )
use MAX pq, sorted by timestamp, when getting news feed
https://leetcode.com/problems/task-scheduler/
code and review logic
use map to get counts of each task, and put the counts in a max pq.
outer loop: while pq is not empty
inner: new cooldown queue each time; for loop for idle time. (add task to cooldown only if its count > 0)
https://leetcode.com/problems/single-threaded-cpu/
code and review logic
sort input array by enqueue time.
min heap, by processing time. each min heap item must also include the index.
start off time at the first enqueue time, and fast-forward instead of incrementing.
instead of while pq is not empty, it is while outputIdx < output.length. inner loop: tasks should be added to pq as long as time is valid.
syntax for converting a map of char counts into a pq
PriorityQueue<Character> pq = new PriorityQueue<>((a, b) ->
Integer.compare(counts.get(b), counts.get(a))); // max heap</Character>
pq.addAll(counts.keySet());
https://leetcode.com/problems/reorganize-string/description/
code and review logic
as i’m filling out the hash map of counts, if any count exceeds len/2, or (len + 1)/2 for odd len, immediately return “”.
very similar to processing tasks w/ cooldown, but instead of having a for loop counting cooldown time, i must write out the processing of 2 consecutive tasks b/c the logic for handling task 1 and task 2 are diff.
must check if pq is empty after polling task 1; if it is, and task 1 still has chars remaining, i must return “”.
https://leetcode.com/problems/longest-happy-string/description/
code and review logic
max heap of CharCounts. must handle case of
if (sb.charAt(sb.length() - 1) == ch && sb.charAt(sb.length() - 2) == ch)
https://leetcode.com/problems/car-pooling/
code and review logic
for loop thru trips array.
first, i get to the position of the new trip. then i drop off all passengers whose end pos is <= curr pos.
then pick up passengers and add new trip to pq. if capacity is exceeded, return false
find median from data stream
don’t code; review logic
- if both heaps are empty, always add to max (smaller half). if num is > max heap peek, add to min; else, add to max
- when finding median, must PEEK, do not poll!
https://leetcode.com/problems/maximum-performance-of-a-team/description/
code and review logic
combine the 2 arrays into 1 Integer array sorted desc by efficiency. min heap based on speed.
as you consider each engineer in each iteration of the loop, polling from the pq must be done BEFORE adding the new speed to the pq
generate parentheses
don’t code; review logic
if (close == 0), add comb to output and return.
if (open > 0), add “(“.
if (close > open), add “)”.
if using sb, must delete last char after each recursive call using sb.setLength(sb.length() - 1) since appending is permanent
https://leetcode.com/problems/daily-temperatures/description/
review while loop
stack of item(temp, idx).
for loop thru temp array.
while stack is not empty and curr temp > stack.peek().temp, pop from stack and edit output arr. after exiting the while loop, add curr temp to stack.
https://leetcode.com/problems/asteroid-collision/description/
just code the while loop
for loop thru input array.
while stack is not empty and prev asteroid is going right and curr asteroid is going left,
compare abs val of the 2 asteroids. do stack.pop() to destroy the prev asteroid and a = 0 to destroy curr asteroid.
after exiting while loop, add a to stack only if it is not 0.
https://leetcode.com/problems/min-stack/description/
don’t code; review logic
just 1 regular stack and 1 min stack.
no need to keep track of min value. if minStack is non-empty, push min(stack.peek(), val); else, just push. when popping, just call pop() on each of the stacks
https://leetcode.com/problems/implement-stack-using-queues/description/
don’t code; review logic
use 1 queue only. all functions are one-liners except push(). for q.size() - 1 times, q.add(q.poll()).
the shifting must be done in push(), not pop(), otherwise top() won’t be implemented correctly.
https://leetcode.com/problems/online-stock-span/description/
don’t code; review logic
each stack item must have span and price
while stack is not empty and price is >= stack.peek().price, span += stack.pop().span
https://leetcode.com/problems/car-fleet/
code and review logic
no need for stack.
combine pos and speed arrays into a single Integer[][] array and sort it by pos in reverse order (bc you want to start w/ the car closest to target).
if you encounter a timeToTarget > TTTofLastFleet add 1 to the number of fleets, and update TTTofLastFleet.
if timeToTarget <= TTTofLastFleet, they would be part of the same fleet.
https://leetcode.com/problems/decode-string/description/
code and review logic
- Stack<StringBuilder> result, from which i get strToRepeat. it must start out with one empty sb</StringBuilder>
- Stack<Integer> kStack</Integer>
- StringBuilder individualK
iterate thru string and handle the 4 cases: digit (use Character.isDigit(ch)), [, ], letter
must result.add(new StringBuilder()) at the beginning (bc there is an imaginary [ at the very beginning) and when you encounter [
https://leetcode.com/problems/remove-k-digits/
code and review logic
since you must remove large numbers in large places, use monotonic non-decreasing stack. same consecutive nums are allowed.
- for loop thru input string. while (k > 0 and stack and digit > stack.peek()), stack.pop()
- take care of remaining k
- get rid of leading 0s by converting stack into string builder (remember to use sb.reverse())
https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/description/
don’t code; review logic
use stack of Item(letter, count).
for loop thru input string. pop from stack once count reaches k.
at the end, use an sb and sb.reverse() to convert stack into a string
https://leetcode.com/problems/simplify-path/
code and review logic
- get tokens by splitting path using / as delimiter
- go thru tokens array. when comparing, use equals(), not ==. if token is .., pop from stack if valid. only add token if it isn’t “..”, “.”, or “”
- return String.join(“/”, stack). this is where absolute path should be handled
https://leetcode.com/problems/132-pattern/description/
code and review logic
each stack item: [num, previousMin]
nums[i] is the 2 of 132. top of stack is 3 of 132.
since we want to maximize 3, we pop from stack while (nums[i] >= stack.peek().num).
after exiting, check if 1 < 2 and 2 < 3.
https://leetcode.com/problems/maximum-frequency-stack/description/
code and review logic
- map of {value : count}
- map of {count : stack of values with that count}
- maxCount variable
remember to update maxCount after popping. if the stack at maxCount is empty, maxCount–;
https://leetcode.com/problems/largest-rectangle-in-histogram/description/
code and review logic
the stack is a stack of indices. when popping off the stack, it is while (stack is not empty and heights[i] <= heights[stack.peek()]). we use <=, not <, bc when we use stack.peek() to calculate the left bound, using < ensures that the building at [stack.peek()] has a height < the building we’re currently considering. in other words, it ensures, the left bound is actually the farthest left we can go.
width = (stack.isEmpty()) ? i : i - stack.peek() - 1;
https://leetcode.com/problems/gas-station/
before doing anything else, return -1 if sum(gas) < sum(cost).
maintain gasRemaining and start. for loop thru indices; if gasRemaining < 0, reset it and set start to i + 1. this works bc we’re guaranteed to have a solution
https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/ or https://leetcode.com/problems/hand-of-straights/ (same)
don’t code; reviw logic
- get map of nums to counts
- make min pq of items
the idea is: at the start of each hand, always get the card with the smallest value. the next card should be val + 1, but if that’s not what pq.peek().val gives, return false
O(n * logn)
https://leetcode.com/problems/valid-parenthesis-string/description/
standard recursion w/ memo. if symbol == ‘*’, res = ___ || ___ || ___.
don’t forget BC
if count < 0, return false
https://leetcode.com/problems/partition-labels/description/
create map {letter : last idx}.
don’t forget edge case of when there is a single partition (just take the entire string)
https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/
start sliding window from leftmost point. the cards OUTSIDE sliding window are the ones you pick.
size of sliding window is actually (len(array) - k + 1) so that you can easily do score -= arr[l] and score += arr[r]
https://leetcode.com/problems/merge-triplets-to-form-target-triplet/
don’t code; review logic
create boolean[ ] found.
go thru all triplets. if any triplet[i] > target[i], continue.
if any triplet[i] == target[i], set found[i] = true
at the end, return whether you’ve found all 3
https://leetcode.com/problems/eliminate-maximum-number-of-monsters/description/
don’t code; review logic
make double[ ] time array of dist/speed. SORT this array.
while min < time[min, min++. return min.
DO NOT forget the condition min < time.length (you may be able to eliminate all monsters)
https://leetcode.com/problems/two-city-scheduling/description/
don’t code; review logic
make differences[ ][3] array of [costB - costA, costA, costB].
SORT that array.
1st half go to city B; 2nd half to city A
https://leetcode.com/problems/contains-duplicate-ii/
sliding window should be a hash set
https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/
maintain sum variable that keeps track of the sum of the current window.
standard sliding window; it is always kept at size k
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
sliding window is a hash set.
https://leetcode.com/problems/longest-repeating-character-replacement/
keep counts[] array of the counts of all the letters currenly in the window. keep a highestCount variable; it only needs to be updated when a letter count is incremented
https://leetcode.com/problems/frequency-of-the-most-frequent-element/description/
SORT and sliding window. keep track of windowSum.
while (we don’t have enough increments to make everything in the window equal to nums[r]), l++
https://leetcode.com/problems/minimum-size-subarray-sum/description/
sliding window, keep track of windowSum.
while (windowSum >= target), recalculate minLen and l++
what’s different about this problem is that the recalculation of the result is done INSIDE the while loop.
https://leetcode.com/problems/find-k-closest-elements/description/
O(logn + k).
- binary search to find idx of target, or idx of the element closest to target. this is contained in r.
- l = r, r++. while (k > 0), shift l and r so that they are the exclusive boundaries of the window containing the k closest elements. exclusive boundaries means that the invalidity conditions are r==arr.length and l==-1
https://leetcode.com/problems/permutation-in-string/description/
counts1[ ] and counts2[ ], each of size 26.
- go thru window 1, [0, len1). update each map.
- do the only O(26) operation in this algorithm – run through both arrays and keep track of the number of matches. if at the end matches==26, return true.
- start at window 2, [len1, len2). do all calculations for right char and left char (left char will be the char just moved out of the window, s2.charAt(l - 1) )
https://leetcode.com/problems/minimum-window-substring/description/
- get counts of chars in target string in a hash map.
- start L and R ptrs at 0. iterate thru entire string, using R ptr. update counts and num of matches for right letter. then, while matches==map.size(),
- update result
- update counts and num of matches for left letter
- move left letter
https://leetcode.com/problems/sliding-window-maximum/description/
use a deque of indices. monotonic strictly decreasing - the leftmost value in the q is always the greatest
If you go w/ the easy soln, it’s O(k * (n - k))
https://leetcode.com/problems/minimum-difference-between-highest-and-lowest-of-k-scores/description/
don’t code; review logic
.
https://leetcode.com/problems/merge-sorted-array/description/
code and review logic
start from END of arrays
https://leetcode.com/problems/move-zeroes/
code and review logic
start L ptr at idx 0; for loop using r.
move all nonzero elements to the start – that’s the same as moving all zeroes to the end.
whenever nums[r] is nonzero, swap it w/ L idx
https://leetcode.com/problems/range-sum-query-immutable/description/
don’t code; review logic
know to use prefix sums array
https://leetcode.com/problems/design-hashmap/description/
don’t code, review logic
define ListNode class w/ key, val, next.
map is an array of ListNodes.
get the idx in the array using key % (num of operations)
resolve the issue of collisions using chaining
https://leetcode.com/problems/valid-sudoku/description/
don’t code; review logic
Map<Integer, Set<Character>> for rows, cols. same for sub-boxes but use a String for the key (i/3 + "-" + j/3)</Character>
remember to continue if we’re at a ‘.’
https://leetcode.com/problems/product-of-array-except-self/description/
2 helper arrays: right products and left products.
right[i] = product of all elements to the right of i. left[i] = product of all elements to the left of i. res[i] = right[i] * left[i].
but you can do it w/o any extra space by maintaining a product variable w/ value initialized to 1.
https://www.algoexpert.io/questions/two-colorable
don’t code; review logic
have colors[] array to store colors.
dfs helper with all the standard parameters, + int prevNode. (when calling dfs from the main function, prevNode should be -1)
https://leetcode.com/problems/implement-trie-prefix-tree/description/
don’t code; review logic
Map<Character, Trie> children;
instead of using endSymbol, just use boolean endOfWord.
instead of initializing curr to root, it should be
Trie curr = this;
https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/
scanningIdx and placementIdx both start at 1. whenever we encounter nums[p] > nums[p - 1], place that num at the scanningIdx
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
l, r ptrs both start at 0. (for loop thru r).
while valid index and num is a duplicate, r++ and count++.
then, for min(2, count) times, insert the num at nums[l++].
