Minimum Number of Increments on Subarrays to Form a Target Array

Minimum Number of Increments on Subarrays to Form a Target Array - Problem

You are given an integer array target. You have an integer array initial of the same size as target with all elements initially zeros.

In one operation you can choose any subarray from initial and increment each value by one.

Return the minimum number of operations to form a target array from initial.

The test cases are generated so that the answer fits in a 32-bit integer.

Input & Output

Example 1 — Basic Mountain Shape

$ Input: target = [1,2,3,2,1]

› Output: 3

💡 Note: We need 3 operations: first element (1), increase to 2 (+1), increase to 3 (+1). Decreases are free since we can extend previous operations.

Example 2 — Multiple Peaks

$ Input: target = [3,1,1,2]

› Output: 4

💡 Note: Start with 3 operations for first element. Then 1≤3 (free), 1=1 (free), 2>1 so add 1 more. Total: 3+0+0+1=4.

Example 3 — Increasing Sequence

$ Input: target = [1,1,2,3]

› Output: 3

💡 Note: First element needs 1 operation. Second is same (free). Then +1 for height 2, +1 for height 3. Total: 1+0+1+1=3.

Constraints

1 ≤ target.length ≤ 10⁵
1 ≤ target[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Target array [3,1,1,2] and initial [0,0,0,0]

Process

Count operations needed: first element + increases only

Output

Minimum operations: 4

Key Takeaway

🎯 Key Insight: Only count upward jumps - you get downward coverage for free from previous operations

Asked in

a Amazon 15 G Google 12

The key insight is to only count increases in the array - decreases are free. The greedy approach counts the first element plus all upward jumps. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Difference Counting	O(n)	O(1)	Count operations by tracking increases between adjacent elements
Brute Force Simulation	O(n × max(target))	O(n)	Simulate the process by finding minimum value and decrementing all elements
Monotonic Stack Approach	O(n)	O(n)	Use stack to track contributing elements and their ranges

Greedy Difference Counting — Algorithm Steps

Add first element to operations (building from 0)
For each subsequent element, if it's larger than previous, add the difference
Sum gives minimum operations needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

First element always counts

Compare

Check if current > previous

Add

Add difference if increase

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* target, int n) {
    int operations = target[0];
    
    for (int i = 1; i < n; i++) {
        if (target[i] > target[i-1]) {
            operations += target[i] - target[i-1];
        }
    }
    
    return operations;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int target[1000];
    int n = 0;
    
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        target[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(target, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

89.0K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Difference Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler