Get started

Minimum Number of Increments on Subarrays to Form a Target Array — Medium Problem & Solution

You start with an array of zeros the same length as target. In one operation you may pick any subarray and increment every element in it by one.

Problem statement

You start with an array of zeros the same length as target. In one operation you may pick any subarray and increment every element in it by one.

Return the minimum number of operations needed to turn the zero array into target.

Example 1

Input: target = [1,2,3,2,1]
Output: 3
Explanation: Increment the whole array, then the middle three, then the middle one.

Example 2

Input: target = [3,1,1,2]
Output: 4
Explanation: 3 for the leading peak plus 1 for the final rise.

Example 3

Input: target = [1,1,1,1]
Output: 1
Explanation: One operation over the whole array.

Constraints

  • 1 <= target.length <= 10^5
  • 1 <= target[i] <= 10^5

How to solve Minimum Number of Increments on Subarrays to Form a Target Array

Sweep left to right. The first element needs target[0] operations to start. After that, every time the target rises you must begin target[i] - target[i-1] fresh operations; a fall is free, since operations can just end. The answer is target[0] + Σ max(0, target[i] - target[i-1]).

Approach

  1. Start the total at target[0].
  2. For each later index, add the difference from the previous element when it is positive.

Why it works

Operations are intervals, so the count at any position is the number of intervals covering it. Moving right, the covering count can drop for free — an interval simply ends — but it can only rise by starting new intervals, one per unit of increase. Summing the rises is therefore both necessary and sufficient, which is why the greedy is exactly optimal and no DP is needed.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Falls contribute nothing — using |difference| roughly doubles the answer.
  • The first element is a rise from an implicit 0 and must be counted.
  • The total can reach about 10¹⁰ only if the constraints are loosened; at these bounds it stays inside a 32-bit int.

Reference solution

Python

from typing import List

def minNumberOperations(target: List[int]) -> int:
    total = target[0]
    for i in range(1, len(target)):
        total += max(0, target[i] - target[i - 1])
    return total

JavaScript

var minNumberOperations = function(target) {
    var total = target[0];
    for (var i = 1; i < target.length; i++) {
        if (target[i] > target[i - 1]) total += target[i] - target[i - 1];
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue