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
