We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Split an Array

Number: 2633

Difficulty: Hard

Paid? No

Companies: Indeed

Problem Description

Given an integer array nums and an integer k, we need to split the array into one or more contiguous subarrays. The cost of a subarray is defined as k plus the length of its "trimmed" version – where trimmed version means removing all numbers that appear only once. Our goal is to minimize the total cost of the split over all subarrays.

Key Insights

  • Use dynamic programming where dp[i] stores the minimum cost to partition nums[0...i-1].
  • The cost of a subarray is k plus the number of repeated elements (in the trimmed version).
  • Maintain a frequency map while expanding a subarray backwards to compute the duplicate cost dynamically.
  • When a number’s frequency increases:
    • From 1 to 2, add 2 to the cost (since both instances become part of the trimmed array).
    • From 2 or more to one additional, add 1.
  • Iterating backward for each partition point efficiently updates the duplicate cost and allows exploration of all possible splits ending at the current index.

Space and Time Complexity

Time Complexity: O(n^2) in worst-case due to the nested loops (where n is the length of nums).
Space Complexity: O(n) for the dp array and frequency map.

Solution

We use a dynamic programming approach. Let dp[i] denote the minimum cost to split the first i elements. For every possible ending index i, iterate backwards to update the frequency counts and calculate the extra cost incurred by duplicates for the current subarray. Then, update dp[i] with the best (minimum) possible cost considering the cost of the current subarray (which is k plus the duplicate cost) added to dp[j-1] where j is the starting index of the subarray. This method ensures all valid splits are considered and the minimum overall cost is found.

Code Solutions

def minCost(nums, k):
    n = len(nums)
    dp = [float('inf')] * (n + 1)
    dp[0] = 0  # Base case: cost is 0 for empty array split
    
    # Process each possible endpoint of the subarray
    for i in range(1, n + 1):
        freq = {}
        duplicate_cost = 0
        # Try every possible start index for the subarray ending at i-1
        for j in range(i, 0, -1):
            num = nums[j - 1]
            freq[num] = freq.get(num, 0) + 1
            # Update duplicate cost based on frequency
            if freq[num] == 2:
                duplicate_cost += 2
            elif freq[num] > 2:
                duplicate_cost += 1
            dp[i] = min(dp[i], dp[j - 1] + k + duplicate_cost)
    return dp[n]

# Example usage
print(minCost([1,2,1,2,1,3,3], 2))
← Back to All Questions