You are given an integer array target. Initially you have an array initial of the same size as target with all elements equal to 0. In one operation you can choose any subarray of initial and increment every element in that subarray by 1. Return the minimum number of operations required to convert initial into target.
Example:
For target = [1,2,3,2,1], the answer is 3.
1 <= target.length <= 10^51 <= target[i] <= 10^5- The answer fits into a signed 32-bit integer (per problem statement).
I thought about how the array grows from all zeros. Every time a position i needs to be higher than the previous position i-1, I must perform additional operations specifically to increase that position beyond the previous level. Those extra operations equal the positive difference target[i] - target[i-1]. Also, the very first element target[0] always requires target[0] operations. So the minimum operations are:
target[0] + sum_{i=1..n-1} max(0, target[i] - target[i-1])
This counts each needed rise and ignores falls or equal values because decreases or equal values can be achieved by stopping increments — they don't require new operations.
-
If
targetis empty, return0. -
Initialize
ans = target[0]. -
Iterate
ifrom1ton-1:- If
target[i] > target[i-1], addtarget[i] - target[i-1]toans. - Otherwise do nothing.
- If
-
Return
ans.
This is a single pass algorithm (left-to-right) and uses constant extra memory.
- Plain arrays (input) and primitive variables (counters). No advanced data structures are required.
- We examine adjacent elements to detect positive increases.
- Each positive increase indicates new operations needed to raise that index (and potentially a suffix) above previous heights.
- We accumulate those increases to get the minimum number of operations.
- Time Complexity:
O(n)— we scan the array once, wheren = target.length. - Space Complexity:
O(1)— we only use a fixed number of extra variables (no additional arrays).
#include <vector>
using namespace std;
class Solution {
public:
int minNumberOperations(vector<int>& target) {
if (target.empty()) return 0;
long long ans = target[0]; // operations for the first element
for (int i = 1; i < (int)target.size(); ++i) {
if (target[i] > target[i - 1]) {
ans += (target[i] - target[i - 1]);
}
}
return (int)ans; // fits in 32-bit per problem guarantee
}
};class Solution {
public int minNumberOperations(int[] target) {
if (target == null || target.length == 0) return 0;
long ans = target[0]; // operations required for index 0
for (int i = 1; i < target.length; i++) {
if (target[i] > target[i - 1]) {
ans += (long)(target[i] - target[i - 1]);
}
}
return (int) ans; // fits in 32-bit per problem guarantee
}
}/**
* @param {number[]} target
* @return {number}
*/
var minNumberOperations = function(target) {
if (!target || target.length === 0) return 0;
let ans = target[0];
for (let i = 1; i < target.length; i++) {
if (target[i] > target[i-1]) {
ans += target[i] - target[i-1];
}
}
return ans;
};from typing import List
class Solution:
def minNumberOperations(self, target: List[int]) -> int:
if not target:
return 0
ans = target[0]
for i in range(1, len(target)):
if target[i] > target[i-1]:
ans += target[i] - target[i-1]
return anspackage main
func minNumberOperations(target []int) int {
if len(target) == 0 {
return 0
}
ans := target[0]
for i := 1; i < len(target); i++ {
if target[i] > target[i-1] {
ans += target[i] - target[i-1]
}
}
return ans
}I'll explain as if I'm teaching a friend. I'll use the same logical steps for all languages; the code differences are syntactic.
- I looked at how the
targetarray differs from left to right. - If
target[i]is greater thantarget[i-1], thentarget[i] - target[i-1]new operations are required — because these extra increments must include indexiand cannot be covered by operations that only raised earlier indices. - For the first element
target[0], we needtarget[0]operations from zero.
- Start
ans = target[0] = 1. - i = 1:
2 > 1→ add1→ans = 2. - i = 2:
3 > 2→ add1→ans = 3. - i = 3:
2 <= 3→ add0→ans = 3. - i = 4:
1 <= 2→ add0→ans = 3. - Return
3.
if not target:
return 0 # If input empty — no operations needed.
ans = target[0] # We must raise index 0 from 0 to target[0] with target[0] ops.
for i in range(1, len(target)):
if target[i] > target[i-1]:
ans += target[i] - target[i-1] # Only positive deltas add new ops.
return ans- Each implementation follows the same three steps above. Types and syntax differ by language.
-
target = [1,2,3,2,1]→3Reason:1 + (2-1) + (3-2) = 3. -
target = [3,1,1,2]→4Reason:3 + max(0,1-3) + max(0,1-1) + max(0,2-1) = 3 + 0 + 0 + 1 = 4. -
target = [3,1,5,4,2]→7Reason:3 + 0 + (5-1) + 0 + 0 = 3 + 4 = 7.
- Create
solution.pywith the Python class above. - Add simple test harness:
if __name__ == "__main__":
sol = Solution()
print(sol.minNumberOperations([1,2,3,2,1])) # prints 3- Run
python solution.py.
- Create
solution.jswith the JavaScript function. - Add:
console.log(minNumberOperations([1,2,3,2,1])); // 3- Run
node solution.js.
- Put class into a file and write a
main()to test the method. - Compile with
g++ -std=c++17 -O2 -o run solution.cpp. - Run
./run.
- Put
Solutionclass intoSolution.javawith amainthat tests the method. - Compile:
javac Solution.java. - Run:
java Solution.
- Place function in
main.goand call it frommain. - Build:
go run main.go.
- This solution is already optimal in time and space for the constraints. It is
O(n)time andO(1)space. - The reasoning is equivalent to viewing the target as a skyline: every time the skyline height increases from left to right we pay for that rise.
- Use 64-bit accumulator (e.g.,
long longin C++ orlongin Java) if you worry about intermediate sums — but problem guarantees final answer fits in 32-bit. I usedlong/long longto be safe in code examples.