Minimum Cost to Split an Array
HardPrompt
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 bek + 5.
Return the minimum possible cost of a split of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,2,1,2,1,3,3], k = 2
Output: 8
Explanation: We split nums to have two subarrays: [1,2], [1,2,1,3,3].
The importance value of [1,2] is 2 + (0) = 2.
The importance value of [1,2,1,3,3] is 2 + (2 + 2) = 6.
The cost of the split is 2 + 6 = 8. It can be shown that this is the minimum possible cost among all the possible splits.Example 2:
Input: nums = [1,2,1,2,1], k = 2
Output: 6
Explanation: We split nums to have two subarrays: [1,2], [1,2,1].
The importance value of [1,2] is 2 + (0) = 2.
The importance value of [1,2,1] is 2 + (2) = 4.
The cost of the split is 2 + 4 = 6. It can be shown that this is the minimum possible cost among all the possible splits.Example 3:
Input: nums = [1,2,1,2,1], k = 5
Output: 10
Explanation: We split nums to have one subarray: [1,2,1,2,1].
The importance value of [1,2,1,2,1] is 5 + (3 + 2) = 10.
The cost of the split is 10. It can be shown that this is the minimum possible cost among all the possible splits.
Constraints:
1 <= nums.length <= 10000 <= nums[i] < nums.length1 <= k <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a straightforward dynamic programming formulation. We define dp[i] as the minimum cost to split the prefix of the array nums of length i. To compute dp[i], we consider all possible previous split points j < i. The cost would be the minimum cost to split the array up to j (dp[j]) plus the cost of the newly formed last subarray nums[j...i-1]. The main drawback is the repeated and inefficient calculation of the cost for each subarray.
Algorithm
- Create a
dparray of sizen+1, wherenis the length ofnums.dp[i]will store the minimum cost to split the prefixnums[0...i-1]. - Initialize
dp[0] = 0and all otherdp[i]to a very large value. - Iterate
ifrom1ton:- For each
i, iteratejfrom0toi-1. Thisjrepresents a potential split point, makingnums[j...i-1]the last subarray. - For each subarray
nums[j...i-1], calculate its cost:- Create a frequency map (or an array since element values are bounded) for the elements in
nums[j...i-1]by iterating fromjtoi-1. - Calculate
trimmed_lengthby iterating through the frequency map and summing up the counts of elements that appear more than once. - The cost of the subarray is
k + trimmed_length.
- Create a frequency map (or an array since element values are bounded) for the elements in
- Update the
dpstate:dp[i] = min(dp[i], dp[j] + cost).
- For each
- The final answer is
dp[n].
Walkthrough
The recurrence relation for this DP approach is dp[i] = min_{0 <= j < i} (dp[j] + cost(nums[j...i-1])). The cost of a subarray nums[j...i-1] is k + trimmed(nums[j...i-1]).length.
To implement this, we use two nested loops to iterate through all possible start (j) and end (i) points of the subarrays. For each subarray, we perform another loop to calculate the frequency of its elements to determine the trimmed_length. This three-level nested loop structure leads to a cubic time complexity.
import java.util.Arrays;import java.util.HashMap;import java.util.Map; class Solution { public int minCost(int[] nums, int k) { int n = nums.length; long[] dp = new long[n + 1]; Arrays.fill(dp, Long.MAX_VALUE); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { // Subarray is nums[j...i-1] // Since 0 <= nums[i] < nums.length, an array can be used instead of a HashMap int[] counts = new int[n]; for (int l = j; l < i; l++) { counts[nums[l]]++; } int trimmedLength = 0; // This loop can be optimized, but overall complexity remains O(N^3) for (int count : counts) { if (count > 1) { trimmedLength += count; } } long cost = k + trimmedLength; if (dp[j] != Long.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[j] + cost); } } } return (int) dp[n]; }}Complexity
Time
O(N^3), where N is the number of elements in `nums`. There are two nested loops for `i` and `j` (O(N^2)), and inside, calculating the cost of a subarray takes O(N) time.
Space
O(N), where N is the number of elements in `nums`. This is for the `dp` array and the frequency count array used inside the loops.
Trade-offs
Pros
It is a direct translation of the problem's recurrence relation, making it relatively easy to understand and implement.
Cons
The time complexity of O(N^3) is too slow for the given constraints (N <= 1000), and this solution will likely result in a 'Time Limit Exceeded' error.
Solutions
Solution
class Solution {private Integer[] f;private int[] nums;private int n, k;public int minCost(int[] nums, int k) { n = nums.length; this.k = k; this.nums = nums; f = new Integer[n]; return dfs(0); }private int dfs(int i) { if (i >= n) { return 0; } if (f[i] != null) { return f[i]; } int[] cnt = new int[n]; int one = 0; int ans = 1 << 30; for (int j = i; j < n; ++j) { int x = ++cnt[nums[j]]; if (x == 1) { ++one; } else if (x == 2) { --one; } ans = Math.min(ans, k + j - i + 1 - one + dfs(j + 1)); } return f[i] = ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.