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.
This approach uses dynamic programming alongside a frequency table to calculate the minimum cost of splitting the array. We maintain a DP array where dp[i] stores the minimum cost of splitting the first i elements of the nums array. For each element in nums, we keep track of its frequency within the current window using a dictionary or hash map. The importance value calculation involves determining the trimmed version's length by checking values in this frequency table. The idea is to iterate through potential endpoints of subarrays and calculate possible segments' costs while updating the minimum cost in the DP table.
This solution employs a DP array of size n+1, where each index represents the minimum cost of splitting the array up to that point. For each i from 1 to n, a dictionary named `freq` tracks element occurrences between j and i. This frequency tracking helps to compute the cost of the current subarray given the importance value calculation. Through this method, the DP table keeps getting updated with the optimal split costs for progressively larger subarrays.
Python
Time Complexity: O(n^2) as each subarray is examined, and Space Complexity: O(n) for the DP array.
This approach leverages two pointers and a greedy methodology to ensure the array is minimally split. It dynamically adjusts subarrays based on their importance value, effectively using two pointers to define the current subarray and its trimming. Maintaining two pointers that start at the beginning and slide as necessary allows identifying sections of nums, continuously updating the minimal costs of various splits while keeping a focus on local optimal importance values.segmentation while trying to ensure each subarray contributes to the minimum cost.
The Java solution uses two pointers iteratively to explore potential subarray segments while maintaining a frequency map to track occurrences within the current valid subarray. It updates the DP array based on the computed cost by considering each possible split endpoint, greedily determining the minimal cost path dynamically. The nested loops iteratively adjust the `dp` cost array given the current pair of boundaries, leveraging the two-pointer technique to control segment lengths and contribute to refined cost estimates consistently.
Java
Time Complexity: O(n^2) due to the double nested loops accounting for full subarrays, and Space Complexity: O(n) for the DP array in conjunction with any overhead from map structures.
In this approach, we use dynamic programming to minimize the cost of splitting the array. We define a DP array where dp[i] represents the minimum cost to split the array nums[0...i]. We iterate through the array, and for each position, we try to split the array into subarrays at different points to find the minimum cost. We make use of a frequency map to calculate the trimmed length of subarrays optimally.
We update the DP array by considering all possible subarrays ending at position i, and use the frequency count to determine the importance value of each subarray. The goal is to find the minimum possible sum of costs for all splits made in the array.
The Python solution initializes a DP array where each entry is set to infinity, except for dp[0] which is zero (the base case for an empty subarray). The algorithm calculates the frequency of numbers in a current subarray and updates the length of trimmed elements accordingly.
For each possible end of subarray, it calculates the cost and updates dp[i] with the minimum cost found. It uses nested loops to consider subarrays ending at each index.
Time Complexity: O(n^2), where n is the length of the array, due to the nested loops for checking subarray splits. Space Complexity: O(n) for the DP array and frequency dictionary.
This approach involves using a greedy algorithm optimized with prefix calculations to efficiently trim subarrays. We track frequencies using prefix data structures, allowing us to efficiently calculate the trimmed length for any subarray by examining the prefix data. This helps reduce redundant calculations seen in the naive approach.
The critical observation is that for any subarray not ending in a unique value, its contribution to trimming is cumulative and can be precomputed to allow constant-time queries during the splitting decision process.
This Python solution preprocesses a prefix array that accumulates the lengths of possible 'important' subarrays. For index i, prefix_data[i] holds the cumulative length to facilitate quick lookups for calculating trimmed subarray lengths. This allows us to efficiently compute the importance value of different split configurations.
Time Complexity: O(n^2), preprocessing time is linear with respect to n, but the main computation involves nested loops. Space Complexity: O(n) for storing DP and prefix length data.
We design a function dfs(i), which represents the minimum cost of splitting from index i. So the answer is dfs(0).
The calculation process of the function dfs(i) is as follows:
If i \ge n, it means that the splitting has reached the end of the array, and 0 is returned at this time.
Otherwise, we enumerate the end j of the subarray. During the process, we use an array or hash table cnt to count the number of times each number appears in the subarray, and use a variable one to count the number of numbers in the subarray that appear once. So the importance of the subarray is k + j - i + 1 - one, and the cost of splitting is k + j - i + 1 - one + dfs(j + 1). We enumerate all j and take the minimum value as the return value of dfs(i).
During the process, we can use memoization search, that is, use an array f to memorize the return value of the function dfs(i) to avoid repeated calculations.
The time complexity is O(n^2), and the space complexity is O(n). Where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with Frequency Table | Time Complexity: O(n^2) as each subarray is examined, and Space Complexity: O(n) for the DP array. |
| Greedy Approach with Two Pointers | Time Complexity: O(n^2) due to the double nested loops accounting for full subarrays, and Space Complexity: O(n) for the DP array in conjunction with any overhead from map structures. |
| Dynamic Programming Approach | Time Complexity: O(n^2), where n is the length of the array, due to the nested loops for checking subarray splits. Space Complexity: O(n) for the DP array and frequency dictionary. |
| Greedy with Optimized Prefix Calculations | Time Complexity: O(n^2), preprocessing time is linear with respect to n, but the main computation involves nested loops. Space Complexity: O(n) for storing DP and prefix length data. |
| Memoization Search | — |
| 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 |
2547. Minimum Cost to Split an Array | Weekly Contest 329 | LeetCode 2547 • Bro Coders • 2,456 views views
Watch 9 more video solutions →Practice Minimum Cost to Split an Array with our built-in code editor and test cases.
Practice on FleetCode