Scale Engineer

Minimum Number of Increments on Subarrays to Form a Target Array

Hard
#1407Time: O(A * N), where N is the length of the array and `A` is the total number of operations (the final answer). In each of the `A` operations, we may scan the array to find a subarray to increment, which takes O(N) time. Since `A` can be large, this approach is very slow.Space: O(N), where N is the length of the `target` array. This space is required to store the `current` array.1 company
Patterns
Dynamic ProgrammingGreedy
Data structures
ArrayStackMonotonic Stack
Companies
Dream11

Prompt

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.

 

Example 1:

Input: target = [1,2,3,2,1]
Output: 3
Explanation: We need at least 3 operations to form the target array from the initial array.
[0,0,0,0,0] increment 1 from index 0 to 4 (inclusive).
[1,1,1,1,1] increment 1 from index 1 to 3 (inclusive).
[1,2,2,2,1] increment 1 at index 2.
[1,2,3,2,1] target array is formed.

Example 2:

Input: target = [3,1,1,2]
Output: 4
Explanation: [0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2]

Example 3:

Input: target = [3,1,5,4,2]
Output: 7
Explanation: [0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2].

 

Constraints:

  • 1 <= target.length <= 105
  • 1 <= target[i] <= 105

Approaches

4 approaches with complexity analysis and trade-offs.

This approach directly simulates the process of building the target array. We start with an array of zeros and repeatedly find a segment that is still below the target values and increment it. This process continues until our array matches the target array.

Algorithm

  • Initialize a current array of the same size as target with all zeros.
  • Initialize an operations counter to 0.
  • Enter a loop that continues as long as the current array does not match the target array.
  • Inside the loop, increment the operations counter.
  • Find the first index i where current[i] is less than target[i].
  • From this index i, find a continuous subarray [i, j] where current[k] < target[k] for all k in this range.
  • Increment every element in the current array within the subarray [i, j] by one.
  • Once the loop terminates (i.e., current equals target), return the total operations count.

Walkthrough

We maintain a current array, initialized to all zeros, representing the state of our array at any point. We also keep a counter for the number of operations. In a loop, we check if current is equal to target. If not, we perform one operation: we find the first index i from the left where current[i] < target[i]. Then, we increment current[i] and continue incrementing subsequent elements current[j] as long as they are also less than their corresponding target[j] values. This constitutes one operation on a subarray. We increment our operation counter and repeat the process until current matches target.

class Solution {    public int minNumberOperations(int[] target) {        int n = target.length;        int operations = 0;        int[] current = new int[n];                while (true) {            boolean done = true;            for(int val : current) {                if (val == 0) {                    // This check is just to find if we need to start. A better check is needed.                }            }            if (java.util.Arrays.equals(current, target)) {                break;            }                        operations++;            int i = 0;            // Find the start of a segment that needs incrementing            while (i < n && current[i] >= target[i]) {                i++;            }                        // Increment the segment            int j = i;            while (j < n && current[j] < target[j]) {                current[j]++;                j++;            }        }        return operations;    }}

Complexity

Time

O(A * N), where N is the length of the array and `A` is the total number of operations (the final answer). In each of the `A` operations, we may scan the array to find a subarray to increment, which takes O(N) time. Since `A` can be large, this approach is very slow.

Space

O(N), where N is the length of the `target` array. This space is required to store the `current` array.

Trade-offs

Pros

  • Conceptually simple and directly models the problem description.

Cons

  • Extremely inefficient, especially for large inputs.

  • The time complexity depends on the final answer A, which can be very large, leading to a Time Limit Exceeded error on most platforms.

Solutions

class Solution {public  int minNumberOperations(int[] target) {    int f = target[0];    for (int i = 1; i < target.length; ++i) {      if (target[i] > target[i - 1]) {        f += target[i] - target[i - 1];      }    }    return f;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem