How should I practice Minimum Fence Painting Operations?

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

Is Minimum Fence Painting Operations associated with Gemini?

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

Problem · Dynamic Programming

Minimum Fence Painting Operations

Learn this problem

● Hard

GeminiFULLTIMEPHONE SCREEN

Problem statement

A fence is made of n adjacent vertical boards. Board i has width 1 and height heights[i].

You have a brush of width 1 and may perform only these two types of painting operations:

Vertical stroke: paint one entire board from bottom to top in a single operation.
Horizontal stroke: paint exactly one unit of height across a contiguous segment of adjacent boards. A horizontal stroke may cover only portions of boards that still need paint.

Return the minimum number of operations required to paint the entire fence.

Function

minPaintOperations(heights: int[]) → int

Complete the function minPaintOperations in the editor below.

minPaintOperations has the following parameter:

int[] heights: the heights of the boards

Returns

int: the minimum number of painting operations.

Examples

Example 1

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

Paint one horizontal stroke across all five boards to cover the first unit of height. Then paint a second horizontal stroke across the first two boards. Finally, paint board 4 vertically. The entire fence is painted in 3 operations.

Example 2

heights = [1, 1, 1, 1]return = 1

A single horizontal stroke across all four boards paints the whole fence.

Constraints

The source thread did not provide explicit numeric bounds.

heights.length >= 1
Each heights[i] is a non-negative integer.