Minimum Number of Strokes Needed

Pin down what one stroke can paint

A minimum-strokes problem could be the Strange Printer style operation, painting a contiguous horizontal segment of a histogram, or removing a colored interval. The algorithm depends entirely on that rule. For the common fence-painting version, recursively solve an interval: either paint each bar vertically, costing its count, or paint one horizontal layer across the interval, subtract it, split around zeros, and recurse. An optimized monotone-stack form is possible for variants where each new height rise starts necessary horizontal work.

Show the decision boundary

The key reasoning is comparing the cost of continuing a shared horizontal stroke against treating bars independently; blindly using a stack without proving that strokes can extend across the specified gaps is unsafe. If the operation is Strange Printer, use interval DP dp[l][r] and merge equal end characters instead, which has different complexity. State the exact variant before claiming Big-O. The basic divide-and-conquer fence formulation can be O(n^2) in the worst case, while a valid monotone-stack optimization is often O(n) time and O(n) space. Test equal heights, zeros, one bar, and disjoint colored sections.