Scale Engineer

Divide an Array Into Subarrays With Minimum Cost II

Hard
#2681Time: O((n - dist) * dist * log(dist)). The outer loop runs about `n - dist` times. Inside the loop, we create a list of size `dist + 1` and sort it, which takes `O(dist * log(dist))` time. This is too slow for `n` and `dist` up to 10<sup>5</sup>.Space: O(dist) to store the numbers in the current window for sorting.2 companies
Patterns
Sliding Window
Data structures
ArrayHash TableHeap (Priority Queue)
Companies
American Expressjio

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

The core of the problem is to select k-1 starting indices for the second to k-th subarrays from nums[1:]. The constraint i_{k-1} - i_1 <= dist implies that all these k-1 chosen indices must lie within a contiguous block of dist + 1 indices. To minimize the cost, we need to find a block (or window) of dist + 1 indices in [1, n-1] such that the sum of the k-1 smallest nums values within that block is minimized. This brute-force approach iterates through every possible window of size dist + 1, and for each window, it explicitly finds the k-1 smallest elements by sorting, calculating their sum, and tracking the minimum sum found across all windows.

Algorithm

  • The cost of the first subarray is always nums[0], so we add it at the end. We need to find the minimum sum of costs for the other k-1 subarrays.
  • Let m = k - 1. We need to choose m indices from nums[1:].
  • The chosen indices must lie in a window of size dist + 1.
  • Iterate through all possible start indices i for a window of size dist + 1. The window of indices is [i, i + dist]. i ranges from 1 to n - 1 - dist.
  • For each window:
    • Collect all nums[j] for j from i to i + dist into a list.
    • Sort the list.
    • Calculate the sum of the first m elements.
    • Update a global minimum sum with this sum if it's smaller.
  • Return nums[0] plus the global minimum sum.

Walkthrough

The algorithm iterates through all possible starting positions for a window of size dist + 1. The windows slide over the part of the array from which we can choose our k-1 start indices, which is nums[1] to nums[n-1].

Let m = k - 1. For each window, we do the following:

  1. Extract the numbers within the current window into a temporary list.
  2. Sort this list in non-decreasing order.
  3. Sum the first m elements of the sorted list. This gives the minimum cost for the k-1 subarrays if their start indices are chosen from this window.
  4. We keep track of the minimum sum found among all windows.

Finally, the total minimum cost is nums[0] (the cost of the first subarray, which is fixed) plus the minimum sum we found.

import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public long minimumCost(int[] nums, int k, int dist) {        int n = nums.length;        long minOtherCosts = Long.MAX_VALUE;        int m = k - 1;         // The window of candidate indices for the other k-1 subarrays        // slides from [1, 1+dist] to [n-1-dist, n-1].        // The starting index of the window 'i' can go from 1 to n-1-dist.        for (int i = 1; i <= n - 1 - dist; i++) {            List<Integer> windowNums = new ArrayList<>();            for (int j = i; j <= i + dist; j++) {                windowNums.add(nums[j]);            }                        Collections.sort(windowNums);                        long currentSum = 0;            for (int l = 0; l < m; l++) {                currentSum += windowNums.get(l);            }                        minOtherCosts = Math.min(minOtherCosts, currentSum);        }                return (long)nums[0] + minOtherCosts;    }}

Complexity

Time

O((n - dist) * dist * log(dist)). The outer loop runs about `n - dist` times. Inside the loop, we create a list of size `dist + 1` and sort it, which takes `O(dist * log(dist))` time. This is too slow for `n` and `dist` up to 10<sup>5</sup>.

Space

O(dist) to store the numbers in the current window for sorting.

Trade-offs

Pros

  • Conceptually simple and easy to implement.

  • Correctly models the problem by checking all valid possibilities.

Cons

  • Highly inefficient due to repeated work.

  • Sorting within each sliding window step leads to a high time complexity, making it too slow for the given constraints.

Solutions

class Solution {public  long minimumCost(int[] nums, int k, int dist) {    long result = Long.MAX_VALUE, sum = 0L;    int n = nums.length;    TreeSet<Integer> set1 =        new TreeSet<>((a, b)->nums[a] == nums[b] ? a - b : nums[a] - nums[b]);    TreeSet<Integer> set2 =        new TreeSet<>((a, b)->nums[a] == nums[b] ? a - b : nums[a] - nums[b]);    for (int i = 1; i < n; i++) {      set1.add(i);      sum += nums[i];      if (set1.size() >= k) {        int x = set1.pollLast();        sum -= nums[x];        set2.add(x);      }      if (i - dist > 0) {        result = Math.min(result, sum);        int temp = i - dist;        if (set1.contains(temp)) {          set1.remove(temp);          sum -= nums[temp];          if (set2.size() > 0) {            int y = set2.pollFirst();            sum += nums[y];            set1.add(y);          }        } else {          set2.remove(i - dist);        }      }    }    return result + nums[0];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem