Minimum Cost to Split an Array - Practice Coding Problems

Minimum Cost to Split an Array - Problem

You are given an integer array nums and an integer k.

Split the array into some number of non-empty subarrays. The cost of a split is the sum of the importance value of each subarray in the split.

Let trimmed(subarray) be the version of the subarray where all numbers which appear only once are removed.

For example, trimmed([3,1,2,4,3,4]) = [3,4,3,4].

The importance value of a subarray is k + trimmed(subarray).length.

For example, if a subarray is [1,2,3,3,3,4,4], then trimmed([1,2,3,3,3,4,4]) = [3,3,3,4,4]. The importance value of this subarray will be k + 5.

Return the minimum possible cost of a split of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

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

› Output: 8

💡 Note: Split into [1,2,3,2] and [2]. First subarray has trimmed([1,2,3,2]) = [2,2] with length 2, so cost = 3+2 = 5. Second subarray has trimmed([2]) = [] with length 0, so cost = 3+0 = 3. Total = 5+3 = 8.

Example 2 — All Duplicates

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

› Output: 6

💡 Note: Keep as single array [1,1,1,1]. trimmed([1,1,1,1]) = [1,1,1,1] with length 4. Cost = 2+4 = 6. Any split would cost more since each subarray adds k=2.

Example 3 — All Unique

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

› Output: 4

💡 Note: Best to split into individual elements: [1], [2], [3], [4]. Each has trimmed length 0, so each costs 1+0 = 1. Total = 1+1+1+1 = 4.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000
1 ≤ k ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Array

[1,2,3,2,2] with k=3

Try Split

Split into [1,2,3,2] and [2]

Calculate Cost

First: 3+2=5, Second: 3+0=3, Total: 8

Key Takeaway

🎯 Key Insight: Only elements that appear multiple times in a subarray contribute to its trimmed length and cost

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is that only elements appearing multiple times in a subarray contribute to its cost. We use dynamic programming to find the optimal way to split the array, trying all possible split positions and choosing the minimum cost. Best approach is memoized recursion or bottom-up DP. Time: O(n³), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Bottom-Up Dynamic Programming	O(n³)	O(n)	Build solution iteratively from smaller subproblems
Memoized Dynamic Programming	O(n³)	O(n)	Cache results to avoid recalculating same subproblems
Brute Force - Try All Splits	O(2ⁿ × n²)	O(n)	Recursively try every possible way to split the array

Bottom-Up Dynamic Programming — Algorithm Steps

Create DP array of size n+1
Initialize dp[n] = 0 (base case)
For each position i, try all possible splits
Use dp[j+1] for remaining subarray cost
Return dp[0]

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[n] = 0, others to infinity

Fill Array

For each position, try all possible splits

Final Answer

dp[0] contains the minimum cost

Code -

solution.c — C

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

#define MAX_N 1000

int solution(int* nums, int n, int k) {
    int* dp = (int*)malloc((n + 1) * sizeof(int));
    for (int i = 0; i < n; i++) dp[i] = INT_MAX;
    dp[n] = 0;
    
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            int count[2001] = {0};
            for (int idx = i; idx <= j; idx++) {
                count[nums[idx] + 1000]++;
            }
            int trimmedLength = 0;
            for (int c = 0; c < 2001; c++) {
                if (count[c] > 1) trimmedLength += count[c];
            }
            int importance = k + trimmedLength;
            if (importance + dp[j + 1] < dp[i]) {
                dp[i] = importance + dp[j + 1];
            }
        }
    }
    
    int result = dp[0];
    free(dp);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[MAX_N];
    int n = 0;
    char* token = strtok(line, "[,] \n");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[,] \n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, n, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: position i, split end j, and counting frequencies in each subarray

⚠ Quadratic Growth

Space Complexity

O(n)

DP array of size n+1 plus temporary frequency counting

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

890 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

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler