Show problems as
Classic problem #1526HardArrayDynamic ProgrammingStackGreedyMonotonic Stack

Minimum Number of Increments on Subarrays to Form a Target Array

Real-world version: Sealant Runs Along a Towpath
Tracked in this browser only
Read Minimum Number of Increments on Subarrays to Form a Target Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A canal towpath is split into n numbered sections laid end to end. The surveyor has written down how thick the sealant on each section must finish: section i needs exactly coats[i] coats. The path starts bare.

A sealant lorry works in runs. One run chooses a contiguous block of sections, drives the block once, and leaves exactly one further coat on every section inside it. A block may be as short as one section or as long as the whole path, and later runs may overlap earlier ones however you like.

Sealant cannot be lifted once laid, so no section may finish with more coats than the surveyor asked for, and none may finish with fewer.

Return the fewest runs that leave every section at its written thickness.

Examples

Example 1

Input
coats = [2, 2, 2]
Output
2

Two runs, each driving the whole path, leave every section with two coats.

Example 2

Input
coats = [1, 4, 2]
Output
4

One run over all three sections, one over the last two, then two more over the middle section alone: the sections finish at one, four and two coats.

Example 3

Input
coats = [4, 1, 3]
Output
6

Three runs over the first section only, one over the whole path, then two over the last section only, finishing at four, one and three coats.

Example 4

Input
coats = [7, 2, 7, 2, 7]
Output
17

Seventeen runs suffice: two over the whole path, then five more over each of the first, third and fifth sections taken singly.

Constraints

  • 1 <= coats.length <= 10^5
  • 1 <= coats[i] <= 10^5
  • The inputs are chosen so the answer fits in a signed 32-bit integer.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_number_operations(coats: list[int]) -> int:
Java
public int minNumberOperations(int[] coats)

More on the same topics