Problem

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 ofnums.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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

1
2
3
4
5

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^9

Solution

Method 1 – Dynamic Programming with Hash Map

Intuition

We use dynamic programming to find the minimum cost to split the array. For each possible split, we calculate the cost of the subarray using a hash map to count frequencies, then recursively compute the minimum cost for the rest of the array.

Approach

  1. Use DP: dp[i] is the minimum cost to split the first i elements.
  2. For each position i, try all possible previous split points j:
    • Use a hash map to count frequencies in nums[j:i].
    • Compute the trimmed length (count of elements with freq > 1).
    • The cost for subarray [j, i-1] is k + trimmed_len.
    • Update dp[i] as the minimum over all splits.
  3. Return dp[n] for the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int minCost(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            unordered_map<int,int> freq;
            int trimmed = 0;
            for (int j = i; j >= 1; --j) {
                freq[nums[j-1]]++;
                if (freq[nums[j-1]] == 2) trimmed += 2;
                else if (freq[nums[j-1]] > 2) trimmed++;
                dp[i] = min(dp[i], dp[j-1] + k + trimmed);
            }
        }
        return dp[n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func minCost(nums []int, k int) int {
    n := len(nums)
    dp := make([]int, n+1)
    for i := range dp { dp[i] = 1<<31 - 1 }
    dp[0] = 0
    for i := 1; i <= n; i++ {
        freq := map[int]int{}
        trimmed := 0
        for j := i; j >= 1; j-- {
            freq[nums[j-1]]++
            if freq[nums[j-1]] == 2 { trimmed += 2 }
            else if freq[nums[j-1]] > 2 { trimmed++ }
            if dp[j-1]+k+trimmed < dp[i] { dp[i] = dp[j-1]+k+trimmed }
        }
    }
    return dp[n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int minCost(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            Map<Integer,Integer> freq = new HashMap<>();
            int trimmed = 0;
            for (int j = i; j >= 1; --j) {
                freq.put(nums[j-1], freq.getOrDefault(nums[j-1], 0)+1);
                if (freq.get(nums[j-1]) == 2) trimmed += 2;
                else if (freq.get(nums[j-1]) > 2) trimmed++;
                dp[i] = Math.min(dp[i], dp[j-1] + k + trimmed);
            }
        }
        return dp[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun minCost(nums: IntArray, k: Int): Int {
        val n = nums.size
        val dp = IntArray(n+1) { Int.MAX_VALUE }
        dp[0] = 0
        for (i in 1..n) {
            val freq = mutableMapOf<Int,Int>()
            var trimmed = 0
            for (j in i downTo 1) {
                freq[nums[j-1]] = freq.getOrDefault(nums[j-1],0)+1
                if (freq[nums[j-1]] == 2) trimmed += 2
                else if (freq[nums[j-1]]!! > 2) trimmed++
                dp[i] = minOf(dp[i], dp[j-1] + k + trimmed)
            }
        }
        return dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def minCost(self, nums: list[int], k: int) -> int:
        n = len(nums)
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            freq = {}
            trimmed = 0
            for j in range(i, 0, -1):
                freq[nums[j-1]] = freq.get(nums[j-1], 0) + 1
                if freq[nums[j-1]] == 2:
                    trimmed += 2
                elif freq[nums[j-1]] > 2:
                    trimmed += 1
                dp[i] = min(dp[i], dp[j-1] + k + trimmed)
        return dp[n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn min_cost(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let mut dp = vec![i32::MAX; n+1];
        dp[0] = 0;
        for i in 1..=n {
            let mut freq = std::collections::HashMap::new();
            let mut trimmed = 0;
            for j in (1..=i).rev() {
                *freq.entry(nums[j-1]).or_insert(0) += 1;
                if freq[&nums[j-1]] == 2 { trimmed += 2; }
                else if freq[&nums[j-1]] > 2 { trimmed += 1; }
                dp[i] = dp[i].min(dp[j-1] + k + trimmed);
            }
        }
        dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    minCost(nums: number[], k: number): number {
        const n = nums.length;
        const dp = Array(n+1).fill(Infinity);
        dp[0] = 0;
        for (let i = 1; i <= n; ++i) {
            const freq: Record<number, number> = {};
            let trimmed = 0;
            for (let j = i; j >= 1; --j) {
                freq[nums[j-1]] = (freq[nums[j-1]] || 0) + 1;
                if (freq[nums[j-1]] === 2) trimmed += 2;
                else if (freq[nums[j-1]] > 2) trimmed++;
                dp[i] = Math.min(dp[i], dp[j-1] + k + trimmed);
            }
        }
        return dp[n];
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) where n is the length of nums, due to nested loops.
  • 🧺 Space complexity: O(n) for the DP array.