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.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Dynamic Programming, Counting
- Asked at: Amazon, Google, Uber, Indeed
- 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 <= 10000 <= nums[i] < nums.length1 <= k <= 10^9
Hints for Minimum Cost to Split an Array
Hint 1
dp[i]= the minimum cost for the suffix starting ati.Hint 2
Extending a subarray to the right lets you maintain its trimmed length incrementally.
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
- Set
dp[n] = 0. - For
ifromn-1down to 0, reset a count array andtrimmed = 0. - Extend
jfromi: incrementcount[nums[j]]. If it reaches 2, add 2 totrimmed; if it is above 2, add 1. - Take the minimum of
k + trimmed + dp[j+1]over allj.
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