coding misc

Question 1

https://leetcode.com/problems/valid-parentheses/

don’t code; review logic

Answer 1

At closing bracket, must check if stack is empty

Question 2

syntax for PQ that returns coordinate farthest from origin when you poll

Answer 2

PriorityQueue<int[]> maxPQ =
new PriorityQueue<>
(new Comparator<int[]>() {
public int compare(int[] left, int[] right) { return getEuclidDist(right) - getEuclidDist(left); }
});

Question 3

https://leetcode.com/problems/design-twitter/description/

don’t code; review logic

Answer 3

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

Question 4

https://leetcode.com/problems/task-scheduler/

code and review logic

Answer 4

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)

Question 5

https://leetcode.com/problems/single-threaded-cpu/

code and review logic

Answer 5

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.

Question 6

syntax for converting a map of char counts into a pq

Answer 6

PriorityQueue<Character> pq = new PriorityQueue<>((a, b) ->
Integer.compare(counts.get(b), counts.get(a))); // max heap</Character>

pq.addAll(counts.keySet());

Question 7

https://leetcode.com/problems/reorganize-string/description/

code and review logic

Answer 7

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

Question 8

https://leetcode.com/problems/longest-happy-string/description/

code and review logic

Answer 8

max heap of CharCounts. must handle case of

if (sb.charAt(sb.length() - 1) == ch && sb.charAt(sb.length() - 2) == ch)

Question 9

https://leetcode.com/problems/car-pooling/

code and review logic

Answer 9

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

Question 10

find median from data stream

don’t code; review logic

Answer 10

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

Question 11

https://leetcode.com/problems/maximum-performance-of-a-team/description/

code and review logic

Answer 11

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

Question 12

generate parentheses

don’t code; review logic

Answer 12

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

Question 13

https://leetcode.com/problems/daily-temperatures/description/

review while loop

Answer 13

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.

Question 14

https://leetcode.com/problems/asteroid-collision/description/

just code the while loop

Answer 14

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.

Question 15

https://leetcode.com/problems/min-stack/description/

don’t code; review logic

Answer 15

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

Question 16

https://leetcode.com/problems/implement-stack-using-queues/description/

don’t code; review logic

Answer 16

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.

Question 17

https://leetcode.com/problems/online-stock-span/description/

don’t code; review logic

Answer 17

each stack item must have span and price

while stack is not empty and price is >= stack.peek().price, span += stack.pop().span

Question 18

https://leetcode.com/problems/car-fleet/

code and review logic

Answer 18

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.

Question 19

https://leetcode.com/problems/decode-string/description/

code and review logic

Answer 19

1. Stack<StringBuilder> result, from which i get strToRepeat. it must start out with one empty sb</StringBuilder>
2. Stack<Integer> kStack</Integer>
3. 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 [

Question 20

https://leetcode.com/problems/remove-k-digits/

code and review logic

Answer 20

since you must remove large numbers in large places, use monotonic non-decreasing stack. same consecutive nums are allowed.

1. for loop thru input string. while (k > 0 and stack and digit > stack.peek()), stack.pop()
2. take care of remaining k
3. get rid of leading 0s by converting stack into string builder (remember to use sb.reverse())

Question 21

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/description/

don’t code; review logic

Answer 21

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

Question 22

https://leetcode.com/problems/simplify-path/

code and review logic

Answer 22

1. get tokens by splitting path using / as delimiter
2. 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 “”
3. return String.join(“/”, stack). this is where absolute path should be handled

Question 23

https://leetcode.com/problems/132-pattern/description/

code and review logic

Answer 23

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.

Question 24

https://leetcode.com/problems/maximum-frequency-stack/description/

code and review logic

Answer 24

1. map of {value : count}
2. map of {count : stack of values with that count}
3. maxCount variable

remember to update maxCount after popping. if the stack at maxCount is empty, maxCount–;

Question 25

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

code and review logic

Answer 25

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;

Question 26

https://leetcode.com/problems/gas-station/

Answer 26

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

Question 27

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

Answer 27

1. get map of nums to counts
2. 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)

Question 28

https://leetcode.com/problems/valid-parenthesis-string/description/

Answer 28

standard recursion w/ memo. if symbol == ‘*’, res = ___ || ___ || ___.
don’t forget BC
if count < 0, return false

Question 29

https://leetcode.com/problems/partition-labels/description/

Answer 29

create map {letter : last idx}.

don’t forget edge case of when there is a single partition (just take the entire string)

Question 30

https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/

Answer 30

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]

Question 31

https://leetcode.com/problems/merge-triplets-to-form-target-triplet/

don’t code; review logic

Answer 31

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

Question 32

https://leetcode.com/problems/eliminate-maximum-number-of-monsters/description/

don’t code; review logic

Answer 32

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)

Question 33

https://leetcode.com/problems/two-city-scheduling/description/

don’t code; review logic

Answer 33

make differences[ ][3] array of [costB - costA, costA, costB].

SORT that array.

1st half go to city B; 2nd half to city A

Question 34

https://leetcode.com/problems/contains-duplicate-ii/

Answer 34

sliding window should be a hash set

Question 35

https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/

Answer 35

maintain sum variable that keeps track of the sum of the current window.

standard sliding window; it is always kept at size k

Question 36

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Answer 36

sliding window is a hash set.

Question 37

https://leetcode.com/problems/longest-repeating-character-replacement/

Answer 37

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

Question 38

https://leetcode.com/problems/frequency-of-the-most-frequent-element/description/

Answer 38

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

Question 39

https://leetcode.com/problems/minimum-size-subarray-sum/description/

Answer 39

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.

Question 40

https://leetcode.com/problems/find-k-closest-elements/description/

Answer 40

O(logn + k).

1. binary search to find idx of target, or idx of the element closest to target. this is contained in r.
2. 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

Question 41

https://leetcode.com/problems/permutation-in-string/description/

Answer 41

counts1[ ] and counts2[ ], each of size 26.

1. go thru window 1, [0, len1). update each map.
2. 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.
3. 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) )

Question 42

https://leetcode.com/problems/minimum-window-substring/description/

Answer 42

1. get counts of chars in target string in a hash map.
2. 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

Question 43

https://leetcode.com/problems/sliding-window-maximum/description/

Answer 43

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

Question 44

https://leetcode.com/problems/minimum-difference-between-highest-and-lowest-of-k-scores/description/

don’t code; review logic

Answer 44

.

Question 45

https://leetcode.com/problems/merge-sorted-array/description/

code and review logic

Answer 45

start from END of arrays

Question 46

https://leetcode.com/problems/move-zeroes/

code and review logic

Answer 46

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

Question 47

https://leetcode.com/problems/range-sum-query-immutable/description/

don’t code; review logic

Answer 47

know to use prefix sums array

Question 48

https://leetcode.com/problems/design-hashmap/description/

don’t code, review logic

Answer 48

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

Question 49

https://leetcode.com/problems/valid-sudoku/description/

don’t code; review logic

Answer 49

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 ‘.’

Question 50

https://leetcode.com/problems/product-of-array-except-self/description/

Answer 50

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.

Question 51

https://www.algoexpert.io/questions/two-colorable

don’t code; review logic

Answer 51

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)

Question 52

https://leetcode.com/problems/implement-trie-prefix-tree/description/

don’t code; review logic

Answer 52

Map<Character, Trie> children;

instead of using endSymbol, just use boolean endOfWord.

instead of initializing curr to root, it should be
Trie curr = this;

Question 53

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

Answer 53

scanningIdx and placementIdx both start at 1. whenever we encounter nums[p] > nums[p - 1], place that num at the scanningIdx

Question 54

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

Answer 54

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++].