Divide an Array Into Subarrays With Minimum Cost II solution and explanation
Google
9 more videos on this problem
Divide an Array Into Subarrays With Minimum Cost II | Detailed Intuition | Leetcode 3013 | MIKcodestorywithMIK · 55:15 · 15K views
3013. Divide an Array Into Subarrays With Minimum Cost II | Sliding Window | MultisetsAryan Mittal · 33:09 · 5K views
3013. Divide an Array Into Subarrays With Minimum Cost II | Leetcode Daily - PythonLeetcode Daily · 9:32 · 1K views
3013. Divide an Array Into Subarrays With Minimum Cost II | Leetcode Biweekly 122codingMohan · 50:42 · 1K views
Divide an Array Into Subarrays With Minimum Cost II | LeetCode 3013 | Sliding Window + TreeSet Study Placement · 36:17 · 1K views
Daily Leetcode #2134: Feb 02, 2026 - 3013. Divide an Array Into Subarrays With Minimum Cost IIProgramming Live with Larry · 22:42 · 876 views
Divide an Array Into Subarrays With Minimum Cost II | LeetCode 3013 - Pythonimpoldev · 22:06 · 656 views
3013. Divide an Array Into Subarrays With Minimum Cost II (Leetcode Hard)Programming Live with Larry · 32:53 · 621 views
【每日一题】LeetCode 3013. Divide an Array Into Subarrays With Minimum Cost IIHuifeng Guan · 19:05 · 584 views
Divide an Array Into Subarrays With Minimum Cost II | LeetCode 3013 | Sliding Window | MultisetscodeTips · 22:41 · 568 views
The problem
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 - 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
def solve_brute_force():
# Implement your brute force solution here
pass
solve_brute_force()public class Solution {
public static void solveBruteForce() {
// Implement your brute force solution here
}
public static void main(String[] args) {
solveBruteForce();
}
}#include <iostream>
using namespace std;
void solveBruteForce() {
// Implement your brute force solution here
}
int main() {
solveBruteForce();
return 0;
}function solveBruteForce() {
// Implement your brute force solution here
}
solveBruteForce();#include <stdio.h>
void solveBruteForce() {
// Implement your brute force solution here
}
int main() {
solveBruteForce();
return 0;
}using System;
class Solution {
static void SolveBruteForce() {
// Implement your brute force solution here
}
static void Main() {
SolveBruteForce();
}
}This Python code outlines a function for a brute force solution. Implement the solution logic inside the solve_brute_force function.
Time Complexity: O(n^2) because it checks every combination.
Space Complexity: O(1) because it uses a constant amount of space.
Approach 2: Optimized Approach Using Dynamic Programming
def solve_dynamic_programming():
# Implement your dynamic programming solution here
pass
solve_dynamic_programming()import java.util.*;
public class Solution {
public static void solveDynamicProgramming() {
// Implement your dynamic programming solution here
}
public static void main(String[] args) {
solveDynamicProgramming();
}
}#include <iostream>
#include <vector>
using namespace std;
void solveDynamicProgramming() {
// Implement your dynamic programming solution here
}
int main() {
solveDynamicProgramming();
return 0;
}function solveDynamicProgramming() {
// Implement your dynamic programming solution here
}
solveDynamicProgramming();#include <stdio.h>
void solveDynamicProgramming() {
// Implement your dynamic programming solution here
}
int main() {
solveDynamicProgramming();
return 0;
}using System;
using System.Collections.Generic;
class Solution {
static void SolveDynamicProgramming() {
// Implement your dynamic programming solution here
}
static void Main() {
SolveDynamicProgramming();
}
}This Python code provides a function for setting up the dynamic programming approach. Implement your solution logic in the solve_dynamic_programming function, utilizing lists or dictionaries for memoization.
Time Complexity: O(n) due to memoization.
Space Complexity: O(n) because of the additional data structure used for storage.
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.
function minimumCost(nums: number[], k: number, dist: number): number {
--k;
const l = new TreapMultiSet<number>((a, b) => a - b);
const r = new TreapMultiSet<number>((a, b) => a - b);
let s = nums[0];
for (let i = 1; i < dist + 2; ++i) {
s += nums[i];
l.add(nums[i]);
}
const l2r = () => {
const x = l.pop()!;
s -= x;
r.add(x);
};
const r2l = () => {
const x = r.shift()!;
l.add(x);
s += x;
};
while (l.size > k) {
l2r();
}
let ans = s;
for (let i = dist + 2; i < nums.length; ++i) {
const x = nums[i - dist - 1];
if (l.has(x)) {
l.delete(x);
s -= x;
} else {
r.delete(x);
}
const y = nums[i];
if (y < l.last()!) {
l.add(y);
s += y;
} else {
r.add(y);
}
while (l.size < k) {
r2l();
}
while (l.size > k) {
l2r();
}
ans = Math.min(ans, s);
}
return ans;
}
type CompareFunction<T, R extends 'number' | 'boolean'> = (
a: T,
b: T,
) => R extends 'number' ? number : boolean;
interface ITreapMultiSet<T> extends Iterable<T> {
add: (...value: T[]) => this;
has: (value: T) => boolean;
delete: (value: T) => void;
bisectLeft: (value: T) => number;
bisectRight: (value: T) => number;
indexOf: (value: T) => number;
lastIndexOf: (value: T) => number;
at: (index: number) => T | undefined;
first: () => T | undefined;
last: () => T | undefined;
lower: (value: T) => T | undefined;
higher: (value: T) => T | undefined;
floor: (value: T) => T | undefined;
ceil: (value: T) => T | undefined;
shift: () => T | undefined;
pop: (index?: number) => T | undefined;
count: (value: T) => number;
keys: () => IterableIterator<T>;
values: () => IterableIterator<T>;
rvalues: () => IterableIterator<T>;
entries: () => IterableIterator<[number, T]>;
readonly size: number;
}
class TreapNode<T = number> {
value: T;
count: number;
size: number;
priority: number;
left: TreapNode<T> | null;
right: TreapNode<T> | null;
constructor(value: T) {
this.value = value;
this.count = 1;
this.size = 1;
this.priority = Math.random();
this.left = null;
this.right = null;
}
static getSize(node: TreapNode<any> | null): number {
return node?.size ?? 0;
}
static getFac(node: TreapNode<any> | null): number {
return node?.priority ?? 0;
}
pushUp(): void {
let tmp = this.count;
tmp += TreapNode.getSize(this.left);
tmp += TreapNode.getSize(this.right);
this.size = tmp;
}
rotateRight(): TreapNode<T> {
// eslint-disable-next-line @typescript-eslint/no-this-alias
let node: TreapNode<T> = this;
const left = node.left;
node.left = left?.right ?? null;
left && (left.right = node);
left && (node = left);
node.right?.pushUp();
node.pushUp();
return node;
}
rotateLeft(): TreapNode<T> {
// eslint-disable-next-line @typescript-eslint/no-this-alias
let node: TreapNode<T> = this;
const right = node.right;
node.right = right?.left ?? null;
right && (right.left = node);
right && (node = right);
node.left?.pushUp();
node.pushUp();
return node;
}
}
class TreapMultiSet<T = number> implements ITreapMultiSet<T> {
private readonly root: TreapNode<T>;
private readonly compareFn: CompareFunction<T, 'number'>;
private readonly leftBound: T;
private readonly rightBound: T;
constructor(compareFn?: CompareFunction<T, 'number'>);
constructor(compareFn: CompareFunction<T, 'number'>, leftBound: T, rightBound: T);
constructor(
compareFn: CompareFunction<T, any> = (a: any, b: any) => a - b,
leftBound: any = -Infinity,
rightBound: any = Infinity,
) {
this.root = new TreapNode<T>(rightBound);
this.root.priority = Infinity;
this.root.left = new TreapNode<T>(leftBound);
this.root.left.priority = -Infinity;
this.root.pushUp();
this.leftBound = leftBound;
this.rightBound = rightBound;
this.compareFn = compareFn;
}
get size(): number {
return this.root.size - 2;
}
get height(): number {
const getHeight = (node: TreapNode<T> | null): number => {
if (node == null) return 0;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
};
return getHeight(this.root);
}
/**
*
* @complexity `O(logn)`
* @description Returns true if value is a member.
*/
has(value: T): boolean {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): boolean => {
if (node == null) return false;
if (compare(node.value, value) === 0) return true;
if (compare(node.value, value) < 0) return dfs(node.right, value);
return dfs(node.left, value);
};
return dfs(this.root, value);
}
/**
*
* @complexity `O(logn)`
* @description Add value to sorted set.
*/
add(...values: T[]): this {
const compare = this.compareFn;
const dfs = (
node: TreapNode<T> | null,
value: T,
parent: TreapNode<T>,
direction: 'left' | 'right',
): void => {
if (node == null) return;
if (compare(node.value, value) === 0) {
node.count++;
node.pushUp();
} else if (compare(node.value, value) > 0) {
if (node.left) {
dfs(node.left, value, node, 'left');
} else {
node.left = new TreapNode(value);
node.pushUp();
}
if (TreapNode.getFac(node.left) > node.priority) {
parent[direction] = node.rotateRight();
}
} else if (compare(node.value, value) < 0) {
if (node.right) {
dfs(node.right, value, node, 'right');
} else {
node.right = new TreapNode(value);
node.pushUp();
}
if (TreapNode.getFac(node.right) > node.priority) {
parent[direction] = node.rotateLeft();
}
}
parent.pushUp();
};
values.forEach(value => dfs(this.root.left, value, this.root, 'left'));
return this;
}
/**
*
* @complexity `O(logn)`
* @description Remove value from sorted set if it is a member.
* If value is not a member, do nothing.
*/
delete(value: T): void {
const compare = this.compareFn;
const dfs = (
node: TreapNode<T> | null,
value: T,
parent: TreapNode<T>,
direction: 'left' | 'right',
): void => {
if (node == null) return;
if (compare(node.value, value) === 0) {
if (node.count > 1) {
node.count--;
node?.pushUp();
} else if (node.left == null && node.right == null) {
parent[direction] = null;
} else {
// 旋到根节点
if (
node.right == null ||
TreapNode.getFac(node.left) > TreapNode.getFac(node.right)
) {
parent[direction] = node.rotateRight();
dfs(parent[direction]?.right ?? null, value, parent[direction]!, 'right');
} else {
parent[direction] = node.rotateLeft();
dfs(parent[direction]?.left ?? null, value, parent[direction]!, 'left');
}
}
} else if (compare(node.value, value) > 0) {
dfs(node.left, value, node, 'left');
} else if (compare(node.value, value) < 0) {
dfs(node.right, value, node, 'right');
}
parent?.pushUp();
};
dfs(this.root.left, value, this.root, 'left');
}
/**
*
* @complexity `O(logn)`
* @description Returns an index to insert value in the sorted set.
* If the value is already present, the insertion point will be before (to the left of) any existing values.
*/
bisectLeft(value: T): number {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
return TreapNode.getSize(node.left);
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
return dfs(this.root, value) - 1;
}
/**
*
* @complexity `O(logn)`
* @description Returns an index to insert value in the sorted set.
* If the value is already present, the insertion point will be before (to the right of) any existing values.
*/
bisectRight(value: T): number {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
return TreapNode.getSize(node.left) + node.count;
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
return dfs(this.root, value) - 1;
}
/**
*
* @complexity `O(logn)`
* @description Returns the index of the first occurrence of a value in the set, or -1 if it is not present.
*/
indexOf(value: T): number {
const compare = this.compareFn;
let isExist = false;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
isExist = true;
return TreapNode.getSize(node.left);
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
const res = dfs(this.root, value) - 1;
return isExist ? res : -1;
}
/**
*
* @complexity `O(logn)`
* @description Returns the index of the last occurrence of a value in the set, or -1 if it is not present.
*/
lastIndexOf(value: T): number {
const compare = this.compareFn;
let isExist = false;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
isExist = true;
return TreapNode.getSize(node.left) + node.count - 1;
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
const res = dfs(this.root, value) - 1;
return isExist ? res : -1;
}
/**
*
* @complexity `O(logn)`
* @description Returns the item located at the specified index.
* @param index The zero-based index of the desired code unit. A negative index will count back from the last item.
*/
at(index: number): T | undefined {
if (index < 0) index += this.size;
if (index < 0 || index >= this.size) return undefined;
const dfs = (node: TreapNode<T> | null, rank: number): T | undefined => {
if (node == null) return undefined;
if (TreapNode.getSize(node.left) >= rank) {
return dfs(node.left, rank);
} else if (TreapNode.getSize(node.left) + node.count >= rank) {
return node.value;
} else {
return dfs(node.right, rank - TreapNode.getSize(node.left) - node.count);
}
};
const res = dfs(this.root, index + 2);
return ([this.leftBound, this.rightBound] as any[]).includes(res) ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element less than `val`, return `undefined` if no such element found.
*/
lower(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) >= 0) return dfs(node.left, value);
const tmp = dfs(node.right, value);
if (tmp == null || compare(node.value, tmp) > 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.leftBound ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element greater than `val`, return `undefined` if no such element found.
*/
higher(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) <= 0) return dfs(node.right, value);
const tmp = dfs(node.left, value);
if (tmp == null || compare(node.value, tmp) < 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.rightBound ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element less than or equal to `val`, return `undefined` if no such element found.
*/
floor(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) === 0) return node.value;
if (compare(node.value, value) >= 0) return dfs(node.left, value);
const tmp = dfs(node.right, value);
if (tmp == null || compare(node.value, tmp) > 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.leftBound ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element greater than or equal to `val`, return `undefined` if no such element found.
*/
ceil(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) === 0) return node.value;
if (compare(node.value, value) <= 0) return dfs(node.right, value);
const tmp = dfs(node.left, value);
if (tmp == null || compare(node.value, tmp) < 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.rightBound ? undefined : res;
}
/**
* @complexity `O(logn)`
* @description
* Returns the last element from set.
* If the set is empty, undefined is returned.
*/
first(): T | undefined {
const iter = this.inOrder();
iter.next();
const res = iter.next().value;
return res === this.rightBound ? undefined : res;
}
/**
* @complexity `O(logn)`
* @description
* Returns the last element from set.
* If the set is empty, undefined is returned .
*/
last(): T | undefined {
const iter = this.reverseInOrder();
iter.next();
const res = iter.next().value;
return res === this.leftBound ? undefined : res;
}
/**
* @complexity `O(logn)`
* @description
* Removes the first element from an set and returns it.
* If the set is empty, undefined is returned and the set is not modified.
*/
shift(): T | undefined {
const first = this.first();
if (first === undefined) return undefined;
this.delete(first);
return first;
}
/**
* @complexity `O(logn)`
* @description
* Removes the last element from an set and returns it.
* If the set is empty, undefined is returned and the set is not modified.
*/
pop(index?: number): T | undefined {
if (index == null) {
const last = this.last();
if (last === undefined) return undefined;
this.delete(last);
return last;
}
const toDelete = this.at(index);
if (toDelete == null) return;
this.delete(toDelete);
return toDelete;
}
/**
*
* @complexity `O(logn)`
* @description
* Returns number of occurrences of value in the sorted set.
*/
count(value: T): number {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) return node.count;
if (compare(node.value, value) < 0) return dfs(node.right, value);
return dfs(node.left, value);
};
return dfs(this.root, value);
}
*[Symbol.iterator](): Generator<T, any, any> {
yield* this.values();
}
/**
* @description
* Returns an iterable of keys in the set.
*/
*keys(): Generator<T, any, any> {
yield* this.values();
}
/**
* @description
* Returns an iterable of values in the set.
*/
*values(): Generator<T, any, any> {
const iter = this.inOrder();
iter.next();
const steps = this.size;
for (let _ = 0; _ < steps; _++) {
yield iter.next().value;
}
}
/**
* @description
* Returns a generator for reversed order traversing the set.
*/
*rvalues(): Generator<T, any, any> {
const iter = this.reverseInOrder();
iter.next();
const steps = this.size;
for (let _ = 0; _ < steps; _++) {
yield iter.next().value;
}
}
/**
* @description
* Returns an iterable of key, value pairs for every entry in the set.
*/
*entries(): IterableIterator<[number, T]> {
const iter = this.inOrder();
iter.next();
const steps = this.size;
for (let i = 0; i < steps; i++) {
yield [i, iter.next().value];
}
}
private *inOrder(root: TreapNode<T> | null = this.root): Generator<T, any, any> {
if (root == null) return;
yield* this.inOrder(root.left);
const count = root.count;
for (let _ = 0; _ < count; _++) {
yield root.value;
}
yield* this.inOrder(root.right);
}
private *reverseInOrder(root: TreapNode<T> | null = this.root): Generator<T, any, any> {
if (root == null) return;
yield* this.reverseInOrder(root.right);
const count = root.count;
for (let _ = 0; _ < count; _++) {
yield root.value;
}
yield* this.reverseInOrder(root.left);
}
}func minimumCost(nums []int, k int, dist int) int64 {
k--
l := redblacktree.New[int, int]()
r := redblacktree.New[int, int]()
merge := func(st *redblacktree.Tree[int, int], x, v int) {
c, _ := st.Get(x)
if c+v == 0 {
st.Remove(x)
} else {
st.Put(x, c+v)
}
}
s := nums[0]
for _, x := range nums[1 : dist+2] {
s += x
merge(l, x, 1)
}
size := dist + 1
l2r := func() {
x := l.Right().Key
merge(l, x, -1)
s -= x
size--
merge(r, x, 1)
}
r2l := func() {
x := r.Left().Key
merge(r, x, -1)
merge(l, x, 1)
s += x
size++
}
for size > k {
l2r()
}
ans := s
for i := dist + 2; i < len(nums); i++ {
x := nums[i-dist-1]
if _, ok := l.Get(x); ok {
merge(l, x, -1)
s -= x
size--
} else {
merge(r, x, -1)
}
y := nums[i]
if y < l.Right().Key {
merge(l, y, 1)
s += y
size++
} else {
merge(r, y, 1)
}
for size < k {
r2l()
}
for size > k {
l2r()
}
ans = min(ans, s)
}
return int64(ans)
}use std::collections::BTreeMap;
impl Solution {
pub fn minimum_cost(nums: Vec<i32>, k: i32, dist: i32) -> i64 {
let n = nums.len();
let k = (k - 1) as usize;
let dist = dist as usize;
let mut l: BTreeMap<i32, i32> = BTreeMap::new();
let mut r: BTreeMap<i32, i32> = BTreeMap::new();
let mut s: i64 = nums[0] as i64;
let mut size: usize = 0;
for i in 1..=dist + 1 {
s += nums[i] as i64;
*l.entry(nums[i]).or_insert(0) += 1;
}
size = dist + 1;
while size > k {
l2r(&mut l, &mut r, &mut s, &mut size);
}
let mut ans = s;
for i in dist + 2..n {
let x = nums[i - dist - 1];
if let Some(v) = l.get_mut(&x) {
*v -= 1;
if *v == 0 {
l.remove(&x);
}
s -= x as i64;
size -= 1;
} else {
let v = r.get_mut(&x).unwrap();
*v -= 1;
if *v == 0 {
r.remove(&x);
}
}
let y = nums[i];
let l_max = *l.iter().next_back().unwrap().0;
if y < l_max {
*l.entry(y).or_insert(0) += 1;
size += 1;
s += y as i64;
} else {
*r.entry(y).or_insert(0) += 1;
}
while size < k {
r2l(&mut l, &mut r, &mut s, &mut size);
}
while size > k {
l2r(&mut l, &mut r, &mut s, &mut size);
}
ans = ans.min(s);
}
ans
}
}
fn l2r(
l: &mut BTreeMap<i32, i32>,
r: &mut BTreeMap<i32, i32>,
s: &mut i64,
size: &mut usize,
) {
let x = *l.iter().next_back().unwrap().0;
*s -= x as i64;
if let Some(v) = l.get_mut(&x) {
*v -= 1;
if *v == 0 {
l.remove(&x);
}
}
*size -= 1;
*r.entry(x).or_insert(0) += 1;
}
fn r2l(
l: &mut BTreeMap<i32, i32>,
r: &mut BTreeMap<i32, i32>,
s: &mut i64,
size: &mut usize,
) {
let x = *r.iter().next().unwrap().0;
if let Some(v) = r.get_mut(&x) {
*v -= 1;
if *v == 0 {
r.remove(&x);
}
}
*l.entry(x).or_insert(0) += 1;
*s += x as i64;
*size += 1;
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
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.