🛂 Beginner-Friendly Guide 'Divide an Array Into Subarrays With Minimum Cost II' - Problem 3013 (C++, Python, JavaScript)

Source: Dev.to

Problem Overview

Dividing data into optimal segments is a classic challenge in computer science, often requiring a balance between specific constraints and efficiency.
This problem asks us to find the cheapest way to split an array while ensuring our split points stay within a certain distance of each other. It is a fantastic exercise in combining sliding‑window techniques with advanced data structures to maintain a sorted view of moving data.

You are given

• An array of integers nums.
• An integer k, representing the number of sub‑arrays you must create.
• An integer dist, which limits how far apart the starting indices of the second and last sub‑arrays can be.

Goal

Minimize the total cost, where the cost of a sub‑array is its first element.
Since the first sub‑array always starts at index 0, nums[0] is always part of the cost.
We need to pick k‑1 additional starting indices from the rest of the array that minimize the sum and satisfy the dist constraint.

Formalisation

Let the starting indices of the k sub‑arrays be

[ p_1, p_2, \dots, p_k ]

• p_1 is always 0.
• We must choose k‑1 indices from the range 1 … n‑1.
• The constraint

[ p_k - p_2 \le \text{dist} ]

means all chosen indices (from the second to the k‑th) must fit within a window of size dist.

As we slide this window of size dist across the array, we need to quickly find the sum of the k‑1 smallest elements within that window.
To do this efficiently we use a Binary Indexed Tree (Fenwick Tree) together with coordinate compression. This allows us to “rank” the numbers and use binary lifting to find the smallest values in logarithmic time.

Example

nums = [1,3,2,6,4,2], k = 3, dist = 3

We must pick k‑1 = 2 indices from the window.

• The window size is dist + 1 = 4.

• If the first chosen index is 1, the last index can be at most 1 + dist = 4.

  Looking at indices 1 … 4: [3, 2, 6, 4].
  The two smallest are 2 and 3.
  Cost = nums[0] + 2 + 3 = 1 + 5 = 6.

• If the first chosen index is 2, the last index can be up to 5.

  Looking at indices 2 … 5: [2, 6, 4, 2].
  The two smallest are 2 and 2.
  Cost = 1 + 2 + 2 = 5.

The minimum possible cost is 5.

Reference Implementations

C++ (GNU C++17)

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int max_rank;
    vector<int> bit_count;
    vector<long long> bit_sum;
    vector<int> sorted_values;

    // Add / remove a value from the BIT
    void update(int idx, int count_delta, long long val_delta) {
        for (; idx <= max_rank; idx += idx & -idx) {
            bit_count[idx] += count_delta;
            bit_sum[idx]   += val_delta;
        }
    }

    // Query sum of smallest `target` elements
    long long query(int target) {
        int idx = 0;
        int cur_k = 0;
        long long cur_s = 0;
        for (int i = 1 << (31 - __builtin_clz(max_rank)); i; i >>= 1) {
            int next_idx = idx + i;
            if (next_idx <= max_rank && cur_k + bit_count[next_idx] < target) {
                idx   = next_idx;
                cur_k += bit_count[next_idx];
                cur_s += bit_sum[next_idx];
            }
        }
        // add the remaining part of the (target‑cur_k)‑th element
        return cur_s + 1LL * (target - cur_k) * sorted_values[idx];
    }

public:
    int minCost(vector<int>& nums, int k, int dist) {
        int n = nums.size();

        // coordinate compression
        sorted_values = nums;
        sort(sorted_values.begin(), sorted_values.end());
        sorted_values.erase(unique(sorted_values.begin(), sorted_values.end()), sorted_values.end());
        max_rank = sorted_values.size();

        bit_count.assign(max_rank + 1, 0);
        bit_sum.assign(max_rank + 1, 0);

        auto get_rank = [&](int val) {
            return lower_bound(sorted_values.begin(), sorted_values.end(), val) - sorted_values.begin() + 1;
        };

        int target_k = k - 1;                     // we need k‑1 additional starts

        // initialise the window (first `dist + 1` elements, but not beyond the array)
        for (int i = 1; i <= min(dist, n - 1); ++i) {
            update(get_rank(nums[i]), 1, nums[i]);
        }

        long long min_cost = nums[0] + query(target_k);

        // slide the window across the array
        for (int i = 2; i + dist < n; ++i) {
            // remove element leaving the window
            update(get_rank(nums[i - 1]), -1, -nums[i - 1]);
            // add new element entering the window
            update(get_rank(nums[i + dist]), 1, nums[i + dist]);

            long long cur = nums[0] + query(target_k);
            min_cost = min(min_cost, cur);
        }
        return (int)min_cost;
    }
};

Python

def minCost(nums, k, dist):
    n = len(nums)

    # ---- coordinate compression ----
    sorted_unique = sorted(set(nums))
    ranks = {val: i + 1 for i, val in enumerate(sorted_unique)}
    max_rank = len(sorted_unique)

    bit_count = [0] * (max_rank + 1)   # how many numbers of each rank
    bit_sum   = [0] * (max_rank + 1)   # sum of those numbers

    def update(rank: int, c_delta: int, v_delta: int) -> None:
        while rank <= max_rank:
            bit_count[rank] += c_delta
            bit_sum[rank]   += v_delta
            rank += rank & -rank

    def query(target: int) -> int:
        idx = 0
        cur_k = 0
        cur_s = 0
        i = max_rank.bit_length()
        while i >= 0:
            next_idx = idx + (1 << i)
            if next_idx <= max_rank and cur_k + bit_count[next_idx] < target:
                idx   = next_idx
                cur_k += bit_count[next_idx]
                cur_s += bit_sum[next_idx]
            i -= 1
        return cur_s + (target - cur_k) * sorted_unique[idx]

    target_k = k - 1

    # initialise the window (first `dist + 1` elements, but not beyond the array)
    for i in range(1, min(dist + 1, n)):
        update(ranks[nums[i]], 1, nums[i])

    min_cost = nums[0] + query(target_k)

    # slide the window across the array
    for i in range(2, n - target_k + 1):
        # remove the element that leaves the window
        update(ranks[nums[i - 1]], -1, -nums[i - 1])

        # add the new element that enters the window (if any)
        if i + dist < n:
            update(ranks[nums[i + dist]], 1, nums[i + dist])

        cur = nums[0] + query(target_k)
        min_cost = min(min_cost, cur)

    return min_cost

JavaScript (Node.js)

function minCost(nums, k, dist) {
    const n = nums.length;

    // ---- coordinate compression ----
    const sortedUnique = Array.from(new Set(nums)).sort((a, b) => a - b);
    const ranks = new Map();
    sortedUnique.forEach((val, i) => ranks.set(val, i + 1));
    const maxRank = sortedUnique.length;

    const bitCount = new Array(maxRank + 1).fill(0);
    const bitSum   = new Array(maxRank + 1).fill(0n); // use BigInt for safety

    const update = (rank, cDelta, vDelta) => {
        while (rank <= maxRank) {
            bitCount[rank] += cDelta;
            bitSum[rank]   += BigInt(vDelta);
            rank += rank & -rank;
        }
    };

    const query = (target) => {
        let idx = 0, curK = 0, curS = 0n;
        for (let i = Math.floor(Math.log2(maxRank)); i >= 0; i--) {
            const nextIdx = idx + (1 << i);
            if (nextIdx <= maxRank && curK + bitCount[nextIdx] < target) {
                idx   = nextIdx;
                curK += bitCount[nextIdx];
                curS += bitSum[nextIdx];
            }
        }
        const remaining = target - curK;
        return curS + BigInt(remaining) * BigInt(sortedUnique[idx]);
    };

    const targetK = k - 1;

    // initialise the window (first `dist + 1` elements, but not beyond the array)
    for (let i = 1; i <= Math.min(dist, n - 1); i++) {
        update(ranks.get(nums[i]), 1, nums[i]);
    }

    let minCost = BigInt(nums[0]) + query(targetK);

    // slide the window across the array
    for (let i = 2; i + dist < n; i++) {
        // remove element leaving the window
        update(ranks.get(nums[i - 1]), -1, -nums[i - 1]);
        // add new element entering the window
        update(ranks.get(nums[i + dist]), 1, nums[i + dist]);

        const cur = BigInt(nums[0]) + query(targetK);
        if (cur < minCost) minCost = cur;
    }

    return Number(minCost);
}

Key Techniques

Coordinate Compression

When the value range (up to 10^9 or larger) far exceeds the number of elements n, we map each distinct value to a compact rank. This lets us use the ranks as indices in arrays (e.g., Fenwick trees).

Dual Fenwick Tree

One BIT stores counts of elements, the other stores sums of their values. Together they enable fast “sum of the smallest K elements” queries.

Binary Lifting on BIT

Instead of a linear scan or a binary search over the BIT, we use binary lifting to locate the prefix where the cumulative count first reaches (or exceeds) K. This reduces the search to O(log maxRank).

Why This Matters

The problem is a classic example of handling streaming data with tight time constraints:

• In real‑world systems (e.g., high‑frequency trading platforms), you often need the “best K prices in the last T minutes.”

• A sliding window combined with an order‑statistic data structure (the dual BIT) provides the necessary efficiency.

• Although the problem appears daunting as a “Hard” challenge, breaking it down into:

  1. Window management, and
  2. Efficient rank‑based queries

  makes the solution both understandable and implementable.