Notes from LeetCode

  1. Find median from data stream — , modification — siding window median (use 2 heaps)
  2. — why does the heuristic in bfs / the condition to enter into the bfs queue matter ?
  3. — reduce the problem from yi + yj + |xi — xj| to (yi — xi) + (yj + xj) (convert the abs to a signed number)
  4. — 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]
  5. — 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 )
  6. — similar to the next greater element problem using stack
  7. — another application of the dp[i][j]=dp[i][k]+dp[k][j] , O(n³) complexity
  8. — 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
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 𝑓[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. — similar to a three way partition NP complete problem

11. A not so fun math problem using DP — .

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 —

Medium Problems

  2. — quickselect
  3. — end of cycle if the robot is back or if the direction has changed
  4. — two points and compute area
  5. ,— bi-directional BFS — have two queues, keep balancing them, keep two maps for storing the distances covered by q1 and q2;
  6. — why a two pointer solution does not work all the time ?
  7. — mathematical perspective
  8. — O(n) buckets approach
  9. — seive solution
  10. Design games — ,
  11. Next permutation —
  12. Just use remainders to check divisibility —
  13. — NP complete problem with bit masking
  14. — BFS and A* approaches
  15. Tackling edge cases —
  16. A nice trick used in substring questions —



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store