Minimum Number of Increments on Subarrays to Form a Target Array

We can take a greedy approach to solving this question; realise that at the index position i, we only have to increment a subarray that starts at index i if the previous value, target[i-1], was smaller.

code

class Solution {
public:
    int minNumberOperations(vector<int>& target) {
        int ans = 0, prev = 0;

        for (int& t : target) {
            if (prev < t) {
                ans += t-prev;
            }
            prev = t;
        }

        return ans;
    }
};

complexity

• Time: O(n) where n denotes the number of elements inside of target
• Space: O(1)

time taken

1 minute and 53 seconds