0431HardArrayDynamic ProgrammingStackGreedyMonotonic Stack

Sealant Runs Along a Towpath

Tracked in this browser only

Trains the technique from

LeetCode 1526Minimum Number of Increments on Subarrays to Form a Target Array

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_number_operations(coats: list[int]) -> int:

Java

public int minNumberOperations(int[] coats)

The intended approach

Time O(n): one pass, constant work per section.Space O(1) beyond the input: one accumulator.

Read the profile once from left to right. The leftmost section has no neighbour to inherit runs from, so its whole demand is paid for outright. At every later section, compare it with the section on its left: a rise has to be paid for with that many extra runs starting there, while a level or falling section needs no new run at all. Summing the leftmost demand and every rise gives the answer in one pass with a single accumulator.

Pythonentry point: min_number_operations

def min_number_operations(coats):
    # A run can only ever end a section's stack of coats; walking left to right,
    # a section that needs more coats than its left neighbour must start exactly
    # that many fresh runs, and a section needing fewer can reuse runs already
    # open. So the total is the first section's demand plus every rise along the
    # walk. O(n) time, O(1) space beyond the input.
    runs = coats[0]
    for i in range(1, len(coats)):
        if coats[i] > coats[i - 1]:
            runs += coats[i] - coats[i - 1]
    return runs

The obvious version

Slice the demand profile horizontally. For each coat level from one up to the deepest demand, scan the path and count the maximal contiguous blocks of sections that still need a coat at that level; each such block is one run. Costs work proportional to the deepest demand times the path length.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_number_operations(coats):
    # Peel the profile one coat-level at a time: at level h, every maximal block
    # of sections still needing coat number h costs one run.
    total = 0
    top = max(coats)
    for level in range(1, top + 1):
        inside = False
        for value in coats:
            if value >= level:
                if not inside:
                    total += 1
                    inside = True
            else:
                inside = False
    return total

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in