educative.io

Educative

O(n log n) solution

DP solution is OK when interviewing for a junior positon, but may not cut it otherwise. Dear authors, please at least mention that there is a faster solution based on a monotonic sequence. In fact, I think that it’s quite natural to arrive at that solution after understanding the tabulation.

2 Likes

For those who are curious, https://www.youtube.com/watch?v=22s1xxRvy28