Watch 10 video solutions for Divide an Array Into Subarrays With Minimum Cost II, a hard level problem involving Array, Hash Table, Sliding Window. This walkthrough by codestorywithMIK has 14,587 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed array of integers nums of length n, and two positive integers k and dist.
The cost of an array is the value of its first element. For example, the cost of [1,2,3] is 1 while the cost of [3,4,1] is 3.
You need to divide nums into k disjoint contiguous subarrays, such that the difference between the starting index of the second subarray and the starting index of the kth subarray should be less than or equal to dist. In other words, if you divide nums into the subarrays nums[0..(i1 - 1)], nums[i1..(i2 - 1)], ..., nums[ik-1..(n - 1)], then ik-1 - i1 <= dist.
Return the minimum possible sum of the cost of these subarrays.
Example 1:
Input: nums = [1,3,2,6,4,2], k = 3, dist = 3 Output: 5 Explanation: The best possible way to divide nums into 3 subarrays is: [1,3], [2,6,4], and [2]. This choice is valid because ik-1 - i1 is 5 - 2 = 3 which is equal to dist. The total cost is nums[0] + nums[2] + nums[5] which is 1 + 2 + 2 = 5. It can be shown that there is no possible way to divide nums into 3 subarrays at a cost lower than 5.
Example 2:
Input: nums = [10,1,2,2,2,1], k = 4, dist = 3 Output: 15 Explanation: The best possible way to divide nums into 4 subarrays is: [10], [1], [2], and [2,2,1]. This choice is valid because ik-1 - i1 is 3 - 1 = 2 which is less than dist. The total cost is nums[0] + nums[1] + nums[2] + nums[3] which is 10 + 1 + 2 + 2 = 15. The division [10], [1], [2,2,2], and [1] is not valid, because the difference between ik-1 and i1 is 5 - 1 = 4, which is greater than dist. It can be shown that there is no possible way to divide nums into 4 subarrays at a cost lower than 15.
Example 3:
Input: nums = [10,8,18,9], k = 3, dist = 1 Output: 36 Explanation: The best possible way to divide nums into 4 subarrays is: [10], [8], and [18,9]. This choice is valid because ik-1 - i1 is 2 - 1 = 1 which is equal to dist.The total cost is nums[0] + nums[1] + nums[2] which is 10 + 8 + 18 = 36. The division [10], [8,18], and [9] is not valid, because the difference between ik-1 and i1 is 3 - 1 = 2, which is greater than dist. It can be shown that there is no possible way to divide nums into 3 subarrays at a cost lower than 36.
Constraints:
3 <= n <= 1051 <= nums[i] <= 1093 <= k <= nk - 2 <= dist <= n - 2Problem Overview: You need to divide an array into k subarrays while minimizing the total cost, where the cost depends on the first element of each chosen subarray. The challenge is selecting valid split positions that minimize the sum while respecting distance constraints between indices.
Approach 1: Brute Force Enumeration (O(n * dist log dist) time, O(dist) space)
The straightforward strategy checks every valid group of candidate indices that could start the remaining k-1 subarrays. For each starting index, iterate through the allowed window of size dist, collect possible values, sort them, and pick the smallest k-1. This guarantees the minimal cost for that window but repeats sorting work for overlapping windows. The approach relies mainly on basic array iteration and simple comparisons. While easy to reason about, it becomes slow when the array or distance constraint grows because each window recomputes the same ordering work.
Approach 2: Sliding Window with Two Heaps (O(n log dist) time, O(dist) space)
A more efficient solution maintains the smallest k-1 candidate values dynamically as the window moves. Treat the valid region for split points as a sliding window of size dist. Inside the window, keep two priority queues: one heap storing the current k-1 smallest values contributing to the cost, and another heap storing the remaining candidates. When the window shifts, insert the new element, remove the outgoing one, and rebalance the heaps so the smallest k-1 elements remain selected. A running sum tracks the cost contribution of the selected heap. Using a heap (priority queue) allows each insertion or removal to be handled in O(log dist), eliminating repeated sorting.
Lazy deletion or index tracking ensures that elements leaving the window do not corrupt heap ordering. As the window slides across the array, update the candidate structure and compute the minimal cost for each valid configuration. The final answer is the smallest total cost encountered.
Recommended for interviews: Interviewers expect the sliding window with heaps approach. The brute force method shows you understand the problem structure and constraints. The optimized approach demonstrates mastery of window maintenance, heap balancing, and efficient state updates—skills frequently tested in hard array and data‑structure problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n * dist log dist) | O(dist) | Useful for understanding the problem and validating logic on small inputs |
| Sliding Window + Two Heaps | O(n log dist) | O(dist) | General optimal solution for large arrays and tight distance constraints |