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.
This C code provides a basic framework for implementing a brute force solution. Notice how the main function calls a separate function to encapsulate the solution. You can implement the actual brute-force logic within the solveBruteForce function.
Time Complexity: O(n^2) because it checks every combination.
Space Complexity: O(1) because it uses a constant amount of space.
This C code provides a basic framework for implementing a dynamic programming solution. The solveDynamicProgramming function is where you would implement the memoization or tabulation logic needed for the solution.
Time Complexity: O(n) due to memoization.
Space Complexity: O(n) because of the additional data structure used for storage.
The problem requires us to divide the array nums into k consecutive and non-overlapping subarrays, and the distance between the first element of the second subarray and the first element of the k-th subarray should not exceed dist. This is equivalent to finding a subarray of size dist+1 starting from the element at index 1 in nums, and calculating the sum of the smallest k-1 elements in it. We subtract 1 from k, so we only need to find the sum of the smallest k elements and add nums[0] to it.
We can use two ordered sets l and r to maintain the elements of the window of size dist + 1. The set l maintains the smallest k elements, while the set r maintains the remaining elements of the window. We maintain a variable s to represent the sum of nums[0] and the elements in l. Initially, we add the sum of the first dist+2 elements to s and add all elements with indices [1, dist + 1] to l. If the size of l is greater than k, we repeatedly move the largest element from l to r until the size of l equals k, updating the value of s in the process.
At this point, the initial answer is ans = s.
Next, we traverse nums starting from dist+2. For each element nums[i], we need to remove nums[i-dist-1] from either l or r, and then add nums[i] to either l or r. If nums[i] is less than the largest element in l, we add nums[i] to l; otherwise, we add it to r. If the size of l is less than k, we move the smallest element from r to l until the size of l equals k. If the size of l is greater than k, we move the largest element from l to r until the size of l equals k. During this process, we update the value of s and update ans = min(ans, s).
The final answer is ans.
The time complexity is O(n times log dist), and the space complexity is O(dist). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) because it checks every combination. |
| Optimized Approach Using Dynamic Programming | Time Complexity: O(n) due to memoization. |
| Ordered Set | — |
| 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 |
Divide an Array Into Subarrays With Minimum Cost II | Detailed Intuition | Leetcode 3013 | MIK • codestorywithMIK • 14,587 views views
Watch 9 more video solutions →Practice Divide an Array Into Subarrays With Minimum Cost II with our built-in code editor and test cases.
Practice on FleetCode