{x}
blog image

Minimum Number of Increments on Subarrays to Form a Target Array

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

Solution Explanation: Minimum Number of Increments on Subarrays

This problem asks for the minimum number of operations needed to transform an array of zeros into a given target array. Each operation involves incrementing all elements within a subarray by 1. A greedy approach and dynamic programming provide efficient solutions.

Approach: Greedy Strategy

The core idea is to focus on the differences between consecutive elements in the target array. Consider the following:

  1. First Element: The first element target[0] requires target[0] operations, since we start with 0.

  2. Subsequent Elements: For each subsequent element target[i], we only need additional operations if it's greater than the previous element target[i-1]. The number of additional operations is simply the difference target[i] - target[i-1]. If it's smaller or equal, no extra operation is needed because we can reuse the increments from previous steps.

This directly leads to a simple linear scan of the array.

Code Implementation (Python)

def minNumberOperations(target: list[int]) -> int:
    """
    Calculates the minimum operations to transform an array of zeros to the target array.
 
    Args:
        target: The target integer array.
 
    Returns:
        The minimum number of operations.
    """
    operations = target[0]  # Operations for the first element
    for i in range(1, len(target)):
        if target[i] > target[i - 1]:
            operations += target[i] - target[i - 1]
    return operations

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the target array. We perform a single pass through the array.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Other Language Implementations

The approach translates easily to other languages. The core logic remains the same: a linear scan comparing consecutive elements and summing the differences where target[i] > target[i-1]. Here are examples in Java and C++:

Java:

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

C++:

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

The time and space complexities remain the same across all these implementations. The greedy strategy efficiently solves the problem without needing complex dynamic programming or other advanced techniques.