How should I practice Minimum Fence Painting Strokes?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen problems in FastPrep.

Is Minimum Fence Painting Strokes associated with Google?

FastPrep tags this as a Google phone screen coding practice problem when the problem catalog has that company and stage context.

Minimum Fence Painting Strokes

Google● HardFULLTIMEPHONE SCREEN

Learn

Problem statement

A fence consists of adjacent vertical boards, each one unit wide. Board i has height heights[i]. Return the minimum number of brush strokes needed to paint every part of the fence.

A stroke is one of the following:

A vertical stroke paints one chosen board from bottom to top, regardless of its height.
A horizontal stroke paints one unit-high layer across any consecutive interval of boards. Every board in the interval must reach that layer, so the brush stays in contact throughout.

For this exercise, heights are nonnegative integers and horizontal layers lie between consecutive integer heights. Repainting previously painted areas is allowed, and it still counts as a stroke. A zero-height board has no area to paint and cannot be crossed by a horizontal stroke. An empty fence requires zero strokes.

Function

minPaintStrokes(heights: int[]) → int

Examples

Example 1

heights = [2,2,1,2,1]return = 3

Paint one bottom horizontal layer over all five boards, then two horizontal segments on the second layer. Two strokes cannot cover this shape.

Example 2

heights = [5,5,5]return = 3

Three vertical strokes beat five horizontal layers.

Example 3

heights = [0,0]return = 0

Zero-height boards have no area to paint under the explicit practice convention.

Constraints

0 <= heights.length <= 2000.
0 <= heights[i] <= 10^9.
Return an integer count. A valid answer never exceeds the number of boards.