Skip to main content
Talentd

Divide an Array Into Subarrays With Minimum Cost II - Solution & Explanation

HardArrayHash TableSliding WindowHeap (Priority Queue)31 min readAsked at: Amazon, American Express, Jio +1
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 109
  • 3 <= k <= n
  • k - 2 <= dist <= n - 2

Approach Overview

Problem 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 1: Brute Force Approach

The brute force approach involves examining every possible combination to find the solution. Although this is not optimal, it is a straightforward way to ensure that all possibilities are covered.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) because it checks every combination.
Space Complexity: O(1) because it uses a constant amount of space.

Try this approach in the editor →

Approach 2: Optimized Approach Using Dynamic Programming

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is used here to store results of subproblems to avoid redundant calculations.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) due to memoization.
Space Complexity: O(n) because of the additional data structure used for storage.

Try this approach in the editor →

Approach 3: Ordered Set

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^2) because it checks every combination.
Space Complexity: O(1) because it uses a constant amount of space.

Optimized Approach Using Dynamic Programming

Time Complexity: O(n) due to memoization.
Space Complexity: O(n) because of the additional data structure used for storage.

Ordered Set—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n * dist log dist)O(dist)Useful for understanding the problem and validating logic on small inputs
Sliding Window + Two HeapsO(n log dist)O(dist)General optimal solution for large arrays and tight distance constraints

Video Solution

Divide an Array Into Subarrays With Minimum Cost II | Detailed Intuition | Leetcode 3013 | MIK • codestorywithMIK • 15,160 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Divide an Array Into Subarrays With Minimum Cost II easy or hard?
Divide an Array Into Subarrays With Minimum Cost II is classified as a Hard problem. The difficulty comes from combining sliding window constraints with dynamic selection of the smallest elements using heaps, which requires careful handling of insertions, removals, and balancing.
Divide an Array Into Subarrays With Minimum Cost II Python/Java solution
Implementations typically use heaps: Python uses heapq with additional structures for lazy deletion, while Java implementations rely on PriorityQueue. Both versions maintain two heaps and a running sum to track the smallest k-1 values inside the sliding window.
How to solve Divide an Array Into Subarrays With Minimum Cost II in O(n log d)?
Maintain a sliding window of size dist that represents valid split candidates. Use two heaps: one storing the smallest k-1 elements contributing to the cost and another storing the remaining elements. As the window shifts, insert the new value, lazily remove expired ones, rebalance the heaps, and keep a running sum of the selected elements.
What is the best approach for Divide an Array Into Subarrays With Minimum Cost II?
The most efficient approach uses a sliding window combined with two heaps (priority queues). The window maintains valid candidate indices while the heaps track the smallest k-1 values contributing to the cost. This allows efficient updates as the window moves and reduces the complexity to O(n log dist) time with O(dist) extra space.
Is Divide an Array Into Subarrays With Minimum Cost II asked at Google/Amazon/Meta?
Problems involving sliding windows, heap balancing, and dynamic candidate selection are common in interviews at companies like Google, Amazon, and Meta. Hard array optimization questions similar to this appear in onsite rounds to evaluate data‑structure design and complexity reasoning.
What data structure is used in Divide an Array Into Subarrays With Minimum Cost II?
The optimal solution relies on priority queues (heaps) to maintain the smallest k-1 values efficiently. It also uses a sliding window over the array and sometimes auxiliary structures like hash maps for lazy deletion of elements leaving the window.
What is the time complexity of Divide an Array Into Subarrays With Minimum Cost II?
The optimal solution runs in O(n log dist) time because each element entering or leaving the sliding window triggers heap insertions or removals. The brute force approach is significantly slower, often O(n * dist log dist), since it repeatedly sorts candidate values inside each window.

Ready to solve this problem?

Practice Divide an Array Into Subarrays With Minimum Cost II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Cost to Cut a Stick

Next

Minimum Cost to Split an Array