Split Array into K Subarrays - Minimize Largest Sum - Visualization

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an array of non-negative integers and an integer K, split the array into K contiguous subarrays such that the maximum sum among these subarrays is minimized.

  • You must split the array into exactly K parts.
  • Each part must be a contiguous segment of the array.
  • Every element must be used and order must be maintained.

The goal is to make the largest sum among the K subarrays as small as possible.

If the array is empty or K is zero, return 0 as the answer.

Examples❯

Input Array K Output Description
[7, 2, 5, 10, 8] 2 18 Split as [7,2,5] and [10,8]. Max sum = 14 and 18 → answer is 18
[1, 2, 3, 4, 5] 2 9 Best split is [1,2,3] and [4,5] with max sums 6 and 9
[1, 4, 4] 3 4 Split each element as one subarray → max sum is 4
[5] 1 5 Only one element, one group → max sum = 5
[1, 2, 3] 1 6 All elements in one group → total sum = 6
[1, 2, 3] 3 3 Each element in its own group → largest is 3
[] 3 0 Empty array → no subarrays can be formed
[1, 2, 3] 0 0 Zero partitions not allowed → return 0
[10, 20, 30] 5 30 More partitions than elements → some will be empty, max element becomes answer

Solution❯

Understanding the Problem

We are given an array of integers and a number K. Our task is to split the array into K contiguous subarrays such that the largest sum among these subarrays is as small as possible.

Think of the array as a set of tasks and each subarray as a group of tasks assigned to one worker. We want to divide the work among K workers so that the worker with the heaviest load has to do as little as possible. Our goal is to minimize the maximum load any single worker gets.

Step-by-Step Solution with Example

Step 1: Understand the range of possible answers

The smallest possible value for the largest subarray sum is the largest single element in the array. The largest possible value is the sum of the entire array (if we don’t split at all).

So, if the array is [7, 2, 5, 10, 8] and K = 2:

  • Minimum possible sum = max(7, 2, 5, 10, 8) = 10
  • Maximum possible sum = 7 + 2 + 5 + 10 + 8 = 32

Step 2: Use Binary Search on the answer space

We’ll perform binary search between 10 and 32 to find the smallest "maximum subarray sum" such that we can split the array into ≤ K subarrays.

Step 3: Check if a candidate value is valid

For each mid value, we check: “Can we split the array into K or fewer parts, where each part has a sum ≤ mid?”

We simulate this by traversing the array and forming a new subarray whenever the running sum exceeds mid. We count how many subarrays we end up forming.

Step 4: Adjust binary search range

If we can split the array into ≤ K parts, we try to do even better by lowering the max sum (move left in binary search). If we need more than K parts, our guess is too small, so we increase it (move right).

Step 5: Final Result

The lowest value for which we can split the array into K parts is our answer. For the example [7, 2, 5, 10, 8] with K = 2, the result will be 18.

We can split the array like this: [7, 2, 5] and [10, 8]. The largest subarray sum is 18, which is the smallest possible in this case.

Edge Cases

  • Empty Array: Return 0 since there’s nothing to split.
  • K = 0: Cannot create 0 partitions, return 0 or error depending on specification.
  • K ≥ Length of Array: Best case is to assign one element per subarray, so the answer is the largest element in the array.
  • K = 1: The entire array is one subarray, so the answer is the sum of all elements.
  • Array with very large numbers: The logic still holds, binary search helps us manage large values efficiently.

Finally

This problem is a classic example of using binary search on the answer space. Instead of checking every possible way to split the array, we guess a maximum sum and test if it's valid. This technique dramatically improves efficiency from brute force to O(n log(sum)).

By understanding the problem clearly, working through an example, and carefully handling edge cases, we can arrive at a solution that is both correct and optimized.

Algorithm Steps❯

  1. Set low = max(arr) and high = sum(arr).
  2. While low ≤ high:
  3. → Compute mid = (low + high) / 2.
  4. → Check if it’s possible to split the array into ≤ K subarrays where no subarray has sum > mid.
  5. → If possible, update answer = mid and try a smaller value by high = mid - 1.
  6. → Else, try a larger value by low = mid + 1.
  7. Return the minimum value stored in answer.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
TS
#include <stdio.h>

int canSplit(int nums[], int n, int k, int maxSum) {
    int currentSum = 0, splits = 1;
    for (int i = 0; i < n; i++) {
        if (currentSum + nums[i] > maxSum) {
            splits++;
            currentSum = nums[i];
            if (splits > k) return 0;
        } else {
            currentSum += nums[i];
        }
    }
    return 1;
}

int splitArray(int nums[], int n, int k) {
    int low = nums[0], high = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] > low) low = nums[i];
        high += nums[i];
    }

    int result = high;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canSplit(nums, n, k, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    int arr[] = {7, 2, 5, 10, 8};
    int k = 2;
    printf("Minimum largest sum: %d\n", splitArray(arr, 5, k));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n log(sum - max))We perform binary search over the range from max element to sum of all elements, and in each step, we scan the array once.
Average CaseO(n log(sum - max))For each binary search iteration, we check if the array can be split into K subarrays using a greedy scan.
Worst CaseO(n log(sum - max))Even in the worst case, binary search narrows down the search space logarithmically, with O(n) work per step.

Space Complexity❯

O(1)

Explanation: No extra space is used except a few variables for tracking sums and counters.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...