Minimum Cost to Split an Array

Hard
1051.

Minimum Cost to Split an Array

Minimum Cost to Split an Array is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google, Uber and Indeed interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minCost = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Cost to Split an Array — Problem & Solution

Minimum Cost to Split an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Cost to Split an Array is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google, Uber and Indeed interviews.

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

Hints for Minimum Cost to Split an Array

  1. Hint 1

    dp[i] = the minimum cost for the suffix starting at i.

  2. Hint 2

    Extending a subarray to the right lets you maintain its trimmed length incrementally.

  3. Hint 3

    A value's second occurrence adds 2 to the trimmed length; each further occurrence adds 1.

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

  1. Set dp[n] = 0.
  2. For i from n-1 down to 0, reset a count array and trimmed = 0.
  3. Extend j from i: increment count[nums[j]]. If it reaches 2, add 2 to trimmed; if it is above 2, add 1.
  4. 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]

Java

public static int minCost(int[] nums, int k) {
    int n = nums.length;
    final int INF = 1000000000;
    int[] dp = new int[n + 1];
    Arrays.fill(dp, INF);
    dp[n] = 0;
    for (int i = n - 1; i >= 0; i--) {
        int[] cnt = new int[n];
        int trimmed = 0;
        for (int j = i; j < n; j++) {
            cnt[nums[j]]++;
            if (cnt[nums[j]] == 2) trimmed += 2;
            else if (cnt[nums[j]] > 2) trimmed += 1;
            dp[i] = Math.min(dp[i], k + trimmed + dp[j + 1]);
        }
    }
    return dp[0];
}

C++

int minCost(vector<int>& nums, int k) {
    int n = (int) nums.size();
    const int INF = 1000000000;
    vector<int> dp(n + 1, INF);
    dp[n] = 0;
    for (int i = n - 1; i >= 0; i--) {
        vector<int> cnt(n, 0);
        int trimmed = 0;
        for (int j = i; j < n; j++) {
            cnt[nums[j]]++;
            if (cnt[nums[j]] == 2) trimmed += 2;
            else if (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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets