Watch 10 video solutions for Minimum Cost to Split an Array, a hard level problem involving Array, Hash Table, Dynamic Programming. This walkthrough by Bro Coders has 2,456 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
trimmed([3,1,2,4,3,4]) = [3,4,3,4].The importance value of a subarray is k + trimmed(subarray).length.
[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.
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
Problem Overview: You split nums into multiple subarrays. Each subarray adds a fixed cost k, plus a penalty for duplicate values inside that segment. The penalty equals the size of the "trimmed" subarray—elements that appear more than once remain while unique elements are ignored. The goal is to choose split points that minimize the total cost.
Approach 1: Dynamic Programming with Frequency Table (O(n²) time, O(n) space)
This is the standard solution. Let dp[i] represent the minimum cost to split the first i elements. For each ending index i, iterate backward through possible starting points j. Maintain a frequency table for the current subarray nums[j..i]. When a value appears for the second time, add 2 to the duplicate penalty; for further occurrences add 1. The cost of this segment becomes k + duplicateCost, and you update dp[i+1] = min(dp[i+1], dp[j] + cost). Using a hash table for counting keeps updates constant time. This approach relies heavily on dynamic programming and hash table counting.
Approach 2: Greedy Approach with Two Pointers (≈O(n²) time, O(n) space)
This variation tries to grow segments using two pointers while tracking duplicate penalties. The right pointer expands the current subarray while a frequency map tracks counts. If duplicates inflate the cost too much compared to starting a new segment, the left boundary shifts. The idea is to greedily maintain segments that keep the duplicate penalty small relative to the fixed cost k. While not strictly optimal for all implementations without DP, the two‑pointer strategy reduces recomputation of frequencies and works well in practice when segments remain small.
Approach 3: Dynamic Programming with Incremental Counting (O(n²) time, O(n) space)
A refined DP implementation avoids rebuilding the frequency table for every candidate segment. For each starting index i, extend the end index j forward while maintaining counts and duplicate penalties incrementally. Update dp[j+1] using the current segment cost. This technique keeps counting logic localized and eliminates repeated scans. The algorithm still runs in quadratic time but is usually faster due to better cache behavior and fewer map resets. It combines array traversal with incremental frequency updates.
Approach 4: Greedy with Optimized Prefix Calculations (≈O(n²) time, O(n) space)
This version precomputes duplicate penalties using prefix-style updates. As the right boundary moves, the algorithm tracks how duplicates evolve and reuses those calculations when evaluating potential splits. Instead of recomputing penalties from scratch, the prefix structure lets you quickly update the cost contribution of each new element. The optimization reduces constant factors and performs well on larger arrays where repeated frequency recomputation would otherwise dominate runtime.
Recommended for interviews: The dynamic programming solution with a frequency table is the approach most interviewers expect. It clearly models the decision of where to split the array and demonstrates strong control of state transitions in DP. Showing the brute-force idea first (trying all splits) and then optimizing it with incremental frequency counting highlights algorithmic reasoning and leads naturally to the O(n²) DP solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Frequency Table | O(n²) | O(n) | General case; standard interview solution |
| Greedy with Two Pointers | ≈O(n²) | O(n) | When trying to reduce recomputation of segment frequencies |
| Incremental Dynamic Programming | O(n²) | O(n) | Efficient DP implementation with better constant factors |
| Greedy with Optimized Prefix Calculations | ≈O(n²) | O(n) | Large inputs where prefix reuse reduces repeated counting |