Notes from LeetCode

1. Sliding window maximum https://leetcode.com/problems/sliding-window-maximum/ — deque application
2. 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)
3. 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 ?
4. 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)
5. 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]
6. 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 )
7. 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
8. 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
9. 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)PLL
or, in other words
𝑓[𝑛]=𝑓[𝑛−1]+𝑓[𝑛−2]+𝑓[𝑛−3](Answer 1)(Answer 1)f[n]=f[n−1]+f[n−2]+f[n−3]
with 𝑓[0]=1,𝑓[1]=2,𝑓[2]=22=4f[0]=1,f[1]=2,f[2]=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 𝑓[3]=22+2+1=7f[3]=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/

Medium Problems

1. https://leetcode.com/problems/insert-delete-getrandom-o1/submissions/
2. https://leetcode.com/problems/random-pick-with-weight/solution/
3. https://leetcode.com/problems/kth-largest-element-in-an-array/ — quickselect
4. https://leetcode.com/problems/robot-bounded-in-circle/ — end of cycle if the robot is back or if the direction has changed
5. https://leetcode.com/problems/container-with-most-water/ — two points and compute area
6. 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;
7. https://leetcode.com/problems/contiguous-array/solution/ — why a two pointer solution does not work all the time ?
8. https://leetcode.com/problems/minimum-moves-to-equal-array-elements/ — mathematical perspective
9. https://leetcode.com/problems/car-pooling/ — O(n) buckets approach
10. https://leetcode.com/problems/count-primes/solution/ — seive solution
11. Design games — https://leetcode.com/problems/design-snake-game/ , https://leetcode.com/problems/candy-crush/
12. Next permutation — https://leetcode.com/problems/next-greater-element-iii/discuss/101824/Simple-Java-solution-(4ms)-with-explanation.
13. Just use remainders to check divisibility — https://leetcode.com/problems/smallest-integer-divisible-by-k/solution/
14. https://leetcode.com/problems/partition-to-k-equal-sum-subsets/ — NP complete problem with bit masking
15. https://leetcode.com/problems/shortest-path-in-binary-matrix/ — BFS and A* approaches
16. Tackling edge cases — https://leetcode.com/problems/burst-balloons/
17. A nice trick used in substring questions — https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/