Divide an Array Into Subarrays With Minimum Cost II
Divide an Array Into Subarrays With Minimum Cost II is a hard heaps problem solved with the advanced pattern.
The best approach, optimal (sliding window + fenwick tree over value ranks), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (sort every window) up.
Problem
You are given an integer array nums of length n and two integers k and dist. The cost of a contiguous piece of the array is its first element.
Cut nums into exactly k non-empty contiguous pieces. If the pieces after the first one start at indices i1 < i2 < ... < i(k-1), the cut is allowed only when i(k-1) - i1 <= dist, that is, the second piece and the last piece start at most dist positions apart.
Return the minimum possible total cost of an allowed cut.
Examples
Example 1
- Input
nums = [4, 2, 7, 1, 5, 3], k = 3, dist = 2- Output
7- Why
- Start the pieces at indices 0, 1 and 3: [4], [2, 7], [1, 5, 3]. The second and last pieces start 3 - 1 = 2 apart, and the cost is 4 + 2 + 1 = 7.
Example 2
- Input
nums = [10, 8, 1, 9, 2, 6], k = 4, dist = 3- Output
19- Why
- Start the pieces at 0, 2, 4 and 5: the costs are 10 + 1 + 2 + 6 = 19, and 5 - 2 = 3 <= dist.
Example 3
- Input
nums = [5, 3, 9], k = 3, dist = 1- Output
17- Why
- Three pieces of length 1 are the only option, so every element is paid: 5 + 3 + 9.
Constraints
3 <= n == nums.length <= 10^51 <= nums[i] <= 10^93 <= k <= nk - 2 <= dist <= n - 2
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (sort every window) | O(n · d log d) | O(d) |
| Optimal (sliding window + Fenwick tree over value ranks) | O(n log n) | O(n) |
1Brute force (sort every window)
O(n · d log d)Up to n windows, each of size d = dist + 1, each sorted.O(d)One window copy at a time.The starts of pieces 2..k are any k - 1 indices in [1, n - 1] whose spread is at most dist, so they always fit inside a window [i, i + dist]. For each such window, sort its values and add up the k - 1 smallest. The answer is nums[0] plus the best window.
- For i from 1 while i + dist <= n - 1:
- Copy nums[i..i + dist], sort it, and sum the first k - 1 values.
- Keep the minimum sum; return nums[0] + minimum.
class Solution {
public long minimumCost(int[] nums, int k, int dist) {
int n = nums.length;
long best = Long.MAX_VALUE;
for (int i = 1; i + dist <= n - 1; i++) {
int[] w = Arrays.copyOfRange(nums, i, i + dist + 1);
Arrays.sort(w);
long s = 0;
for (int j = 0; j < k - 1; j++) s += w[j];
best = Math.min(best, s);
}
return nums[0] + best;
}
}class Solution:
def minimumCost(self, nums: List[int], k: int, dist: int) -> int:
n = len(nums)
best = float("inf")
i = 1
while i + dist <= n - 1:
w = sorted(nums[i:i + dist + 1])
best = min(best, sum(w[:k - 1]))
i += 1
return nums[0] + bestclass Solution {
public:
long long minimumCost(vector<int>& nums, int k, int dist) {
int n = nums.size();
long long best = LLONG_MAX;
for (int i = 1; i + dist <= n - 1; i++) {
vector<int> w(nums.begin() + i, nums.begin() + i + dist + 1);
sort(w.begin(), w.end());
long long s = 0;
for (int j = 0; j < k - 1; j++) s += w[j];
best = min(best, s);
}
return nums[0] + best;
}
};function minimumCost(nums, k, dist) {
const n = nums.length;
let best = Infinity;
for (let i = 1; i + dist <= n - 1; i++) {
const w = nums.slice(i, i + dist + 1).sort((a, b) => a - b);
let s = 0;
for (let j = 0; j < k - 1; j++) s += w[j];
best = Math.min(best, s);
}
return nums[0] + best;
}2Optimal (sliding window + Fenwick tree over value ranks)
O(n log n)Sorting for the ranks, then n window moves and n queries, each O(log n) on the trees.O(n)The rank array and two Fenwick trees of size up to n.Compress the values of nums[1..n-1] to ranks and keep two Fenwick trees indexed by rank: one counts how many window elements have each value, the other sums them. Sliding the window is one removal and one insertion. The sum of the m smallest values is found by walking down the tree: take whole blocks while the count stays below m, then take the remaining copies of the next value.
- Sort and deduplicate nums[1..n-1] into uniq; rank(x) = position of x in uniq (1-based).
- Insert nums[1..1 + dist] into both trees; best = sumSmallest(k - 1).
- For i = 2 while i + dist <= n - 1: remove nums[i - 1], insert nums[i + dist], best = min(best, sumSmallest(k - 1)).
- sumSmallest(m): descend from the highest power of two; extend pos while pos + step <= size and the count so far plus cnt[pos + step] < m, adding counts and sums. Then add (m - count) * uniq[pos].
- Return nums[0] + best.
class Solution {
private int size;
private int[] cnt;
private long[] sum;
private int[] uniq;
public long minimumCost(int[] nums, int k, int dist) {
int n = nums.length;
int[] vals = Arrays.copyOfRange(nums, 1, n);
Arrays.sort(vals);
int u = 0;
for (int i = 0; i < vals.length; i++) {
if (i == 0 || vals[i] != vals[i - 1]) vals[u++] = vals[i];
}
uniq = Arrays.copyOf(vals, u);
size = u;
cnt = new int[u + 1];
sum = new long[u + 1];
for (int j = 1; j <= 1 + dist; j++) update(nums[j], 1);
long best = smallest(k - 1);
for (int i = 2; i + dist <= n - 1; i++) {
update(nums[i - 1], -1);
update(nums[i + dist], 1);
best = Math.min(best, smallest(k - 1));
}
return nums[0] + best;
}
private void update(int x, int d) {
for (int i = Arrays.binarySearch(uniq, x) + 1; i <= size; i += i & -i) {
cnt[i] += d;
sum[i] += (long) d * x;
}
}
private long smallest(int m) {
int pos = 0, c = 0;
long s = 0;
int step = Integer.highestOneBit(size);
for (; step > 0; step >>= 1) {
int nxt = pos + step;
if (nxt <= size && c + cnt[nxt] < m) {
pos = nxt;
c += cnt[nxt];
s += sum[nxt];
}
}
return s + (long) (m - c) * uniq[pos];
}
}class Solution:
def minimumCost(self, nums: List[int], k: int, dist: int) -> int:
n = len(nums)
uniq = sorted(set(nums[1:]))
rank = {v: i + 1 for i, v in enumerate(uniq)}
size = len(uniq)
cnt = [0] * (size + 1)
sm = [0] * (size + 1)
def update(x: int, d: int) -> None:
i = rank[x]
while i <= size:
cnt[i] += d
sm[i] += d * x
i += i & -i
top = 1
while top * 2 <= size:
top *= 2
def smallest(m: int) -> int:
pos = c = s = 0
step = top
while step > 0:
nxt = pos + step
if nxt <= size and c + cnt[nxt] < m:
pos = nxt
c += cnt[nxt]
s += sm[nxt]
step >>= 1
return s + (m - c) * uniq[pos]
for j in range(1, 2 + dist):
update(nums[j], 1)
best = smallest(k - 1)
i = 2
while i + dist <= n - 1:
update(nums[i - 1], -1)
update(nums[i + dist], 1)
best = min(best, smallest(k - 1))
i += 1
return nums[0] + bestclass Solution {
int size;
vector<int> cnt, uniq;
vector<long long> sm;
void update(int x, int d) {
int i = lower_bound(uniq.begin(), uniq.end(), x) - uniq.begin() + 1;
for (; i <= size; i += i & -i) {
cnt[i] += d;
sm[i] += (long long)d * x;
}
}
long long smallest(int m) {
int pos = 0, c = 0;
long long s = 0;
int step = 1;
while (step * 2 <= size) step *= 2;
for (; step > 0; step >>= 1) {
int nxt = pos + step;
if (nxt <= size && c + cnt[nxt] < m) {
pos = nxt;
c += cnt[nxt];
s += sm[nxt];
}
}
return s + (long long)(m - c) * uniq[pos];
}
public:
long long minimumCost(vector<int>& nums, int k, int dist) {
int n = nums.size();
uniq.assign(nums.begin() + 1, nums.end());
sort(uniq.begin(), uniq.end());
uniq.erase(unique(uniq.begin(), uniq.end()), uniq.end());
size = uniq.size();
cnt.assign(size + 1, 0);
sm.assign(size + 1, 0);
for (int j = 1; j <= 1 + dist; j++) update(nums[j], 1);
long long best = smallest(k - 1);
for (int i = 2; i + dist <= n - 1; i++) {
update(nums[i - 1], -1);
update(nums[i + dist], 1);
best = min(best, smallest(k - 1));
}
return nums[0] + best;
}
};function minimumCost(nums, k, dist) {
const n = nums.length;
const uniq = [...new Set(nums.slice(1))].sort((a, b) => a - b);
const rank = new Map();
uniq.forEach((v, i) => rank.set(v, i + 1));
const size = uniq.length;
const cnt = new Array(size + 1).fill(0);
const sm = new Array(size + 1).fill(0);
const update = (x, d) => {
for (let i = rank.get(x); i <= size; i += i & -i) {
cnt[i] += d;
sm[i] += d * x;
}
};
let top = 1;
while (top * 2 <= size) top *= 2;
const smallest = (m) => {
let pos = 0, c = 0, s = 0;
for (let step = top; step > 0; step >>= 1) {
const nxt = pos + step;
if (nxt <= size && c + cnt[nxt] < m) {
pos = nxt;
c += cnt[nxt];
s += sm[nxt];
}
}
return s + (m - c) * uniq[pos];
};
for (let j = 1; j <= 1 + dist; j++) update(nums[j], 1);
let best = smallest(k - 1);
for (let i = 2; i + dist <= n - 1; i++) {
update(nums[i - 1], -1);
update(nums[i + dist], 1);
best = Math.min(best, smallest(k - 1));
}
return nums[0] + best;
}Edge cases to test
- k = n: every element starts its own piece, so the answer is the total sum
- dist = k - 2: the chosen starts must be consecutive indices
- dist = n - 2: the distance rule never binds, so take the k - 1 smallest of nums[1..n-1]
- Large values, where the answer exceeds 32-bit range
Hints
Hint 1
The first piece always starts at index 0, so nums[0] is always paid. The real choice is the other k - 1 starting indices, taken from 1..n-1.
Hint 2
Those k - 1 indices just have to fit inside some window of length dist + 1. For a fixed window, the best choice is its k - 1 smallest values.
Hint 3
Slide the window one step at a time and keep a structure that can add a value, remove a value and report the sum of the m smallest values quickly.
FAQ
What is the best time complexity for Divide an Array Into Subarrays With Minimum Cost II?
Optimal (sliding window + Fenwick tree over value ranks) runs in O(n log n) time and O(n) extra space. Sorting for the ranks, then n window moves and n queries, each O(log n) on the trees.
Which pattern does Divide an Array Into Subarrays With Minimum Cost II use?
It is a heaps problem that uses the advanced pattern. Other problems with the same pattern: Find K Pairs with Smallest Sums, Find Median from Data Stream, Trapping Rain Water II.
Is there a brute force solution for Divide an Array Into Subarrays With Minimum Cost II?
Yes. Brute force (sort every window) takes O(n · d log d) time and O(d) space. The starts of pieces 2..k are any k - 1 indices in [1, n - 1] whose spread is at most dist, so they always fit inside a window [i, i + dist].
Which edge cases should I test for Divide an Array Into Subarrays With Minimum Cost II?
k = n: every element starts its own piece, so the answer is the total sum; dist = k - 2: the chosen starts must be consecutive indices; dist = n - 2: the distance rule never binds, so take the k - 1 smallest of nums[1..n-1]; Large values, where the answer exceeds 32-bit range.