# Minimum Number of Increments on Subarrays to Form a Target Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Dream11](https://scaleengineer.com/companies/dream11)
---
## 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.

**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
## Brute-Force Simulation
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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.

## Divide and Conquer with Linear Scan
This approach views the problem recursively. For any given subarray, the number of operations that must be applied to the *entire* subarray is determined by its minimum value. We can apply this number of operations, and then solve the remaining parts (to the left and right of the minimum) as independent subproblems.
**Time:** O(N^2) in the worst case. The recursion tree can be skewed, leading to a recursion depth of N. At each of the N levels, we perform a linear scan (up to O(N)) to find the minimum. This gives a recurrence `T(N) = O(N) + T(N-1)`, which resolves to O(N^2). · **Space:** O(N) for the recursion stack in the worst case (e.g., a sorted `target` array), where N is the length of the array.
**Pros:** It's a more structured approach than simulation and correctly identifies the recursive nature of the problem.; It forms the basis for a more optimized solution.
**Cons:** The O(N^2) time complexity is too slow for the given constraints and will result in a Time Limit Exceeded error.; The recursion depth can go up to N, potentially causing a stack overflow for large N.
### Explanation
We can define a recursive function `solve(l, r, base)` that calculates the minimum operations for the subarray `target[l...r]`, given that `base` operations have already been applied to it. The base case is an empty range (`l > r`), which requires 0 operations. In the recursive step, we find the minimum value `min_val` in `target[l...r]`. The number of operations we can apply to the whole subarray `[l, r]` is `min_val - base`. After this, the problem splits into two independent subproblems at the index of the minimum, `min_idx`: one for the left part `[l, min_idx - 1]` and one for the right part `[min_idx + 1, r]`. The base for these new subproblems is now `min_val`. The total operations is the sum of operations from these three parts. The bottleneck is finding the minimum in each step, which takes a linear scan of the current subarray.

```java
class Solution {
    public int minNumberOperations(int[] target) {
        return solve(target, 0, target.length - 1, 0);
    }

    private int solve(int[] target, int l, int r, int base) {
        if (l > r) {
            return 0;
        }

        int minIdx = l;
        for (int i = l + 1; i <= r; i++) {
            if (target[i] < target[minIdx]) {
                minIdx = i;
            }
        }

        int minVal = target[minIdx];
        int operations = minVal - base;
        
        operations += solve(target, l, minIdx - 1, minVal);
        operations += solve(target, minIdx + 1, r, minVal);
        
        return operations;
    }
}
```
### Algorithm
*   Define a recursive function, e.g., `solve(l, r, base)`, that computes the operations for `target[l...r]` assuming `base` operations have already been applied uniformly.
*   **Base Case:** If `l > r`, the range is empty, so return 0.
*   **Recursive Step:**
    *   Linearly scan the subarray `target[l...r]` to find the minimum value `min_val` and its index `min_idx`.
    *   The number of new operations that can be applied across this entire subarray is `min_val - base`.
    *   The problem is now split at `min_idx`. The elements at `min_idx` are at their target height relative to the subproblem. The new base for the subproblems becomes `min_val`.
    *   The total operations are `(min_val - base) + solve(l, min_idx - 1, min_val) + solve(min_idx + 1, r, min_val)`.
*   The initial call is `solve(0, n-1, 0)`.

## Divide and Conquer with Range Minimum Query
This is an optimization of the previous Divide and Conquer approach. The bottleneck of finding the minimum element in a subarray via linear scan is addressed by pre-processing the array to answer Range Minimum Queries (RMQ) efficiently. A Segment Tree can find the minimum in any subarray in logarithmic time.
**Time:** O(N log N). Building the Segment Tree takes O(N). The total work across all recursive calls is the sum of O(log N) queries. Since there are O(N) subproblems created, the total time is O(N log N). · **Space:** O(N). This is for the Segment Tree (which typically takes O(N) space) and the recursion stack (which can be O(N) in the worst case).
**Pros:** Significantly faster than the O(N^2) approach, with O(N log N) complexity.; Efficient enough to pass the time limits for the given constraints.
**Cons:** Implementation is more complex due to the need for a Segment Tree or a similar data structure.; While efficient, it's still not the optimal solution in terms of simplicity and constant factors.
### Explanation
The logic is identical to the previous Divide and Conquer approach, but we optimize the step of finding the minimum. We first build a Segment Tree over the `target` array in O(N) time. This tree allows us to find the minimum value and its index in any range `[l, r]` in O(log N) time. Inside our recursive function `solve(l, r, base)`, we replace the O(N) linear scan with an O(log N) query to the Segment Tree. This significantly improves the overall time complexity.

```java
// The recursive structure is the same, but the min-finding part is optimized.
class Solution {
    // Assume a SegmentTree class is implemented and an instance `st` is available.
    // st.query(l, r) returns a pair {minValue, minIndex}.
    private int[] target;
    // private SegmentTree st;

    public int minNumberOperations(int[] target) {
        this.target = target;
        // this.st = new SegmentTree(target); // O(N) build time
        return solve(0, target.length - 1, 0);
    }

    private int solve(int l, int r, int base) {
        if (l > r) {
            return 0;
        }

        // This part is now O(log N) instead of O(r - l + 1)
        // Pair<Integer, Integer> minInfo = st.query(l, r);
        // int minVal = minInfo.getKey();
        // int minIdx = minInfo.getValue();
        
        // For demonstration, we show the linear scan version, but in this approach,
        // it would be replaced by a fast query.
        int minIdx = l;
        for (int i = l + 1; i <= r; i++) {
            if (target[i] < target[minIdx]) {
                minIdx = i;
            }
        }
        int minVal = target[minIdx];

        int operations = minVal - base;
        operations += solve(l, minIdx - 1, minVal);
        operations += solve(minIdx + 1, r, minVal);
        return operations;
    }
}
```
### Algorithm
*   The overall recursive structure `solve(l, r, base)` is the same as the previous approach.
*   **Preprocessing:** Before starting the recursion, build a data structure, like a Segment Tree, on the `target` array. This takes O(N) time and will allow for efficient Range Minimum Queries (RMQ).
*   **Recursive Step:**
    *   Instead of a linear scan, query the Segment Tree for the minimum value `min_val` and its index `min_idx` in the range `[l, r]`. This query takes O(log N) time.
    *   The rest of the logic remains identical: calculate operations for the current segment and recurse on the left and right subproblems.
*   The initial call is `solve(0, n-1, 0)` after the Segment Tree is built.

## Greedy Linear Scan
This highly efficient approach is based on a greedy insight. By scanning the array from left to right, we can determine the total number of operations by only considering the increases in the target values. The total number of operations is simply the value of the first element plus the sum of all positive differences between adjacent elements.
**Time:** O(N), where N is the length of the `target` array, because we perform a single pass through the array. · **Space:** O(1), as we only use a few variables to keep track of the total operations and iterate through the array.
**Pros:** Optimal solution with linear time complexity.; Extremely space-efficient, using only constant extra space.; Simple and easy to implement.
**Cons:** The logic, while simple, might not be immediately intuitive. It requires a shift in perspective from building the array to counting the start of new operations.
### Explanation
The core idea is to count the number of times we must start a new increment operation. An operation on a subarray `[i, j]` can be thought of as a continuous block of height 1. The total number of operations is the sum of these blocks.

When we are at index `i`, the value `target[i]` must be reached. The operations that were applied to index `i-1` might carry over to index `i`. Specifically, if `target[i] > target[i-1]`, it means the `target[i-1]` operations that were active at `i-1` are not enough for `target[i]`. We need to introduce `target[i] - target[i-1]` new operations that cover index `i`. If `target[i] <= target[i-1]`, the operations active at `i-1` are sufficient. Therefore, we only need to add to our total count when the target value increases.

The total operations will be `target[0]` (to build the first bar) plus the sum of `target[i] - target[i-1]` for all `i` where `target[i] > target[i-1]`.

```java
class Solution {
    public int minNumberOperations(int[] target) {
        if (target == null || target.length == 0) {
            return 0;
        }
        
        // The first element requires target[0] operations starting from 0.
        int operations = target[0];
        
        // Iterate from the second element
        for (int i = 1; i < target.length; i++) {
            // If the current element is greater than the previous one,
            // we need additional operations equal to the difference.
            if (target[i] > target[i-1]) {
                operations += target[i] - target[i-1];
            }
        }
        
        return operations;
    }
}
```
### Algorithm
*   Initialize a variable `operations` with the value of the first element, `target[0]`. This is because we must perform `target[0]` operations to raise the first element from 0.
*   Iterate through the `target` array from the second element (`i = 1`) to the end.
*   For each element `target[i]`, compare it with the previous element `target[i-1]`.
*   If `target[i] > target[i-1]`, it means we need more operations than were needed for the previous element. The number of additional operations required is `target[i] - target[i-1]`. Add this difference to the `operations` count.
*   If `target[i] <= target[i-1]`, the operations already accounted for are sufficient to cover `target[i]`, so no new operations are needed.
*   After the loop, return the total `operations`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minNumberOperations(vector<int> &target) {
    int f = target[0];
    for (int i = 1; i < target.size(); ++i) {
      if (target[i] > target[i - 1]) {
        f += target[i] - target[i - 1];
      }
    }
    return f;
  }
};

```

### Python

```python
class Solution:
    def minNumberOperations(self, target: List[int]) -> int: return target[0] + sum(
        max(0, b - a) for a, b in pairwise(target))

```