FastPrepFastPrep
Problem Brief

Minimum Fence Painting Operations

FULLTIMEPHONE SCREEN

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:

  1. Vertical stroke: paint one entire board from bottom to top in a single operation.
  2. 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 Description

Complete the function minPaintOperations in the editor below.

minPaintOperations has the following parameter:

  1. int[] heights: the heights of the boards

Returns

int: the minimum number of painting operations.

1Example 1

Input
heights = [2, 2, 1, 2, 1]
Output
3
Explanation

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.

2Example 2

Input
heights = [1, 1, 1, 1]
Output
1
Explanation

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

Constraints

Limits and guarantees your solution can rely on.

The source thread did not provide explicit numeric bounds.

  • heights.length >= 1
  • Each heights[i] is a non-negative integer.
public int minPaintOperations(int[] heights) {
    // write your code here
}
Input

heights

[2, 2, 1, 2, 1]

Output

3

Sign in to submit your solution.