0207HardArrayGreedy

Pipeline Patrol Walks

Tracked in this browser only

Trains the technique from

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 pipeline runs past n inspection posts laid out in a single line and numbered from left to right. risk[i] is the hazard score logged at post i.

A shift plan hands every post a whole number of walk-throughs. Such a plan is signed off only when both of these hold:

No post is skipped: each one receives at least one walk-through.
Wherever a post's hazard score beats the score of a post standing immediately beside it, the plan hands that post strictly more walk-throughs than it hands the lower-scoring neighbour.

Two posts side by side on the same score place no requirement on each other.

Return the smallest total number of walk-throughs a signed-off plan can use.

Examples

Example 1

Input: risk = [3, 5, 5, 2]
Output: 6

The plan 1, 2, 2, 1 is signed off: post 1 beats post 0 and walks more than it, post 2 beats post 3 and walks more than it, and posts 1 and 2 share a score so neither owes the other anything. The walk-throughs add up to 6.

Example 2

Input: risk = [8, 6, 4]
Output: 6

Under the plan 3, 2, 1 post 0 walks more often than post 1 and post 1 walks more often than post 2, each of which it outscores, and no post drops below one walk-through. The total is 6.

Example 3

Input: risk = [2, 7, 9, 4]
Output: 7

Take the plan 1, 2, 3, 1. Posts 1 and 2 each beat the post on their left and walk once more than it, while post 3 sits below post 2 in score and takes a single walk-through. Total 7.

Example 4

Input: risk = [0, 0, 0]
Output: 3

All three scores match, so no post owes another extra walk-throughs, and the plan 1, 1, 1 clears both rules with a total of 3.

Constraints

n == risk.length
1 <= n <= 5 * 10^4
0 <= risk[i] <= 5 * 10^4

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_patrol_walks(risk: list[int]) -> int:

Java

public int minPatrolWalks(int[] risk)

The intended approach

Time O(n)Space O(n) for the walk-count array

Start every post at one walk-through and settle the two directions in separate sweeps over a walk-count array. Going left to right, a post that outscores the post on its left is set to one above that neighbour, which clears every obligation pointing leftward. Going back right to left, a post that outscores the post on its right is raised to one above that neighbour only if it is not already ahead of it, so the count earned in the first sweep is never lowered. Both sweeps read the whole array; summing it gives the total.

Pythonentry point: min_patrol_walks

def min_patrol_walks(risk):
    # Time O(n): two linear sweeps plus one sum.
    # Space O(n) for the walk-count array that is built and summed.
    n = len(risk)
    walks = [1] * n
    for i in range(1, n):
        if risk[i] > risk[i - 1]:
            walks[i] = walks[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if risk[i] > risk[i + 1] and walks[i] <= walks[i + 1]:
            walks[i] = walks[i + 1] + 1
    return sum(walks)

The obvious version

Set every post to one walk-through, then repeatedly scan the line and bump any post that is not strictly ahead of a lower-scoring neighbour, stopping when a full scan changes nothing. Each bump is forced, so the fixed point reached is the cheapest signed-off plan. O(n^2) scans in the worst case.

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_patrol_walks(risk):
    n = len(risk)
    walks = [1] * n
    settled = False
    while not settled:
        settled = True
        for i in range(n):
            if i > 0 and risk[i] > risk[i - 1] and walks[i] <= walks[i - 1]:
                walks[i] = walks[i - 1] + 1
                settled = False
            if i + 1 < n and risk[i] > risk[i + 1] and walks[i] <= walks[i + 1]:
                walks[i] = walks[i + 1] + 1
                settled = False
    return sum(walks)

How this problem was checked

Reference solution executed against 21 test cases — 21 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