Minimum Cost to Split an Array — Hard Problem & Solution

The trimmed version of a subarray removes every value that appears in it exactly once.

Difficulty: Hard
Topics: Arrays, Hash Table, Dynamic Programming, Counting
Asked at: Amazon, Google, Uber
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The trimmed version of a subarray removes every value that appears in it exactly once. The importance of a subarray is k plus the length of its trimmed version.

Split nums into one or more contiguous subarrays and return the minimum total importance.

Example 1

Input: nums = [1,2,1,2,1,3,3], k = 2
Output: 8
Explanation: Split as `[1,2]` (nothing repeats, cost 2) and `[1,2,1,3,3]` (trims to length 4, cost 6).

Example 2

Input: nums = [1,2,1,2,1], k = 2
Output: 6
Explanation: Keep it whole: nothing trims away, so 2 + 4 = 6.

Example 3

Input: nums = [1,2,1,2,1], k = 5
Output: 10
Explanation: A larger `k` discourages splitting.

Constraints

1 <= nums.length <= 1000
0 <= nums[i] < nums.length
1 <= k <= 10^9

How to solve Minimum Cost to Split an Array

Suffix DP. dp[i] is the cheapest way to cover nums[i..]. For each start i, extend the first subarray to every end j, maintaining its trimmed length as you go, and take k + trimmed + dp[j+1].

Approach

Set dp[n] = 0.
For i from n-1 down to 0, reset a count array and trimmed = 0.
Extend j from i: increment count[nums[j]]. If it reaches 2, add 2 to trimmed; if it is above 2, add 1.
Take the minimum of k + trimmed + dp[j+1] over all j.

Why it works

The +2 / +1 rule is the crux. While a value appears once it contributes nothing to the trimmed length; the moment a second copy arrives, both copies start counting, so the jump is 2 — and every later copy adds only itself. Maintaining that incrementally is what keeps the inner loop O(1) per step and the whole solution O(n²) instead of O(n³).

Complexity

Time — O(n²)
Space — O(n)

Pitfalls

The second occurrence adds 2, not 1 — forgetting the first copy under-counts every repeated value.
The count array must be reset for each start i.
A subarray with no repeats still costs k, so splitting is never free.

Reference solution

Python

from typing import List

def minCost(nums: List[int], k: int) -> int:
    n = len(nums)
    INF = 10**9
    dp = [INF] * (n + 1)
    dp[n] = 0
    for i in range(n - 1, -1, -1):
        cnt = [0] * n
        trimmed = 0
        for j in range(i, n):
            cnt[nums[j]] += 1
            if cnt[nums[j]] == 2:
                trimmed += 2
            elif cnt[nums[j]] > 2:
                trimmed += 1
            dp[i] = min(dp[i], k + trimmed + dp[j + 1])
    return dp[0]

JavaScript

var minCost = function(nums, k) {
    var n = nums.length, INF = 1000000000, i, j;
    var dp = [];
    for (i = 0; i <= n; i++) dp.push(INF);
    dp[n] = 0;
    for (i = n - 1; i >= 0; i--) {
        var cnt = [];
        for (j = 0; j < n; j++) cnt.push(0);
        var trimmed = 0;
        for (j = i; j < n; j++) {
            cnt[nums[j]]++;
            if (cnt[nums[j]] === 2) trimmed += 2;
            else if (cnt[nums[j]] > 2) trimmed += 1;
            var cand = k + trimmed + dp[j + 1];
            if (cand < dp[i]) dp[i] = cand;
        }
    }
    return dp[0];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue