LeetCode 3500 - Minimum Cost to Divide Array Into Subarrays

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Prefix Sum

Solution

Problem Understanding

This problem asks us to partition an array nums into contiguous subarrays, where each subarray contributes a weighted cost to the total. The cost for a subarray nums[l..r] depends on two components: the sum of the elements in the subarray, adjusted by a factor k multiplied by the order of the subarray, and the sum of corresponding elements in the cost array. Specifically, the cost formula is:

(subarray sum of nums + k * subarray_index) * (subarray sum of cost)

The goal is to divide nums optimally into subarrays to minimize the total cost. The input includes two arrays of length up to 1000, and the integer k is also up to 1000. These constraints allow an algorithm up to roughly O(n^2) time, but anything worse may be too slow.

Important edge cases include when nums has only one element, or when splitting into multiple subarrays provides a lower cost than keeping a single subarray. The problem guarantees that nums and cost have the same length and contain only positive integers, which simplifies the arithmetic.

Approaches

Brute-Force

A brute-force solution would try all possible partitions of the array. For each partition, compute the cost of each subarray and sum them. This guarantees correctness because it explores every valid division, but the number of partitions of an array of length n is exponential (2^(n-1)), making this approach infeasible for n = 1000.

Optimal Approach

The key observation is that the problem has overlapping subproblems and an optimal substructure, which makes it suitable for dynamic programming. We can define a DP array dp[i] representing the minimum cost for the first i elements of nums. To compute dp[i], we iterate over all possible previous partition points j < i and compute the cost of the subarray nums[j..i-1] added to dp[j]. Using prefix sums for nums and cost allows constant-time computation of subarray sums. This reduces the naive computation per subarray from O(n) to O(1).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Generates all partitions and sums costs
Dynamic Programming	O(n^2)	O(n)	Uses prefix sums to compute subarray costs efficiently

Algorithm Walkthrough

Compute prefix sums for nums and cost arrays. Let prefixNums[i] be the sum of nums[0..i-1] and prefixCost[i] be the sum of cost[0..i-1].
Initialize a DP array dp of size n+1 where dp[0] = 0 (no elements, zero cost).
For each index i from 1 to n, iterate over all possible previous partition points j from 0 to i-1:

a. Compute the sum of nums[j..i-1] as prefixNums[i] - prefixNums[j].

b. Compute the sum of cost[j..i-1] as prefixCost[i] - prefixCost[j].

c. Compute the subarray cost using the formula (prefixNums[i] - prefixNums[j] + k * (subarray_order)) * (prefixCost[i] - prefixCost[j]). Here subarray_order is determined by the number of subarrays ending at position j, which can be tracked implicitly in dp.

d. Update dp[i] to the minimum of its current value and dp[j] + subarray_cost. 4. Return dp[n] as the minimum total cost.

Why it works: The DP array keeps the minimal cost for all prefixes of the array. Since every partition point is considered, the DP approach finds the global minimum while reusing previously computed results for efficiency. The problem requires partitioning an array nums into contiguous subarrays in such a way that the total cost of all subarrays is minimized. Each subarray's cost depends on two components: the sum of its nums elements up to its end index, adjusted by the order of the subarray multiplied by k, and the sum of the corresponding cost elements. Specifically, the cost of the subarray [nums[l..r]] is:

$$(\sum_{j=0}^{r} nums[j] + k \cdot i) \cdot (\sum_{j=l}^{r} cost[j])$$

where i is the 1-based index of the subarray. The goal is to choose a division of nums that minimizes the sum of all subarray costs.

The input consists of two integer arrays nums and cost of equal length (up to 1000 elements), and an integer k in the range 1 to 1000. Each element in nums and cost is also bounded between 1 and 1000. The problem guarantees at least one element, so no empty array concerns arise.

Edge cases to consider include:

The array has only one element, so only one subarray is possible.
All elements are identical, which may make multiple partitions equivalent.
The value of k is large relative to the sums of nums, which may heavily favor fewer subarrays.

Approaches

Brute Force

A brute-force approach enumerates all possible ways to partition the array. For an array of length n, there are $2^{n-1}$ possible divisions because each of the n-1 gaps can either be a cut or not. For each partition, we compute the subarray costs according to the formula and sum them. This guarantees correctness because it evaluates every possible partition.

However, this approach is prohibitively slow for $n \leq 1000$ because $2^{999}$ is far beyond feasible computation. Therefore, it is not viable.

Optimal Approach

The key observation is that the problem exhibits overlapping subproblems and optimal substructure. Specifically, the cost of dividing the first j elements depends only on the partition of elements before j and the choice of the last subarray ending at j. This suggests a dynamic programming (DP) approach.

Let dp[i] represent the minimum cost to partition the first i elements. For each i, we consider all possible previous subarray ends j (where 0 <= j < i) and compute:

$$dp[i] = \min_{0 \le j < i} { dp[j] + (\text{prefixSum}[i] - \text{prefixSum}[j] + k \cdot (\text{count of subarrays})) \cdot (\text{prefixCost}[i] - \text{prefixCost}[j]) }$$

Here, prefixSum and prefixCost are prefix sums for nums and cost, allowing O(1) subarray sum computation. The number of subarrays is incremented by 1 for each new subarray.

Dynamic programming reduces the time complexity to O(n²), which is acceptable for $n \le 1000$.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Enumerate all partitions, infeasible for n=1000
Optimal (DP with prefix sums)	O(n²)	O(n)	Uses prefix sums for O(1) subarray cost, iterates over all subarray ends

Algorithm Walkthrough

Compute prefixSum and prefixCost, where prefixSum[i] is the sum of nums[0..i-1] and prefixCost[i] is the sum of cost[0..i-1]. This allows O(1) computation of any subarray sum as prefixSum[r+1] - prefixSum[l] and similarly for cost.
Initialize a DP array dp of size n+1 where dp[i] represents the minimum cost to partition the first i elements. Set dp[0] = 0 because zero elements have zero cost.
For each index i from 1 to n, consider all possible previous cut positions j from 0 to i-1. Compute the cost of forming a subarray from nums[j..i-1] using the formula:

$$(\text{prefixSum}[i] - \text{prefixSum}[0..j] + k \cdot (\text{number of subarrays})) \cdot (\text{prefixCost}[i] - \text{prefixCost}[j])$$

Increment the subarray count appropriately.

Update dp[i] to the minimum of its current value and dp[j] + cost(j, i-1).
After filling dp, dp[n] contains the minimum total cost.

Why it works: The DP array maintains the invariant that dp[i] is the minimum cost for the first i elements. Each step considers all valid subarray endings, ensuring that no optimal partition is missed. Using prefix sums guarantees constant-time subarray sum computation, preserving correctness while improving efficiency.

Python Solution

from typing import List

class Solution:
    def minimumCost(self, nums: List[int], cost: List[int], k: int) -> int:
        n = len(nums)
        prefixNums = [0] * (n + 1)
        prefixCost = [0] * (n + 1)
        
        for i in range(n):
            prefixNums[i + 1] = prefixNums[i] + nums[i]
            prefixCost[i + 1] = prefixCost[i] + cost[i]
        prefix_sum = [0] * (n + 1)
        prefix_cost = [0] * (n + 1)
        
        for i in range(n):
            prefix_sum[i+1] = prefix_sum[i] + nums[i]
            prefix_cost[i+1] = prefix_cost[i] + cost[i]
        
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for i in range(1, n + 1):
            for j in range(i):
                num_sum = prefixNums[i] - prefixNums[j]
                cost_sum = prefixCost[i] - prefixCost[j]
                subarray_order = 1  # Minimal order in DP formulation
                dp[i] = min(dp[i], dp[j] + (num_sum + k * (i - j)) * cost_sum)
                subarray_sum = prefix_sum[i] - prefix_sum[j]
                subarray_cost = prefix_cost[i] - prefix_cost[j]
                num_subarrays = 1  # the last subarray's order is unknown, handled in the formula
                dp[i] = min(dp[i], dp[j] + (prefix_sum[i] + k * (i - j)) * subarray_cost)
        
        return dp[n]

In this implementation, prefix sums allow efficient calculation of subarray sums. The nested loops iterate over all possible previous partition points, ensuring we consider every valid division. dp[i] stores the minimum cost for the first i elements, and the final answer is dp[n]. The implementation first constructs prefix sums for nums and cost to allow O(1) computation of subarray sums. The nested loop fills the DP array by considering all previous partition points, updating the minimum cost for each i. The formula (prefix_sum[i] + k * (i - j)) * subarray_cost corresponds directly to the problem statement for the last subarray in the current partition.

Go Solution

func minimumCost(nums []int, cost []int, k int) int64 {
    n := len(nums)
    prefixNums := make([]int, n+1)
    prefixCost := make([]int, n+1)
    
    for i := 0; i < n; i++ {
        prefixNums[i+1] = prefixNums[i] + nums[i]
        prefixCost[i+1] = prefixCost[i] + cost[i]
    }
    
    dp := make([]int64, n+1)
    for i := range dp {
        dp[i] = 1<<63 - 1 // Max int64
    }
    dp[0] = 0
    
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            numSum := prefixNums[i] - prefixNums[j]
            costSum := prefixCost[i] - prefixCost[j]
            subCost := int64(numSum + k*(i-j)) * int64(costSum)
            if dp[j]+subCost < dp[i] {
                dp[i] = dp[j] + subCost
            }
    prefixSum := make([]int64, n+1)
    prefixCost := make([]int64, n+1)
    
    for i := 0; i < n; i++ {
        prefixSum[i+1] = prefixSum[i] + int64(nums[i])
        prefixCost[i+1] = prefixCost[i] + int64(cost[i])
    }
    
    dp := make([]int64, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = 1<<62
    }
    
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            subSum := prefixSum[i] - prefixSum[j]
            subCost := prefixCost[i] - prefixCost[j]
            dp[i] = min(dp[i], dp[j]+(prefixSum[i]+int64(k)*(int64(i-j)))*subCost)
        }
    }
    
    return dp[n]
}

In Go, we handle integer overflow carefully by using int64 for the DP array and intermediate products. The logic mirrors the Python solution, with prefix sums and DP updates in nested loops.

Worked Examples

Example 1: nums = [3,1,4], cost = [4,6,6], k = 1

i	j	num_sum	cost_sum	subarray_cost	dp[i]
1	0	3	4	(3+11)4=16	16
2	0	4	10	(4+12)10=60	60
2	1	1	6	(1+11)6=12	28
3	0	8	16	(8+13)16=176	176
3	1	5	12	(5+12)12=84	44
3	2	4	6	(4+11)6=30	74

The minimum total cost is 110.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Two nested loops over n elements, subarray sum via prefix sums in O(1)
Space	O(n)	Prefix sums and DP array of size n+1

Since n ≤ 1000, O(n^2) operations are feasible (~1 million iterations).

Test Cases

# Provided examples
assert Solution().minimumCost([3,1,4], [4,6,6], 1) == 110  # Example 1
assert Solution().minimumCost([4,8,5,1,14,2,2,12,1], [7,2,8,4,2,2,1,1,2], 7) == 985  # Example 2

# Edge cases
assert Solution().minimumCost([1], [1], 1) == 2  # Single element
assert Solution().minimumCost([1,2], [1,1], 1) == 8  # Minimal partition
assert Solution().minimumCost([1,1,1,1], [1,1,1,1], 1) == 16  # All equal elements

Test	Why
Single element	Edge case with minimal input
Minimal partition	Verifies splitting works correctly
All equal

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


In Go, we handle integer overflow by using `int64` throughout. The prefix sums are arrays of `int64` to avoid exceeding 32-bit limits. The DP array is initialized to a very large number (`1<<62`) to simulate infinity. The rest of the logic mirrors the Python solution.

## Worked Examples

### Example 1

Input: `nums = [3,1,4], cost = [4,6,6], k = 1`

Compute prefix sums:

| i | prefixSum | prefixCost |
| --- | --- | --- |
| 0 | 0 | 0 |
| 1 | 3 | 4 |
| 2 | 4 | 10 |
| 3 | 8 | 16 |

Compute DP:

- `i = 1`: `dp[1] = (3 + 1*1)*4 = 16`
- `i = 2`: consider j=0: `(4 + 1*2)*10 = 60`; j=1: `(1+?)*?` → minimum `50`
- `i = 3`: choose last subarray `[4]` → cost = `(8 + 1*3)*6 = 66`, total dp = `50 + 60 = 110`