Leetcode 2547. 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

Explanation is important.

1. Subarray: A contiguous non-empty sequence of elements in the array.

Example: Subarrays of [1, 2, 3] include [1], [1, 2], [2, 3], [1, 2, 3].

2. Trimmed version of a subarray: Remove all elements that appear exactly once in the subarray.

Example: subarray = [3, 1, 2, 4, 3, 4]

Trimmed version: [3, 4, 3, 4] (since 1 and 2 appear only once, they are removed).

3. Importance value of a subarray: importance value=k+length of trimmed(subarray)

Example: If subarray = [1, 2, 3, 3, 3, 4, 4] so the Trimmed version: [3, 3, 3, 4, 4] and Importance value: 𝑘 +5, where 5 is the length of [3, 3, 3, 4, 4].

Cost of a split: Sum of the importance values of all subarrays in the split. Example: If the split is [[3, 1], [2, 4], [3, 4]], the total cost is the sum of importance values of each subarray in the split.

Therefore, the main Objective is to minimize the total cost of splitting nums into subarrays.

Goal:Split the array nums into some number of non-empty subarrays such that the total cost of the split is minimized.

Java Solution: Minimum Cost to Split an Array

class Solution {
    public int minCost(int[] nums, int k) {
        int n = nums.length;
        int[][] cost = new int[n][n];
        
        for(int length = n; length >= 1; length--){
            dfsCompute(cost, nums, length, k);
        }
        
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = k;
        for(int i = 1; i < n; i++){
            dp[i] = cost[0][i];
            for(int j = 0; j < i; j++){
                dp[i] = Math.min(dp[i], dp[j] + cost[j+1][i]);
            }
        }
        return dp[n-1];
    }
    
    private void dfsCompute(int[][] cost, int[] nums, int length , int k){//sliding window
        int[] freq = new int[1001];
        Set distinct = new HashSet<>();
        for(int i = 0; i < length; i++){
            freq[nums[i]]++;
            if(freq[nums[i]] == 1) distinct.add(nums[i]);
            if(freq[nums[i]] > 1 || freq[nums[i]] == 0) distinct.remove(nums[i]); //trimmed version
        }
        
        cost[0][length - 1] = length - distinct.size() + k;
        
        for(int i = length; i < cost.length; i++){
            int l = i - length;
            freq[nums[i]]++;
            if(freq[nums[i]] == 1) distinct.add(nums[i]);
            if((freq[nums[i]] > 1 || freq[nums[i]] == 0) && distinct.contains(nums[i]))  distinct.remove(nums[i]); //trimmed version
            
            freq[nums[l]]--;
            if(freq[nums[l]] == 1) distinct.add(nums[l]);
            if((freq[nums[l]] > 1 || freq[nums[l]] == 0) && distinct.contains(nums[l]))  distinct.remove(nums[l]); //trimmed version
            cost[l+1][i] = length - distinct.size() + k;
        }
        return;
    }
}                    
                    
                    

Time Complexity Analysis

Time Complexity: O(n^2) (from both compute and minCost methods).

The compute method processes all possible subarrays of a given length using a sliding window technique.

for each length, The sliding window iterates through the array in O(n), updating frequencies and calculating costs for subarrays.

Across all len, You iterate from len = n to 1. This means you process subarrays of all lengths, which sums to O(n^2).

Thus, the compute method runs in O(n^2) for precomputing costs for all subarrays.

Thus, the DP computation takes O(n^2) time. because the outer loop iterate through all indices from 1 to n - 1 that takes O(n).

The inner loop iterates through all possible split points j where j < i that takes O(n).

Space Complexity:O(n^2) (dominated by the cost array).

The cost array stores the cost for all possible subarrays, requiring O(n^2) space.

The dp array and Space for freq Array and distinct Set requires O(n) space.