Time complexity of a vertical sweep algorithm with histogram computations
$O(h)$ sounds hard to believe, unless there's some pre computation that's not counted here, as it takes $\Theta(hw)$ time just to read every pixel of the image.

Computing a histogram from scratch can't be done in $O(1)$ time.  But updating a histogram can be done efficiently.  If you already have a histogram for some set of pixels, and then you add or delete one pixel, you can update the histogram in $O(1)$ time.  This kind of idea can be used to speed up the sort of thing you're talking about, because all of the histograms we want are closely related.

In particular, when we increment $l$, we add or delete a row from a histogram.  Thus you can update the histogram more efficiently than computing it from scratch.