LeetCode 3366 - Minimum Array Sum

LeetCode Problem 3366

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

We are given an array nums and two different operations that can reduce the values of elements in the array.

The first operation divides a number by 2 and rounds the result upward. This operation can only be used at most op1 times globally, and each array index can receive this operation at most once.

The second operation subtracts k from a number, but it can only be applied if the current value is at least k. This operation can only be used at most op2 times globally, and each index can receive this operation at most once.

An important detail is that both operations may be applied to the same index. Since the operations are not commutative, the order matters. For example:

• Divide then subtract:

• 10 -> ceil(10/2) = 5 -> 5 - 3 = 2

• Subtract then divide:

• 10 -> 10 - 3 = 7 -> ceil(7/2) = 4

These produce different final values, so we must consider both possibilities whenever both operations are used on the same element.

The goal is to minimize the total sum of the array after performing any valid sequence of operations.

The constraints are relatively small:

• nums.length <= 100
• op1 <= 100
• op2 <= 100

This immediately suggests that dynamic programming is feasible. We can afford a state space based on:

• current index
• how many operation 1 usages remain
• how many operation 2 usages remain

A naive brute force solution that tries every possible combination of operations would become exponential because each index has multiple choices:

• do nothing
• use operation 1
• use operation 2
• use both operations in one order
• use both operations in the other order

Important edge cases include:

• k = 0, where subtracting zero changes nothing but still consumes an operation
• values smaller than k, where operation 2 cannot be applied directly
• cases where applying both operations in different orders gives different results
• arrays containing zeros
• situations where operation counts exceed the number of useful indices

Approaches

Brute Force

The brute force solution explores every possible action for every index.

For each element, we could:

• leave it unchanged
• apply operation 1
• apply operation 2 if allowed
• apply operation 1 then operation 2
• apply operation 2 then operation 1

We recursively try every valid combination while tracking remaining operation counts.

This produces the correct answer because it exhaustively explores every legal configuration of operations and chooses the minimum sum among them.

However, the complexity becomes exponential. Each index can branch into up to five possibilities, so the total number of states grows roughly like 5^n, which is far too large when n = 100.

Optimal Dynamic Programming

The key observation is that the effect of decisions on one index is independent from the others except for the remaining counts of operations.

This is a classic resource allocation dynamic programming problem.

For every index, we only need to know:

• how many operation 1 usages remain
• how many operation 2 usages remain

Then we compute the minimum achievable sum for the suffix of the array.

Since there are only:

• n <= 100
• op1 <= 100
• op2 <= 100

the total DP state count is manageable:

100 * 101 * 101 ≈ 1,000,000

At each state we try a constant number of transitions, making the solution efficient enough.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(5^n)	O(n)	Tries every operation combination recursively
Optimal DP	O(n * op1 * op2)	O(n * op1 * op2)	Memoized DP over index and remaining operations

Algorithm Walkthrough

1. Define a recursive DP state.

Let:

dp(i, rem1, rem2)

represent the minimum sum achievable starting from index i, with:

• rem1 remaining uses of operation 1
• rem2 remaining uses of operation 2

2. Define the base case.

If i == len(nums), there are no elements left to process, so the minimum additional sum is 0. 3. Consider doing nothing.

One valid choice is to leave nums[i] unchanged.

Transition:

nums[i] + dp(i + 1, rem1, rem2)

4. Consider using operation 1 only.

If rem1 > 0, we may divide the number by 2 and round upward.

The transformed value is:

$\left\lceil \frac{x}{2} \right\rceil$

In integer arithmetic:

(x + 1) // 2

Transition:

reduced + dp(i + 1, rem1 - 1, rem2)

5. Consider using operation 2 only.

This operation is valid only if nums[i] >= k.

The transformed value becomes:

nums[i] - k

Transition:

reduced + dp(i + 1, rem1, rem2 - 1)

6. Consider using both operations.

Since order matters, we must check both possibilities.

First possibility:

• divide first
• then subtract k if possible

Second possibility:

• subtract first
• then divide

Each valid result becomes another transition candidate. 7. Take the minimum over all valid transitions.

The DP state stores the smallest achievable sum among all choices. 8. Use memoization.

Without memoization, many states repeat exponentially.

Caching ensures each state is computed only once.

Why it works

The algorithm works because every index decision is locally independent except for the remaining counts of operations. The DP state completely captures all information needed for future decisions. Since every valid action is explored exactly once per state, and the minimum over all transitions is stored, the final result is guaranteed to be the global minimum.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def minArraySum(self, nums: List[int], k: int, op1: int, op2: int) -> int:
        n = len(nums)

        @lru_cache(None)
        def dp(index: int, rem1: int, rem2: int) -> int:
            if index == n:
                return 0

            value = nums[index]

            # Option 1: do nothing
            best = value + dp(index + 1, rem1, rem2)

            # Option 2: apply operation 1 only
            if rem1 > 0:
                reduced = (value + 1) // 2
                best = min(
                    best,
                    reduced + dp(index + 1, rem1 - 1, rem2)
                )

            # Option 3: apply operation 2 only
            if rem2 > 0 and value >= k:
                reduced = value - k
                best = min(
                    best,
                    reduced + dp(index + 1, rem1, rem2 - 1)
                )

            # Option 4: operation 1 then operation 2
            if rem1 > 0 and rem2 > 0:
                after_op1 = (value + 1) // 2

                if after_op1 >= k:
                    reduced = after_op1 - k
                    best = min(
                        best,
                        reduced + dp(index + 1, rem1 - 1, rem2 - 1)
                    )

            # Option 5: operation 2 then operation 1
            if rem1 > 0 and rem2 > 0 and value >= k:
                after_op2 = value - k
                reduced = (after_op2 + 1) // 2

                best = min(
                    best,
                    reduced + dp(index + 1, rem1 - 1, rem2 - 1)
                )

            return best

        return dp(0, op1, op2)

The implementation directly mirrors the DP formulation.

The recursive function dp(index, rem1, rem2) computes the minimum suffix sum from the current index onward.

The first transition leaves the current element unchanged.

The next two transitions independently apply operation 1 or operation 2 if enough operations remain.

The final two transitions handle the cases where both operations are used on the same index. Since operation order changes the result, both orders are evaluated separately.

The @lru_cache decorator memoizes states so repeated subproblems are solved only once.

Go Solution

package main

import "math"

func minArraySum(nums []int, k int, op1 int, op2 int) int {
	n := len(nums)

	memo := make([][][]int, n+1)
	visited := make([][][]bool, n+1)

	for i := 0; i <= n; i++ {
		memo[i] = make([][]int, op1+1)
		visited[i] = make([][]bool, op1+1)

		for j := 0; j <= op1; j++ {
			memo[i][j] = make([]int, op2+1)
			visited[i][j] = make([]bool, op2+1)
		}
	}

	var dp func(int, int, int) int

	dp = func(index int, rem1 int, rem2 int) int {
		if index == n {
			return 0
		}

		if visited[index][rem1][rem2] {
			return memo[index][rem1][rem2]
		}

		visited[index][rem1][rem2] = true

		value := nums[index]

		best := value + dp(index+1, rem1, rem2)

		// Operation 1 only
		if rem1 > 0 {
			reduced := (value + 1) / 2

			best = min(
				best,
				reduced+dp(index+1, rem1-1, rem2),
			)
		}

		// Operation 2 only
		if rem2 > 0 && value >= k {
			reduced := value - k

			best = min(
				best,
				reduced+dp(index+1, rem1, rem2-1),
			)
		}

		// Operation 1 then operation 2
		if rem1 > 0 && rem2 > 0 {
			afterOp1 := (value + 1) / 2

			if afterOp1 >= k {
				reduced := afterOp1 - k

				best = min(
					best,
					reduced+dp(index+1, rem1-1, rem2-1),
				)
			}
		}

		// Operation 2 then operation 1
		if rem1 > 0 && rem2 > 0 && value >= k {
			afterOp2 := value - k
			reduced := (afterOp2 + 1) / 2

			best = min(
				best,
				reduced+dp(index+1, rem1-1, rem2-1),
			)
		}

		memo[index][rem1][rem2] = best
		return best
	}

	return dp(0, op1, op2)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation uses explicit 3D memoization arrays because Go does not provide a built in memoization decorator like Python's lru_cache.

A parallel visited array distinguishes computed states from uninitialized states.

All arithmetic safely fits inside Go int because the maximum possible array sum is at most:

100 * 100000 = 10^7

which is well within integer limits.

Worked Examples

Example 1

Input:

nums = [2,8,3,19,3]
k = 3
op1 = 1
op2 = 1

We process each index while tracking remaining operations.

Index	Value	Choice	Resulting Value
0	2	Do nothing	2
1	8	Operation 2	5
2	3	Do nothing	3
3	19	Operation 1	10
4	3	Do nothing	3

Final array:

[2,5,3,10,3]

Final sum:

23

The DP confirms that no alternative allocation of operations produces a smaller sum.

Example 2

Input:

nums = [2,4,3]
k = 3
op1 = 2
op2 = 1

Processing:

Index	Value	Choice	Result
0	2	Operation 1	1
1	4	Operation 1	2
2	3	Operation 2	0

Final array:

[1,2,0]

Final sum:

3

The DP explores all other combinations and determines this is optimal.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * op1 * op2)	Each DP state is computed once with constant transitions
Space	O(n * op1 * op2)	Memoization table stores all states

There are at most:

(n + 1) * (op1 + 1) * (op2 + 1)

distinct DP states.

Each state performs only a constant number of operations, specifically up to five transitions. Therefore the overall runtime is proportional to the number of states.

The memoization cache dominates the space complexity.

Test Cases

from typing import List

class Solution:
    def minArraySum(self, nums: List[int], k: int, op1: int, op2: int) -> int:
        from functools import lru_cache

        n = len(nums)

        @lru_cache(None)
        def dp(i, a, b):
            if i == n:
                return 0

            x = nums[i]

            ans = x + dp(i + 1, a, b)

            if a > 0:
                ans = min(ans, (x + 1) // 2 + dp(i + 1, a - 1, b))

            if b > 0 and x >= k:
                ans = min(ans, x - k + dp(i + 1, a, b - 1))

            if a > 0 and b > 0:
                y = (x + 1) // 2
                if y >= k:
                    ans = min(ans, y - k + dp(i + 1, a - 1, b - 1))

            if a > 0 and b > 0 and x >= k:
                y = x - k
                ans = min(ans, (y + 1) // 2 + dp(i + 1, a - 1, b - 1))

            return ans

        return dp(0, op1, op2)

sol = Solution()

assert sol.minArraySum([2,8,3,19,3], 3, 1, 1) == 23  # provided example 1
assert sol.minArraySum([2,4,3], 3, 2, 1) == 3  # provided example 2

assert sol.minArraySum([10], 3, 1, 1) == 2  # both operations, divide then subtract
assert sol.minArraySum([1], 5, 0, 1) == 1  # operation 2 impossible
assert sol.minArraySum([0,0,0], 1, 3, 3) == 0  # all zeros
assert sol.minArraySum([5], 0, 0, 1) == 5  # subtract zero changes nothing
assert sol.minArraySum([100000], 100000, 1, 1) == 0  # large values
assert sol.minArraySum([7,7,7], 3, 3, 3) == 3  # use both optimally
assert sol.minArraySum([1,2,3], 10, 3, 3) == 4  # only operation 1 useful
assert sol.minArraySum([8], 3, 1, 1) == 1  # subtract then divide is better

Test	Why
[2,8,3,19,3]	Validates provided example
[2,4,3]	Validates provided example
[10]	Confirms both operation orders are checked
[1], k=5	Ensures invalid subtraction is skipped
[0,0,0]	Handles zero values correctly
k=0	Ensures subtracting zero behaves properly
Large value test	Verifies large integer handling
[7,7,7]	Tests repeated combined operations
Large k	Ensures subtraction becomes unusable
[8]	Demonstrates order sensitivity

Edge Cases

One important edge case occurs when nums[i] < k. In this situation, operation 2 cannot legally be applied. A buggy implementation might subtract k anyway and produce negative numbers. The solution explicitly checks value >= k before allowing operation 2 transitions.

Another subtle case occurs when both operations are applied to the same index. The order changes the result because division rounds upward. A common mistake is assuming the operations commute and evaluating only one ordering. The implementation correctly evaluates both:

• operation 1 then operation 2
• operation 2 then operation 1

and chooses the smaller result.

A third edge case appears when k = 0. Subtracting zero does not change the array element, but the operation still consumes one usage. Some implementations may accidentally create infinite loops or redundant transitions. This solution treats operation 2 normally, so the DP remains valid and finite.

Another important corner case is arrays containing zeros. Applying operation 1 to zero still gives zero, and operation 2 may or may not apply depending on k. The transitions naturally handle this without any special casing.

Finally, when operation counts exceed the number of useful indices, the algorithm still works correctly because operations are optional. The DP is free to leave operations unused if they do not improve the sum.