Minimum Cost to Split an Array
01 · Problem
You are given an integer array nums and an integer k. Split nums into one or more non-empty contiguous subarrays (every element belongs to exactly one subarray).
The importance of a subarray is k + t, where t is the number of elements in that subarray whose value appears at least twice in the subarray (counting every copy). For example, in [1,2,1,3,3,4] the values 1 and 3 repeat, so t = 4.
The cost of a split is the sum of the importances of its subarrays. Return the minimum possible cost.
02 · Examples
nums = [1,2,1,2,1,3,3], k = 2
8
Split into [1,2] and [1,2,1,3,3]. The first has importance 2 + 0 = 2. In the second, 1 appears twice and 3 appears twice, so t = 4 and importance = 2 + 4 = 6. Total 8.
nums = [1,2,1,2,1], k = 2
6
Split into [1,2] (importance 2 + 0) and [1,2,1] (1 repeats twice, importance 2 + 2). Total 6.
nums = [1,2,1,2,1], k = 5
10
Keep the whole array: every element's value repeats, so t = 5 and the importance is 5 + 5 = 10. Any split costs more because each extra piece adds 5.
03 · Constraints
- 011 <= nums.length <= 1000
- 020 <= nums[i] < nums.length
- 031 <= k <= 109
04 · Optimal complexity
- Time
- O(n^2)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.