1

Question 1

https://leetcode.com/problems/search-in-rotated-sorted-array/

Answer 1

there are only 2 ways the array can end up: L < M, L > M. and for each of those 2 ways, the target must be in the 1st half of the array or the 2nd. so 4 cases

Question 2

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/

Answer 2

do bin search twice: once to find 1st pos, once to find last pos

Question 3

https://leetcode.com/problems/time-based-key-value-store/description/

Answer 3

Map<String, List<Item>>. run bin search in get() function</Item>

Question 4

https://leetcode.com/problems/maximum-number-of-removable-characters/description/

Answer 4

run bin search on removable chars input arr; for every m value, add removable[idx] up to m. use isSubsequence helper func.

Question 5

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

Answer 5

sort of bfs. have curr pointing to start of curr level, next pointing to start of next level. do the connecting for all of curr’s children before moving to next level

Question 6

https://leetcode.com/problems/search-suggestions-system/

Answer 6

iterate thru searchWord while using l, r ptrs in products[ ] to eliminate invalid words. invalid is when chars aren’t the same or when the product is too short

Question 7

https://leetcode.com/problems/arranging-coins/

Answer 7

use sum formula [ n(n + 1) ] / 2 and run bin search. use longs and m = l + (r - l) / 2 trick

Question 8

https://leetcode.com/problems/split-array-largest-sum/ / https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/description/

Answer 8

run bin search on [max(arr), sum(arr)]. use canSplit helper function

Question 9

https://leetcode.com/problems/set-matrix-zeroes/description/

Answer 9

1. go thru entire matrix. if matrix[i][j] == 0, set [i][0] and [0][j] to 0. maintain booleans for first row & first col.
2. go thru matrix again starting from [1][1], setting to 0 as necessary
3. set first row / first col to 0 as necessary. this must come after step 2 due to step 1

Question 10

https://leetcode.com/problems/roman-to-integer/

Answer 10

if curr symbol’s value is LESS THAN next symbol’s value, subtraction must occur

Question 11

rotate matrix 90, 180, 270

Answer 11

90: Transpose + Reverse Rows
180: Reverse Rows + Reverse columns
270 : Transpose + Reverse Columns
when transposing, j condition is j < i

Question 12

https://leetcode.com/problems/powx-n/description/

Answer 12

even
2^8 = 2^4 * 2^4

odd
2^9 = 2^4 * 2^4 * 2

Question 13

integer to roman

Answer 13

make map (using arraylist) w/ all roman numerals, including the 6 subtraction cases, mapped to their values. iterate thru list in reverse order, appending symbols to result

Question 14

https://leetcode.com/problems/maximum-number-of-balloons/

Answer 14

2 counts hashmaps. find min ratio of givenWord letter count : targetWord letter count

Question 15

https://leetcode.com/problems/next-greater-element-i/

Answer 15

monotonic stack for next greater + hashmap for indices

Question 16

https://leetcode.com/problems/find-pivot-index/

Answer 16

two passes, first time to get rightsum

the 2 passes must be done in the same direction; otherwise the pivox idx we return won’t necessarily be the leftmost

Question 17

https://leetcode.com/problems/top-k-frequent-elements/

Answer 17

1. hashmap w/ counts of nums
2. array of lists (of size len(nums) + 1), where each index is the frequency. place nums in correct index
3. iterate thru the array in reverse, filling up result array

Question 18

https://leetcode.com/problems/longest-consecutive-sequence/

Answer 18

1. add all elements to hash set
2. loop thru input array again. you know a num is the start of a sequence if !hashset.contains(num - 1). start counting length from there
3. can return early if maxlen > len(nums) / 2

Question 19

https://leetcode.com/problems/sort-colors/description/

Answer 19

L ptr, R ptr, idx.
when idx encounters a 0, it should always go to L; a 2, to R.
** after swapping idx & r, any num can be at idx, so we must check idx again later (don’t idx++)
*** after swapping idx & l, we must increment idx.

Question 20

https://leetcode.com/problems/brick-wall/

Answer 20

1. hashmap { gap position : count of rows that have a gap at that position }
   ** MUST NOT CONSIDER LAST BRICK of each row
2. answer = num rows - max(map values)

Question 21

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

Answer 21

add to profit if curr day’s price > prev day’s price

Question 22

https://leetcode.com/problems/encode-and-decode-tinyurl/description/

Answer 22

first url maps to 1, 2nd to 2, …

Question 23

https://leetcode.com/problems/subarray-sum-equals-k/description/

Answer 23

hashmap of prefix sum : count of occurrences of that prefix sum.

must put {0 : 1} in map

only put new prefix sum count in hashmap after recalculating result.

can we chop off some prefix sum s.t. the sum equals k?

Question 24

https://leetcode.com/problems/continuous-subarray-sum/description/

Answer 24

hashmap (sum % k) : (idx). if we encounter a remainder that’s already in map and the subarr is long enough, we’ve found an ans.

intuition: say we’re at idx 0, and that subarray (containing just arr[0]) has a remainder of 5 when modded by k. then when we get to idx 2, the subarray sum % k again has a remainder of 5. that means the nums (arr[1], arr[2]) we’ve added to the subarray since map.get(5) have a sum divisible by k.

edge case: map.put(0, -1)

** never revise kv pair, only add if it doesn’t exist

Question 25

https://leetcode.com/problems/largest-number/description/

Answer 25

use comparator to sort array after converting everything into str

Question 26

https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/description/

Answer 26

maintain count of extra closing brackets. ++ for ], -- for [. keep track of max at each char. at the end, return max/2 if mafdomix is even, (max + 1)/2 if max is odd, since each swap gets rid of 2 extras if the string is already balanced, the extraCloses count would never be greater than 0 (it only goes negative), so at the end we return 0, which makes sense b/c no swaps are needed.

Question 27

https://leetcode.com/problems/unique-length-3-palindromic-subsequences/description/

Answer 27

- get hashmap of letter counts, starting at i = 1 (this is the "right chars" set) - initialize set for left chars - iterate thru string, treating the ith char as the middle of the pal. add the left char to the Left set and decrement the count of the current char in the Right hashmap - at each char, go thru chars a-z. this is the "outer" char. add to set. - remember Item class doesn't work; only Pair does

Question 28

gcd function

Answer 28

while (true) { if (a == 0) return b; if (b == 0) return a; int temp = a; a = b; b = temp % b; }

Question 29

https://leetcode.com/problems/number-of-pairs-of-interchangeable-rectangles/description/

Answer 29

hashmap using reduced fractions (gcd function) as keys. for all values in the map, res += (value choose 2)

Question 30

https://leetcode.com/problems/grid-game/description/

Answer 30

create prefix sums matrix. iterate thru cols, treating the ith col as the col where the 1st robot turns. if the 1st robot turns at the ith col, the 2nd robot has a top region (top row) and a bottom region(bottom row) to choose from. robotTwoPts = max(top, bottom), but the final result is min(res, robotTwoPts)

Question 31

https://www.lintcode.com/problem/508/ (wiggle sort)

Answer 31

if two nums don't satisfy the condition, swap them. separate cases by even i and odd i video solution 10:10

Question 32

generate random num

Answer 32

Random random = new Random(); return random.nextInt(max - min) + min; The min parameter (the origin) is inclusive, whereas the upper bound max is exclusive

Question 33

https://leetcode.com/problems/insert-delete-getrandom-o1/description/

Answer 33

- list - hashmap {val : idx in list} - when removing a value, always call list.pop(), and put the popped value back in the list, and edit the hashmap entry

Question 34

https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/

Answer 34

the string must contain 2^k distinct binary codes. get all substrings of length k and add to hash set. at the end, check if set.size() == 2^k

Question 35

https://leetcode.com/problems/first-missing-positive/

Answer 35

the smallest missing pos int is 1; largest is len(arr) + 1. pass 1: change neg values to 0 pass 2: consider abs val of arr[i]; get arr[i]'s mapping idx and set arr[mappingIdx] to neg. if arr[mappingIdx] == 0, set it to MIN INT. pass 3: check if arr[i] >= 0; if so, return i + 1. if we still haven't returned yet, that means the disappeared num is arr.length + 1.

Question 36

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

Answer 36

use 2d prefix sum matrix, with preSums[i][j] containing the sum of the matrix enclosed by [0][0], [i][j] simple case: when the region touches 1st row or 1st col else: res = preSums(bottom right) - preSums(1 cell above top right) - preSums(1 cell left of bottom left) + preSums(upper left diagonal of top left)

Question 37

https://leetcode.com/problems/non-decreasing-array/

Answer 37

we are considering ith, (i+1)th elements. modifying an element means SETTING its val to the other element. whenever (i+1)th element is >= (i-1)th element or when i-1 is OOB, modify ith element. else modify the other one whenever possible, we want to decrease the left element, because that maximizes the possibilities for the elements to come. that is possible when arr[i + 1] >= arr[i - 1].

Question 38

https://leetcode.com/problems/push-dominoes/description/

Answer 38

using a queue of indices, add only L and R dominoes. L: just check for valid index and if the prev domino is neutral R: check for valid idx and if the next domino is neutral. if so, then go on to check if the domino at idx + 2 is 'L'. in that case, must poll one more time to remove the idx + 2 domino. don't do anything else. if the idx + 2 domino is not L, then change the neutral domino to R and add to q

Question 39

https://leetcode.com/problems/house-robber-ii/description/

Answer 39

use house robber 1 as helper function, call it twice, once with house 1 robbed and once with last house robbed (cannot rob house 1 and last house together)

Question 40

house robber

Answer 40

work out the soln w/ dp array first, then use it to derive the soln that just keeps track of two variables. arr[i] = Math.max(arr[i - 1], arr[i - 2] + arr[i])

Question 41

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

Answer 41

consider the two substrings [i, i] and [i - 1, i]. if the 1-digit substr is valid, dp[i] = dp[i - 1] (the result of the previous dp) if the 2-digit substr is valid, dp[i] += dp[i - 2] *** MUST account for when i - 2 is OOB; just add 1 in that case

Question 42

https://leetcode.com/problems/minimum-cost-for-tickets/description/

Answer 42

add all travel days to set. create arr of size lastday+1. iterate thru [1, lastday]: if the day isn't in the set, then the cost for that day is the cost of the prev day. if it is, then find the min cost among the 3 choices of passes. ex: for a 7-day pass ending on the ith day, the cost is 7day pass cost + cost of (i-7)th day (if i - 7 < 0, the cost is just 7day pass cost)

Question 43

https://leetcode.com/problems/delete-and-earn/

Answer 43

1. get hashmap of num counts 2. sort the array and get rid of duplicates 3. the rest is similar to house robber

Question 44

https://leetcode.com/problems/triangle/description/

Answer 44

dp, only need to store one row at a time. start with dp = last row of triangle. value = value of cell + min(two values beneath the cell)

Question 45

https://leetcode.com/problems/coin-change/description/

Answer 45

sort coins array, declare dp array of length amount + 1. nested for loops; outer loop is coins, inner loop is dp. starting at first coin, fill dp array. if dp[amount - coin] == int.max_val or coin value is too large, skip

Question 46

https://leetcode.com/problems/perfect-squares/description/

Answer 46

exactly like coin change but remember to initialize dp[0] = 0; dp[1] = 1;

Question 47

https://leetcode.com/problems/word-break/description/

Answer 47

boolean[] dp = new boolean[s.length() + 1]. dp[1] means can put break before 1 BC: dp[0] = true; outer loop dp array, inner loop wordDict. remember to continue if word is too long

Question 48

https://leetcode.com/problems/maximum-product-subarray/description/

Answer 48

keep track of 3 vars - res, currMin, currMax - all initialized to nums[0]. for each i, there are 2 products: prod1 = currMin * nums[i], prod2 = currMax * nums[i]. update currMin, currMax at each iteration - must not consider currMin/currMax itself in calculations, since we want a subarray (which is contiguous)

Question 49

https://leetcode.com/problems/longest-increasing-subsequence/description/

Answer 49

outer loop thru dp array, inner loop thru all 0 <= j < i. if nums[j] < nums[i], dp[i] = max(dp[i], 1 + dp[j])

Question 50

https://leetcode.com/problems/partition-equal-subset-sum/description/

Answer 50

if sum of array is odd, return false. generate all subset sums (using set of subset sums); once you encounter a sum == target, return true

Question 51

https://leetcode.com/problems/number-of-longest-increasing-subsequence/

Answer 51

two dp[] arrays, one for lengths, one for counts. maintain two variables, result (count of longest subsq) and maxLen. if you get a new longest length, dpCounts[i] = dpCounts[j]. if length == maxLen, dpCounts[i] += dpCounts[j]. then do the same, comparing maxLen with the final value of dp[i] after going thru all j < i

Question 52

https://leetcode.com/problems/integer-break/description/

Answer 52

BC: dp[1] = 1 nested for loops; second loop is j < i. edge case: before entering the inner loop, dp[i] = 0 iff i is the final num

Question 53

https://leetcode.com/problems/unique-paths/

Answer 53

all first row and first col: 1 way to get to each cell. sum left and upper cells.

Question 54

https://leetcode.com/problems/longest-common-subsequence/description/

Answer 54

2d array with "" in row 0 and "" in col 0. if chars are ==, append char to substr from upper left diagonal. else, take longest substr from top cell or left cell

Question 55

https://leetcode.com/problems/coin-change-ii/

Answer 55

BC: 1 way to make $0. outer loop thru coins, inner loop thru dp. if coin is small enough, dp[j] += dp[j - coin]

Question 56

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/

Answer 56

dfs recursive helper. change buyOrSell, idx. cooldown is always same: buyOrSell stays same, idx + 1 if buying, flip buyOrSell, idx + 1, and -prices[idx]. if selling, also flip, but idx + 2 (forced cooldown) and +prices[idx]. when putting in cache, take max(cooldown, ___) cache key: idx + "-" + buyOrSell

Question 57

https://leetcode.com/problems/target-sum/

Answer 57

classic dfs helper, but remember the key of the cache must be idx + "-" + currSum

Question 58

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

Answer 58

recursive helper. check if len1 + len2 == len3. dfs helper. use Boolean[len1 + 1][len2 + 2] cache, so we can use null.

Question 59

https://leetcode.com/problems/stone-game/

Answer 59

dfs helper. BC: if (end < start) return (aSum > bSum); helper function takes in input array, cache, start idx, end idx, boolean isAliceTurn, aSum, bSum

Question 60

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/

Answer 60

dfs helper. Integer[][] cache to store max path length at given i,j. dp[i][j] = 1 + max(top, bottom, left, right)

Question 61

min path sum (matrix)

Answer 61

prefix sums for row 0 and col 0. dp[i][j] = matrix[i][j] + min of dp(top, left)

Question 62

https://leetcode.com/problems/maximal-square/

Answer 62

dp[i][j] is the side length of the longest square you can make w/ i,j as the lower right corner dp[i][j] = min(top, left, top left diagonal) + 1 when declaring the dp[][] array, add 1 to each dimension. this is so we can get the 1s in the first row and first col at every dp cell, update max

Question 63

https://leetcode.com/problems/distinct-subsequences/description/

Answer 63

dfs helper. BCs: - we are at end of t; return 1 - we are at end of s and not at end of t; return 0 key of cache = idx1 + "," + idx2. 2 paths: 1. increment both indices 2. increment only sIdx if chars are equal, go down both paths. else, go down only path 2

Question 64

https://leetcode.com/problems/maximum-alternating-subsequence-sum/

Answer 64

this is the problem with dfs in the other direction. cache w/ key being [idx, evenOrOdd] BC: idx out of bounds, means empty array has max sum of 0. SAME IDEA as buying stock w/ cooldown

Question 65

https://leetcode.com/problems/edit-distance/

Answer 65

int[][] dp with "" in row 0 and "" in col 0. only need to store 2 rows at a time. (so it's just dp[ ]) if chars are ==, dp[j] = left cell. else, dp[j] = 1 + min(left, top left diagonal, top)

Question 66

https://leetcode.com/problems/count-vowels-permutation/description/

Answer 66

dp[x] = sum of all dp letters that x can follow, NOT sum of all dp letters that can follow x to remember the above, keep in mind we're storing, at dp[x], how many strings we can create that end in the cahracter 'x' mod each sum as the dp array is being filled. only modding at the end won't work

Question 67

https://leetcode.com/problems/regular-expression-matching/

Answer 67

declare boolean match to keep track of whether the two chars can match. this is where the '.' is handled s == s.length() (the str w/o * and .) isn't a base case for returning b/c there can be * and . in p that we still need to consider if there's no *: - if !match, return false - if match, go down path with i + 1, j + 1 if there is *: - if !match, go down path with i, j + 2 (not taking a match) - if match, go down the 2 possible paths (we can either take the match or not take it) and take the ||

Question 68

https://leetcode.com/problems/intersection-of-two-linked-lists/

Answer 68

while (ptrA != ptrB), let the ptrs go thru their respective lists. if ptrA == null, set it to headB, and vice versa. when the ptrs are == (either intersection found, or both are null) return a ptr

Question 69

https://leetcode.com/problems/copy-list-with-random-pointer/description/

Answer 69

use map { original node : copy node}. two passes thru LL: 1. just create the new copy nodes and put in map. no connecting. 2. do connecting. copy.next = map.get(curr.next)

Question 70

Merge k sorted lists

Answer 70

if linked lists, just add all the heads to pq. make sure to only add if node is not null. a bit more involved if they're arrays. use Item class with value, elementIdx, arrayIdx

Question 71

https://leetcode.com/problems/design-circular-queue/description/

Answer 71

use doubly LL w/ dummy head and tail. add nodes to end of queue (right before dummy tail). remove nodes from front of queue (right after dummy head)

Question 72

https://leetcode.com/problems/sort-list/

Answer 72

use merge sort. 1. main function: split lists down the middle w/ helper (see 2.) and call merge() on the two lists 2. use slow, fast ptrs to get middle node 3. merge 2 lists

Question 73

insertion sort LL

Answer 73

use dummy head and curr ptr. (when comparing values, always use .next) while (curr.next is not null), - while list is sorted (curr.val <= curr.next.val), advance curr - when not sorted, nodeToInsert = curr.next. - using while loop, locate the node to insert nodeToInsert after - rearrange ptrs

Question 74

find duplicate num in array w/o modifying array

Answer 74

same as find starting point of cycle in LL, but with slow initially set to nums[0], fast to nums[nums[0]]. setting both to 0 or both to nums[0] is incorrect. 2nd time - set slow ptr to 0, NOT nums[0]

Question 75

https://leetcode.com/problems/happy-number/

Answer 75

add results of calculations to hash set. if you end up at a num that's already in the set, num isn't happy. if you end at 1, num is happy

Question 76

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return true if n is an ugly number.

Answer 76

if n <= 0, return false. for (int f : factors) { while (n % f == 0) { n /= f; } } return n ==1;

Question 77

reverse LL recursively

Answer 77

--

Question 78

https://leetcode.com/problems/shift-2d-grid/description/

Answer 78

use 2d Integer[][] array, then convert to AL. (i,j) to 1d idx: i*numCols + j. then add shift, and mod by (numCols * numRows) back to (i, j): r = idx / numCols c = idx % numCols

Question 79

detect if integer is palindrome w/o conv to string

Answer 79

1. get greatest place of x while (num / 10 >= greatestPlace) { greatestPlace *= 10; } 2. while x > 0, compare its leftmost, rightmost digits. then chop off leftmost and rightmost, and greatest place /= 100

Question 80

https://leetcode.com/problems/robot-bounded-in-circle/

Answer 80

- position change, direction no change: no cycle. (this means you keep moving in 1 direction) - if both change, there will be a cycle keep track of a string, direction, and posX, posY. review structure and return statements