Minimum Cost to Split an Array

Hard

#2327Time: 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.1 company

Patterns

Dynamic Programming Counting

Data structures

Array Hash Table

Companies

Indeed

Prompt

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 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 <= 1000
0 <= nums[i] < nums.length
1 <= k <= 10⁹

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 dp array of size n+1, where n is the length of nums. dp[i] will store the minimum cost to split the prefix nums[0...i-1].
Initialize dp[0] = 0 and all other dp[i] to a very large value.
Iterate i from 1 to n:
- For each i, iterate j from 0 to i-1. This j represents a potential split point, making nums[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 from j to i-1.
  - Calculate trimmed_length by 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.
- Update the dp state: dp[i] = min(dp[i], dp[j] + cost).
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.

1import java.util.Arrays;2import java.util.HashMap;3import java.util.Map;4 5class Solution {6    public int minCost(int[] nums, int k) {7        int n = nums.length;8        long[] dp = new long[n + 1];9        Arrays.fill(dp, Long.MAX_VALUE);10        dp[0] = 0;11 12        for (int i = 1; i <= n; i++) {13            for (int j = 0; j < i; j++) {14                // Subarray is nums[j...i-1]15                // Since 0 <= nums[i] < nums.length, an array can be used instead of a HashMap16                int[] counts = new int[n];17                for (int l = j; l < i; l++) {18                    counts[nums[l]]++;19                }20 21                int trimmedLength = 0;22                // This loop can be optimized, but overall complexity remains O(N^3)23                for (int count : counts) {24                    if (count > 1) {25                        trimmedLength += count;26                    }27                }28 29                long cost = k + trimmedLength;30                if (dp[j] != Long.MAX_VALUE) {31                    dp[i] = Math.min(dp[i], dp[j] + cost);32                }33            }34        }35        return (int) dp[n];36    }37}

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.

This approach refines the naive DP solution by optimizing the calculation of subarray costs. The core DP state and recurrence remain the same, but we avoid recomputing the trimmed_length from scratch for every subarray. By iterating backwards for the start of the last subarray, we can incrementally update the trimmed_length in constant time for each new element added. This optimization reduces the overall time complexity from cubic to quadratic.

Algorithm

Use the same DP state dp[i] as the naive approach, representing the minimum cost for the prefix nums[0...i-1].
Initialize dp[0] = 0 and other dp entries to a large value.
Iterate i from 1 to n:
- To calculate dp[i], we will consider all subarrays nums[j...i-1] ending at i-1.
- Instead of a forward j loop, we loop j backwards from i-1 down to 0.
- Maintain a frequency array counts and a running trimmedLength for the current subarray being considered.
- In the inner loop (for j):
  - Add nums[j] to the current subarray (which was nums[j+1...i-1]).
  - Update the frequency of nums[j] in counts.
  - Update trimmedLength based on the new count of nums[j]. If the count becomes 2, trimmedLength increases by 2. If it's greater than 2, it increases by 1.
  - Calculate the cost k + trimmedLength and update dp[i] = min(dp[i], dp[j] + cost).
Return dp[n].

Walkthrough

The key insight is that for a fixed endpoint i, as we consider different start points j, the subarrays nums[j...i-1] are related. Specifically, nums[j...i-1] is just nums[j+1...i-1] with nums[j] prepended.

We can exploit this. For a fixed i, we iterate j from i-1 down to 0. We maintain the trimmed_length of the subarray nums[j...i-1]. When we move from j to j-1, we are essentially adding nums[j-1] to our subarray. The change in trimmed_length depends only on the number of times nums[j-1] has already appeared in nums[j...i-1]. This update can be done in O(1) time with a frequency map. This eliminates the innermost O(N) loop from the naive approach.

1import java.util.Arrays;2 3class Solution {4    public int minCost(int[] nums, int k) {5        int n = nums.length;6        long[] dp = new long[n + 1];7        Arrays.fill(dp, Long.MAX_VALUE);8        dp[0] = 0;9 10        for (int i = 1; i <= n; i++) {11            int[] counts = new int[n]; // Since 0 <= nums[i] < nums.length12            int trimmedLength = 0;13            for (int j = i - 1; j >= 0; j--) {14                int num = nums[j];15                counts[num]++;16                if (counts[num] == 2) {17                    trimmedLength += 2;18                } else if (counts[num] > 2) {19                    trimmedLength += 1;20                }21                22                long cost = k + trimmedLength;23                if (dp[j] != Long.MAX_VALUE) {24                    dp[i] = Math.min(dp[i], dp[j] + cost);25                }26            }27        }28        return (int) dp[n];29    }30}

Note: We use a long array for dp because intermediate costs dp[j] + cost can exceed Integer.MAX_VALUE given the constraints on k, even though the final answer is guaranteed to fit in an int.

Complexity

Time

O(N^2), where N is the number of elements in `nums`. The two nested loops dominate the runtime, and the operations inside are O(1).

Space

O(N), for the `dp` array and the `counts` frequency array.

Trade-offs

Pros

The O(N^2) complexity is efficient enough to solve the problem within typical time limits for N up to 1000.
It's a common and powerful optimization technique for this class of DP problems.

Cons

While efficient enough for the given constraints, an O(N^2) solution might still be too slow for significantly larger inputs.

Solutions

Solution

1class Solution {2private3  Integer[] f;4private5  int[] nums;6private7  int n, k;8public9  int minCost(int[] nums, int k) {10    n = nums.length;11    this.k = k;12    this.nums = nums;13    f = new Integer[n];14    return dfs(0);15  }16private17  int dfs(int i) {18    if (i >= n) {19      return 0;20    }21    if (f[i] != null) {22      return f[i];23    }24    int[] cnt = new int[n];25    int one = 0;26    int ans = 1 << 30;27    for (int j = i; j < n; ++j) {28      int x = ++cnt[nums[j]];29      if (x == 1) {30        ++one;31      } else if (x == 2) {32        --one;33      }34      ans = Math.min(ans, k + j - i + 1 - one + dfs(j + 1));35    }36    return f[i] = ans;37  }38}

1class Solution {2public:3  int minCost(vector<int> &nums, int k) {4    int n = nums.size();5    int f[n];6    memset(f, 0, sizeof f);7    function<int(int)> dfs = [&](int i) {8      if (i >= n) {9        return 0;10      }11      if (f[i]) {12        return f[i];13      }14      int cnt[n];15      memset(cnt, 0, sizeof cnt);16      int one = 0;17      int ans = 1 << 30;18      for (int j = i; j < n; ++j) {19        int x = ++cnt[nums[j]];20        if (x == 1) {21          ++one;22        } else if (x == 2) {23          --one;24        }25        ans = min(ans, k + j - i + 1 - one + dfs(j + 1));26      }27      return f[i] = ans;28    };29    return dfs(0);30  }31};

1class Solution:2    def minCost(self, nums: List[int], k: int) -> int: @ cache def dfs(i): if i >= n: return 0 cnt = Counter() one = 0 ans = inf for j in range(i, n): cnt[nums[j]] += 1 if cnt[nums[j]] == 1: one += 1 elif cnt[nums[j]] == 2: one -= 1 ans = min(ans, k + j - i + 1 - one + dfs(j + 1)) return ans n = len(nums) return dfs(0)

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.

← Previous

Previous problem

Next problem