1526. Minimum Number of Increments on Subarrays to Form a Target Array

📝 Problem Details

• Title: 1526. Minimum Number of Increments on Subarrays to Form a Target Array
• Link: https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
• Difficulty: Hard
• Tags/Categories: Greedy Dynamic-Programming

input array target input array initial ⇒ all elements initialize to 0 both target and initial have the same size 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 frominitial

Summary:

• we start with an array initial = [0,0, ... , 0] (same size as target)
• in one operation, we can pick any subarray and increment all its values by 1
• we need to find the minimum number of operations to make initial equal to target

💭What Were My Initial Thoughts?

brute force:
- pick the smallest missing value and increment a subarray up to that value
- repeat until all values in initial match target
- this results in many unnecessary subarray operations

optimal approach:
- instead of modifying subarrays explicitly, focus on how each element changes
- every time target[i] is larger than target[i-1], we need extra operations
- the number of operations required is sum of all increases in target

why? each increase corresponds to an independent set of operations

💡 Explanation

Input: target = [3, 1, 5, 4, 2] Output: 7

Index	Target Value	Previous Value	Increment Needed
0	3	0	+3
1	1	3	+0 (No increase)
2	5	1	+4
3	4	5	+0 (No increase)
4	2	4	+0 (No increase)
Total Operations	= 3 + 0 + 4 + 0 + 0 = 7 ✅

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int minNumberOperations(vector<int>& target) {
        int operations = target[0]; // start with the first element
        for(int i = 1; i < target.size(); i++) {
            if(target[i] > target[i-1]) {
                operations += target[i] - target[i-1]; // count only the increases
            }
        }
        return operations;
    }
};