1 Flashcards
https://leetcode.com/problems/search-in-rotated-sorted-array/
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
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
do bin search twice: once to find 1st pos, once to find last pos
https://leetcode.com/problems/time-based-key-value-store/description/
Map<String, List<Item>>. run bin search in get() function</Item>
https://leetcode.com/problems/maximum-number-of-removable-characters/description/
run bin search on removable chars input arr; for every m value, add removable[idx] up to m. use isSubsequence helper func.
https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
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
https://leetcode.com/problems/search-suggestions-system/
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
https://leetcode.com/problems/arranging-coins/
use sum formula [ n(n + 1) ] / 2 and run bin search. use longs and m = l + (r - l) / 2 trick
https://leetcode.com/problems/split-array-largest-sum/ / https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/description/
run bin search on [max(arr), sum(arr)]. use canSplit helper function
https://leetcode.com/problems/set-matrix-zeroes/description/
- go thru entire matrix. if matrix[i][j] == 0, set [i][0] and [0][j] to 0. maintain booleans for first row & first col.
- go thru matrix again starting from [1][1], setting to 0 as necessary
- set first row / first col to 0 as necessary. this must come after step 2 due to step 1
https://leetcode.com/problems/roman-to-integer/
if curr symbol’s value is LESS THAN next symbol’s value, subtraction must occur
rotate matrix 90, 180, 270
90: Transpose + Reverse Rows
180: Reverse Rows + Reverse columns
270 : Transpose + Reverse Columns
when transposing, j condition is j < i
https://leetcode.com/problems/powx-n/description/
even
2^8 = 2^4 * 2^4
odd
2^9 = 2^4 * 2^4 * 2
integer to roman
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
https://leetcode.com/problems/maximum-number-of-balloons/
2 counts hashmaps. find min ratio of givenWord letter count : targetWord letter count
https://leetcode.com/problems/next-greater-element-i/
monotonic stack for next greater + hashmap for indices
https://leetcode.com/problems/find-pivot-index/
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
https://leetcode.com/problems/top-k-frequent-elements/
- hashmap w/ counts of nums
- array of lists (of size len(nums) + 1), where each index is the frequency. place nums in correct index
- iterate thru the array in reverse, filling up result array
https://leetcode.com/problems/longest-consecutive-sequence/
- add all elements to hash set
- 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
- can return early if maxlen > len(nums) / 2
https://leetcode.com/problems/sort-colors/description/
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.
https://leetcode.com/problems/brick-wall/
- hashmap { gap position : count of rows that have a gap at that position }
** MUST NOT CONSIDER LAST BRICK of each row - answer = num rows - max(map values)
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
add to profit if curr day’s price > prev day’s price
https://leetcode.com/problems/encode-and-decode-tinyurl/description/
first url maps to 1, 2nd to 2, …
https://leetcode.com/problems/subarray-sum-equals-k/description/
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?
https://leetcode.com/problems/continuous-subarray-sum/description/
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
https://leetcode.com/problems/largest-number/description/
use comparator to sort array after converting everything into str
https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/description/
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.
https://leetcode.com/problems/unique-length-3-palindromic-subsequences/description/
- 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
gcd function
while (true) {
if (a == 0) return b;
if (b == 0) return a;
int temp = a;
a = b;
b = temp % b;
}
https://leetcode.com/problems/number-of-pairs-of-interchangeable-rectangles/description/
hashmap using reduced fractions (gcd function) as keys. for all values in the map, res += (value choose 2)
https://leetcode.com/problems/grid-game/description/
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)
https://www.lintcode.com/problem/508/ (wiggle sort)
if two nums don’t satisfy the condition, swap them. separate cases by even i and odd i
video solution 10:10
generate random num
Random random = new Random();
return random.nextInt(max - min) + min;
The min parameter (the origin) is inclusive, whereas the upper bound max is exclusive
https://leetcode.com/problems/insert-delete-getrandom-o1/description/
- 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
https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/
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
https://leetcode.com/problems/first-missing-positive/
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.
https://leetcode.com/problems/range-sum-query-2d-immutable/
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)
https://leetcode.com/problems/non-decreasing-array/
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].
https://leetcode.com/problems/push-dominoes/description/
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
https://leetcode.com/problems/house-robber-ii/description/
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)
house robber
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])
https://leetcode.com/problems/decode-ways/description/
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
https://leetcode.com/problems/minimum-cost-for-tickets/description/
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)
https://leetcode.com/problems/delete-and-earn/
- get hashmap of num counts
- sort the array and get rid of duplicates
- the rest is similar to house robber
https://leetcode.com/problems/triangle/description/
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)
https://leetcode.com/problems/coin-change/description/
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
https://leetcode.com/problems/perfect-squares/description/
exactly like coin change but remember to initialize dp[0] = 0; dp[1] = 1;
https://leetcode.com/problems/word-break/description/
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
https://leetcode.com/problems/maximum-product-subarray/description/
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)
https://leetcode.com/problems/longest-increasing-subsequence/description/
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])
https://leetcode.com/problems/partition-equal-subset-sum/description/
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
https://leetcode.com/problems/number-of-longest-increasing-subsequence/
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
https://leetcode.com/problems/integer-break/description/
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
https://leetcode.com/problems/unique-paths/
all first row and first col: 1 way to get to each cell.
sum left and upper cells.
https://leetcode.com/problems/longest-common-subsequence/description/
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
https://leetcode.com/problems/coin-change-ii/
BC: 1 way to make $0.
outer loop thru coins, inner loop thru dp. if coin is small enough, dp[j] += dp[j - coin]
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
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
https://leetcode.com/problems/target-sum/
classic dfs helper, but remember the key of the cache must be idx + “-“ + currSum
https://leetcode.com/problems/interleaving-string/description/
recursive helper.
check if len1 + len2 == len3.
dfs helper. use Boolean[len1 + 1][len2 + 2] cache, so we can use null.
https://leetcode.com/problems/stone-game/
dfs helper.
BC:
if (end < start)
return (aSum > bSum);
helper function takes in input array, cache, start idx, end idx, boolean isAliceTurn, aSum, bSum
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/
dfs helper.
Integer[][] cache to store max path length at given i,j.
dp[i][j] = 1 + max(top, bottom, left, right)
min path sum (matrix)
prefix sums for row 0 and col 0.
dp[i][j] = matrix[i][j] + min of dp(top, left)
https://leetcode.com/problems/maximal-square/
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
https://leetcode.com/problems/distinct-subsequences/description/
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
https://leetcode.com/problems/maximum-alternating-subsequence-sum/
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
https://leetcode.com/problems/edit-distance/
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)
https://leetcode.com/problems/count-vowels-permutation/description/
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
https://leetcode.com/problems/regular-expression-matching/
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 ||
https://leetcode.com/problems/intersection-of-two-linked-lists/
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
https://leetcode.com/problems/copy-list-with-random-pointer/description/
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)
Merge k sorted lists
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
https://leetcode.com/problems/design-circular-queue/description/
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)
https://leetcode.com/problems/sort-list/
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
insertion sort LL
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
find duplicate num in array w/o modifying array
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]
https://leetcode.com/problems/happy-number/
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
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.
if n <= 0, return false.
for (int f : factors) {
while (n % f == 0) {
n /= f;
}
}
return n ==1;
reverse LL recursively
–
https://leetcode.com/problems/shift-2d-grid/description/
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
detect if integer is palindrome w/o conv to string
- get greatest place of x
while (num / 10 >= greatestPlace) {
greatestPlace *= 10;
}
- while x > 0, compare its leftmost, rightmost digits. then chop off leftmost and rightmost, and greatest place /= 100
https://leetcode.com/problems/robot-bounded-in-circle/
- 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
