Fold and Scan
The Array Cast
00:00
How to Find the Smallest Window at Every Time
There's a known way to do this to keep the to keep enough information so that you can find the smallest window at every time. And it runs in linear time and it uses maybe in the worst case, it uses an amount of memory that's equal to the window size. But I looked at this and I said, well, you know, if the window is small enough, what I should really be doing is taking taking pairwise maximums in powers of two. That lets me use array operations. And then I tested this out and it performed very well. What I actually found was I couldn't find any combination of arguments where that linear time C solution was better than this logar
Transcript
Play full episode
