Minimum Cost to Divide Array Into Subarrays

Minimum Cost to Divide Array Into Subarrays - Problem

You are given two integer arrays, nums and cost, of the same size, and an integer k.

You can divide nums into subarrays. The cost of the i-th subarray consisting of elements nums[l..r] is:

(nums[l] + nums[l+1] + ... + nums[r] + k * i) * (cost[l] + cost[l+1] + ... + cost[r])

Note that i represents the order of the subarray: 1 for the first subarray, 2 for the second, and so on.

Return the minimum total cost possible from any valid division.

Input & Output

Example 1 — Basic Division

$ Input: nums = [1,3,2], cost = [2,3,1], k = 1

› Output: 15

💡 Note: Divide into [1,3] | [2]. First subarray: (1+3+1*1)*(2+3) = 5*5 = 25. Second subarray: (2+1*2)*1 = 4*1 = 4. Total: 25+4 = 29. Better: [1] | [3,2] gives (1+1*1)*2 + (3+2+1*2)*4 = 4 + 28 = 32. Best: single array [1,3,2] gives (1+3+2+1*1)*6 = 42. Actually optimal is [1,3] | [2] = (4+1)*5 + (2+2)*1 = 25+4 = 29, but [1] | [3,2] = 2*1 + 7*4 = 30, and single [1,3,2] = 7*6 = 42. The minimum is when we split optimally.

Example 2 — Single Element

$ Input: nums = [5], cost = [2], k = 3

› Output: 16

💡 Note: Only one way to divide: single subarray [5]. Cost = (5 + 3*1) * 2 = 8 * 2 = 16

Example 3 — All Separate vs Together

$ Input: nums = [1,1], cost = [1,1], k = 2

› Output: 10

💡 Note: Option 1: [1] | [1] gives (1+2*1)*1 + (1+2*2)*1 = 3 + 5 = 8. Option 2: [1,1] gives (1+1+2*1)*2 = 4*2 = 8. Both give same result.

Constraints

1 ≤ nums.length ≤ 1000
nums.length == cost.length
-1000 ≤ nums[i] ≤ 1000
1 ≤ cost[i] ≤ 1000
1 ≤ k ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums=[1,3,2], cost=[2,3,1], k=1

Try Partitions

Calculate cost for different ways to divide

Find Minimum

Return the lowest total cost

Key Takeaway

🎯 Key Insight: Each subarray's cost includes a penalty k×i based on its position, making the division order crucial for minimization.

Asked in

G Google 12 M Microsoft 8 A Amazon 6

This problem requires dynamic programming to find the optimal way to partition an array. The key insight is that each subarray's cost depends on both its content and its position in the sequence. The memoization approach with O(n²) time complexity provides the best balance of efficiency and clarity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible ways to divide the array recursively
Dynamic Programming with Memoization	O(n²)	O(n²)	Cache results of recursive calls to avoid recalculation
Bottom-Up Dynamic Programming	O(n²)	O(n)	Build solution iteratively from smaller subproblems

Brute Force Recursion — Algorithm Steps

For each position, decide whether to end current subarray
Calculate cost if ending subarray here
Recursively solve remaining array
Return minimum among all choices

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Division

At each position, decide to cut or continue

Calculate Cost

Compute subarray cost using formula

Recurse

Solve remaining array recursively

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

long long solve(int* nums, int* cost, int n, int k, int start, int subarrayIndex) {
    if (start == n) return 0;
    
    long long minCost = LLONG_MAX;
    long long numsSum = 0;
    long long costSum = 0;
    
    for (int end = start; end < n; end++) {
        numsSum += nums[end];
        costSum += cost[end];
        
        long long currentCost = (numsSum + (long long)k * subarrayIndex) * costSum;
        long long remainingCost = solve(nums, cost, n, k, end + 1, subarrayIndex + 1);
        
        if (currentCost + remainingCost < minCost) {
            minCost = currentCost + remainingCost;
        }
    }
    
    return minCost;
}

long long solution(int* nums, int* cost, int n, int k) {
    return solve(nums, cost, n, k, 0, 1);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse nums array
    int nums[100], cost[100], n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL && n < 100) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    // Parse cost array
    fgets(line, sizeof(line), stdin);
    int costCount = 0;
    token = strtok(line, "[],\n");
    while (token != NULL && costCount < 100) {
        if (strlen(token) > 0 && token[0] != ' ') {
            cost[costCount++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%lld\n", solution(nums, cost, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each position has 2 choices (cut or continue), leading to 2^n possibilities

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth can go up to n levels

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler