2547. Minimum Cost to Split an Array LeetCode Solution
In this guide, you will get 2547. Minimum Cost to Split an Array LeetCode Solution with the best time and space complexity. The solution to Minimum Cost to Split an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Cost to Split an Array
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.
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.
2547. Minimum Cost to Split an Array LeetCode Solution in C++
class Solution {
public:
int minCost(vector<int>& nums, int k) {
constexpr int kMax = 1001;
const int n = nums.size();
// trimmedLength[i][j] := trimmed(nums[i..j]).length
vector<vector<int>> trimmedLength(n, vector<int>(n));
// dp[i] := the minimum cost to split nums[i..n)
vector<int> dp(n + 1, INT_MAX / 2);
for (int i = 0; i < n; ++i) {
int length = 0;
vector<int> count(kMax);
for (int j = i; j < n; ++j) {
if (++count[nums[j]] == 2)
length += 2;
else if (count[nums[j]] > 2)
++length;
trimmedLength[i][j] = length;
}
}
dp[n] = 0;
for (int i = n - 1; i >= 0; --i)
for (int j = i; j < n; ++j)
dp[i] = min(dp[i], k + trimmedLength[i][j] + dp[j + 1]);
return dp[0];
}
}; /* code provided by PROGIEZ */
2547. Minimum Cost to Split an Array LeetCode Solution in Java
class Solution {
public int minCost(int[] nums, int k) {
final int kMax = 1001;
final int n = nums.length;
// trimmedLength[i][j] := trimmed(nums[i..j]).length
int[][] trimmedLength = new int[n][n];
// dp[i] := the minimum cost to split nums[i..n)
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE / 2);
for (int i = 0; i < n; ++i) {
int length = 0;
int[] count = new int[kMax];
for (int j = i; j < n; ++j) {
if (++count[nums[j]] == 2)
length += 2;
else if (count[nums[j]] > 2)
++length;
trimmedLength[i][j] = length;
}
}
dp[n] = 0;
for (int i = n - 1; i >= 0; --i)
for (int j = i; j < n; ++j)
dp[i] = Math.min(dp[i], k + trimmedLength[i][j] + dp[j + 1]);
return dp[0];
}
} // code provided by PROGIEZ
2547. Minimum Cost to Split an Array LeetCode Solution in Python
class Solution:
def minCost(self, nums: list[int], k: int) -> int:
kMax = 1001
n = len(nums)
# trimmedLength[i][j] := trimmed(nums[i..j]).length
trimmedLength = [[0] * n for _ in range(n)]
# dp[i] := the minimum cost to split nums[i..n)
dp = [math.inf] * n + [0]
for i in range(n):
length = 0
count = [0] * kMax
for j in range(i, n):
count[nums[j]] += 1
if count[nums[j]] == 2:
length += 2
elif count[nums[j]] > 2:
length += 1
trimmedLength[i][j] = length
dp[n] = 0
for i in range(n - 1, -1, -1):
for j in range(i, n):
dp[i] = min(dp[i], k + trimmedLength[i][j] + dp[j + 1])
return dp[0] # code by PROGIEZ
