Notes from LeetCode
- Sliding window maximum https://leetcode.com/problems/sliding-window-maximum/ — deque application
- Find median from data stream — https://leetcode.com/problems/find-median-from-data-stream/ , modification — siding window median https://leetcode.com/problems/sliding-window-median/solution/ (use 2 heaps)
- https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/ — why does the heuristic in bfs / the condition to enter into the bfs queue matter ?
- https://leetcode.com/problems/max-value-of-equation/ — reduce the problem from yi + yj + |xi — xj| to (yi — xi) + (yj + xj) (convert the abs to a signed number)
- https://leetcode.com/problems/minimum-window-subsequence/ — what does the dp array intend to store , dp[i][j] stores the length of the first sequence needed. The starting index will be obtained from this length when we go through dp[i][length of second string to be searched] ie. i-dp[i][n]
- https://leetcode.com/problems/maximum-number-of-visible-points/ — field of vision — adding 360 degrees to the points we obtained and checking if it falls within the window . Angle between dx,dy and y axis = ( atan2 (dx/dy)*180)/pi )
- https://leetcode.com/problems/car-fleet-ii/discuss/1086364/Full-detailed-explaination-starting-with-a-simplier-problem — similar to the next greater element problem using stack
- https://leetcode.com/problems/encode-string-with-shortest-length/ — another application of the dp[i][j]=dp[i][k]+dp[k][j] , O(n³) complexity
- https://leetcode.com/problems/student-attendance-record-ii/solution/ — for the no more than three consecutive part f(x) = f(x-1)-f(x-4) (there is only only way to get to x-1 with three consecutive Ls from x-4th index , so f(ending at index x with three consecutive ls) = f(x-1)-f(x-4) or refer to this https://math.stackexchange.com/questions/2250558/recurrence-relation-in-a-student-attendance-problem
You have 3 possible mutually exclusive and exhaustive endings to valid sequences of length 𝑛n(valid sequence length 𝑛−1)P(valid sequence length n−1)P(valid sequence length 𝑛−2)PL(valid sequence length n−2)PL(valid sequence length 𝑛−3)PLL(valid sequence length n−3)PLLor, in other words𝑓[𝑛]=𝑓[𝑛−1]+𝑓[𝑛−2]+𝑓[𝑛−3](Answer 1)(Answer 1)f[n]=f[n−1]+f[n−2]+f[n−3]with 𝑓=1,𝑓=2,𝑓=22=4f=1,f=2,f=22=4.But since𝑓[𝑛−1]=𝑓[𝑛−2]+𝑓[𝑛−3]+𝑓[𝑛−4]f[n−1]=f[n−2]+f[n−3]+f[n−4]we have𝑓[𝑛]=2𝑓[𝑛−1]−𝑓[𝑛−4](Answer 2)(Answer 2)f[n]=2f[n−1]−f[n−4]with the extra initial value 𝑓=22+2+1=7f=22+2+1=7.
10. https://leetcode.com/problems/optimal-account-balancing/ — similar to a three way partition NP complete problem
11. A not so fun math problem using DP — https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/ .
Its easy when we only to deal with rectangles in the above problem . But when you try placing squares(side s and side k in the fig), the problem changes as below .
We need to solve for the rectangle case and the square case to find the min number and cache the answer.
12. Interesting line sweep problem — https://leetcode.com/problems/split-array-largest-sum/
- https://leetcode.com/problems/kth-largest-element-in-an-array/ — quickselect
- https://leetcode.com/problems/robot-bounded-in-circle/ — end of cycle if the robot is back or if the direction has changed
- https://leetcode.com/problems/container-with-most-water/ — two points and compute area
- https://leetcode.com/problems/minimum-knight-moves/solution/ , https://leetcode.com/problems/word-ladder/— bi-directional BFS — have two queues, keep balancing them, keep two maps for storing the distances covered by q1 and q2;
- https://leetcode.com/problems/contiguous-array/solution/ — why a two pointer solution does not work all the time ?
- https://leetcode.com/problems/minimum-moves-to-equal-array-elements/ — mathematical perspective
- https://leetcode.com/problems/car-pooling/ — O(n) buckets approach
- https://leetcode.com/problems/count-primes/solution/ — seive solution
- Design games — https://leetcode.com/problems/design-snake-game/ , https://leetcode.com/problems/candy-crush/
- Next permutation — https://leetcode.com/problems/next-greater-element-iii/discuss/101824/Simple-Java-solution-(4ms)-with-explanation.
- Just use remainders to check divisibility — https://leetcode.com/problems/smallest-integer-divisible-by-k/solution/
- https://leetcode.com/problems/partition-to-k-equal-sum-subsets/ — NP complete problem with bit masking
- https://leetcode.com/problems/shortest-path-in-binary-matrix/ — BFS and A* approaches
- Tackling edge cases — https://leetcode.com/problems/burst-balloons/
- A nice trick used in substring questions — https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/