LeetCode Problem 3914

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

LeetCode 3914 - Minimum Operations to Make Array Non Decreasing

Problem Understanding

We are given an array nums. In a single operation, we choose any contiguous subarray and increase every element in that subarray by the same positive integer value x.

The cost of an operation is exactly the chosen value x. If we perform multiple operations, the total cost is the sum of all chosen x values.

Our goal is to make the final array non-decreasing, meaning:

nums[i] <= nums[i + 1]

for every valid index.

The important detail is that the cost depends only on the increment value x, not on the length of the chosen subarray. Increasing a single element by 5 costs the same as increasing an entire suffix by 5.

The array length can be as large as 10^5, and values can be as large as 10^9. These constraints immediately rule out any approach that repeatedly simulates operations or searches through many possible subarrays. We need a linear or near-linear solution.

Several edge cases are worth noting:

• The array may already be non-decreasing, in which case the answer is 0.
• The array may be strictly decreasing.
• Large drops can appear anywhere in the array.
• Since values can reach 10^9, the answer may exceed the range of a 32-bit integer, so a 64-bit result is required.
• The optimal strategy may use long subarrays because increasing many elements together costs no more than increasing one element.

Approaches

Brute Force

A natural way to think about the problem is to repeatedly find positions where:

nums[i] > nums[i + 1]

and perform operations to fix them.

For example, when a drop of size:

nums[i] - nums[i + 1]

is found, we could increase some suffix containing nums[i + 1] until the violation disappears.

The difficulty is that there are infinitely many possible subarrays and increment values. A brute force search would need to explore many choices and simulate their effects. Even a greedy simulation that repeatedly fixes violations can require many operations and becomes too slow for n = 10^5.

While such methods can eventually produce a valid array, they do not provide an efficient way to prove optimality or compute the minimum cost.

Key Insight

Instead of thinking about operations directly, think about how much each position must be increased in the final array.

Let:

inc[i]

be the total amount added to index i.

The final value becomes:

nums[i] + inc[i]

and must satisfy:

nums[i] + inc[i] <= nums[i+1] + inc[i+1]

Rearranging:

inc[i+1] - inc[i] >= nums[i] - nums[i+1]

Now consider what one operation does.

If we add x to a subarray [l..r], then in the increment array inc:

• inc increases by x starting at l
• inc decreases by x after r

This means every operation contributes exactly x to a positive jump in the increment profile.

The total cost therefore equals the sum of all positive increases in inc.

To minimize cost, we want the smallest increment array satisfying all constraints.

Scanning from left to right, whenever:

nums[i] > nums[i+1]

we need at least:

nums[i] - nums[i+1]

more increment at position i+1 than at position i.

Each such required increase contributes directly to the answer.

Therefore:

answer = Σ max(0, nums[i] - nums[i+1])

This remarkably simple formula gives the minimum total cost.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential or worse	Large	Explores many subarray choices and operations
Optimal	O(n)	O(1)	Sum all adjacent decreases

Algorithm Walkthrough

1. Initialize answer = 0.
2. Iterate through every adjacent pair of elements.
3. For each index i, compare nums[i] and nums[i+1].
4. If nums[i] <= nums[i+1], no additional cost is required because this pair already satisfies the non-decreasing condition.
5. If nums[i] > nums[i+1], compute the deficit:

deficit = nums[i] - nums[i+1]

This is the minimum amount by which the cumulative increment must increase when moving from position i to position i+1. 6. Add this deficit to the answer. 7. After processing all adjacent pairs, return the accumulated answer.

Why it works

Let inc[i] denote the total increase applied to position i. The final array must satisfy:

inc[i+1] - inc[i] >= nums[i] - nums[i+1]

for every adjacent pair.

The total operation cost is exactly the sum of positive jumps in the increment sequence. Therefore, whenever nums[i] > nums[i+1], we must pay at least nums[i] - nums[i+1]. These requirements are independent and can be achieved exactly, so the minimum total cost is the sum of all adjacent decreases. Since the algorithm computes precisely this quantity, it is optimal.

Python Solution

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        answer = 0

        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                answer += nums[i] - nums[i + 1]

        return answer

The implementation directly follows the mathematical observation.

The variable answer stores the minimum total cost. We scan every adjacent pair once. Whenever a decrease is encountered, we add the size of that decrease to the answer. If the pair is already non-decreasing, no contribution is needed.

Since every adjacent pair is processed exactly once and no extra data structures are required, the implementation is both simple and efficient.

Go Solution

func minOperations(nums []int) int64 {
    var answer int64 = 0

    for i := 0; i < len(nums)-1; i++ {
        if nums[i] > nums[i+1] {
            answer += int64(nums[i] - nums[i+1])
        }
    }

    return answer
}

The Go implementation is identical in logic to the Python version.

The main difference is that the return type is int64. The sum of all decreases can exceed the range of a 32-bit integer when n is large and values approach 10^9, so using int64 guarantees correctness.

Worked Examples

Example 1

nums = [3, 3, 2, 1]

i	nums[i]	nums[i+1]	Decrease	Answer
0	3	3	0	0
1	3	2	1	1
2	2	1	1	2

Final answer:

2

This matches the example.

Example 2

nums = [5, 1, 2, 3]

i	nums[i]	nums[i+1]	Decrease	Answer
0	5	1	4	4
1	1	2	0	4
2	2	3	0	4

Final answer:

4

This matches the example.

Additional Example

nums = [7, 4, 6, 2]

i	nums[i]	nums[i+1]	Decrease	Running Answer
0	7	4	3	3
1	4	6	0	3
2	6	2	4	7

Result:

7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass through the array
Space	O(1)	Only a few variables are used

The algorithm performs a single linear scan of the input. Each adjacent pair contributes at most one constant-time calculation. No auxiliary arrays, stacks, queues, or hash maps are needed, so the extra memory usage remains constant.

Test Cases

sol = Solution()

assert sol.minOperations([3, 3, 2, 1]) == 2      # provided example 1
assert sol.minOperations([5, 1, 2, 3]) == 4      # provided example 2

assert sol.minOperations([1]) == 0               # single element
assert sol.minOperations([1, 2, 3, 4]) == 0      # already non-decreasing
assert sol.minOperations([4, 3, 2, 1]) == 3      # strictly decreasing

assert sol.minOperations([5, 5, 5, 5]) == 0      # all equal
assert sol.minOperations([10, 1]) == 9           # single large drop

assert sol.minOperations([7, 4, 6, 2]) == 7      # multiple decreases
assert sol.minOperations([8, 3, 5, 1, 7]) == 9   # alternating pattern

assert sol.minOperations([10**9, 1]) == 999999999  # large values
assert sol.minOperations([100, 1, 100, 1]) == 198  # repeated large drops

Test Summary

Test	Why
[3,3,2,1]	Verifies example 1
[5,1,2,3]	Verifies example 2
[1]	Minimum array size
[1,2,3,4]	Already valid array
[4,3,2,1]	Strictly decreasing sequence
[5,5,5,5]	Equal values throughout
[10,1]	Single adjacent decrease
[7,4,6,2]	Multiple independent decreases
[8,3,5,1,7]	Mixed increasing and decreasing sections
[10^9,1]	Large value handling
[100,1,100,1]	Multiple large deficits

Edge Cases

Single Element Array

When n = 1, there are no adjacent pairs to check. A single element is always non-decreasing by definition. The loop executes zero times and the algorithm correctly returns 0.

Already Non-Decreasing Array

Consider an array such as [1, 2, 2, 5]. Every adjacent pair already satisfies the required ordering. No decreases are encountered during the scan, so the answer remains 0. This correctly reflects that no operations are necessary.

Strictly Decreasing Array

For an array like [4, 3, 2, 1], every adjacent pair contributes to the answer. The algorithm sums all decreases:

(4 - 3) + (3 - 2) + (2 - 1) = 3

This is exactly the minimum cost required to build enough increment difference between consecutive positions.

Very Large Values

Because nums[i] may be as large as 10^9 and there can be up to 10^5 elements, the final answer can exceed 32-bit integer limits. The Python implementation naturally supports arbitrary-sized integers, while the Go implementation uses int64 to safely store the result.