Split Array into K Subarrays - Minimize Largest Sum

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.

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.

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.

#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;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canSplit(const vector<int>& nums, int k, int maxSum) {
    int currentSum = 0, splits = 1;
    for (int num : nums) {
        if (currentSum + num > maxSum) {
            splits++;
            currentSum = num;
            if (splits > k) return false;
        } else {
            currentSum += num;
        }
    }
    return true;
}

int splitArray(vector<int>& nums, int k) {
    int low = *max_element(nums.begin(), nums.end());
    int high = 0;
    for (int num : nums) high += num;

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

int main() {
    vector<int> arr = {7, 2, 5, 10, 8};
    int k = 2;
    cout << "Minimum largest sum: " << splitArray(arr, k) << endl;
    return 0;
}

def can_split(nums, k, max_sum):
    current_sum = 0
    splits = 1
    for num in nums:
        if current_sum + num > max_sum:
            splits += 1
            current_sum = num
            if splits > k:
                return False
        else:
            current_sum += num
    return True

def split_array(nums, k):
    low = max(nums)
    high = sum(nums)
    result = high

    while low <= high:
        mid = (low + high) // 2
        if can_split(nums, k, mid):
            result = mid
            high = mid - 1
        else:
            low = mid + 1
    return result

arr = [7, 2, 5, 10, 8]
k = 2
print("Minimum largest sum:", split_array(arr, k))

public class SplitArrayLargestSum {
  public static int splitArray(int[] nums, int k) {
    int low = Integer.MIN_VALUE;
    int high = 0;
    for (int num : nums) {
      low = Math.max(low, num);
      high += num;
    }
    int result = high;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (canSplit(nums, k, mid)) {
        result = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return result;
  }

  private static boolean canSplit(int[] nums, int k, int maxSum) {
    int currentSum = 0, splits = 1;
    for (int num : nums) {
      if (currentSum + num > maxSum) {
        splits++;
        currentSum = num;
        if (splits > k) return false;
      } else {
        currentSum += num;
      }
    }
    return true;
  }

  public static void main(String[] args) {
    int[] arr = {7, 2, 5, 10, 8};
    int k = 2;
    System.out.println("Minimum largest sum: " + splitArray(arr, k));
  }
}

function canSplit(nums, k, maxSum) {
  let currentSum = 0;
  let splits = 1;
  for (const num of nums) {
    if (currentSum + num > maxSum) {
      splits++;
      currentSum = num;
      if (splits > k) return false;
    } else {
      currentSum += num;
    }
  }
  return true;
}

function splitArray(nums, k) {
  let low = Math.max(...nums);
  let high = nums.reduce((a, b) => a + b);
  let result = high;

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

const arr = [7, 2, 5, 10, 8];
const k = 2;
console.log("Minimum largest sum:", splitArray(arr, k));

package main

import (
	"fmt"
)

func canSplit(nums []int, k int, maxSum int) bool {
	currentSum := 0
	splits := 1
	for _, num := range nums {
		if currentSum+num > maxSum {
			splits++
			currentSum = num
			if splits > k {
				return false
			}
		} else {
			currentSum += num
		}
	}
	return true
}

func splitArray(nums []int, k int) int {
	low, high := nums[0], 0
	for _, num := range nums {
		if num > low {
			low = num
		}
		high += num
	}
	result := high
	for low <= high {
		mid := low + (high-low)/2
		if canSplit(nums, k, mid) {
			result = mid
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return result
}

func main() {
	nums := []int{7, 2, 5, 10, 8}
	k := 2
	fmt.Println("Minimum largest sum:", splitArray(nums, k))
}

fn can_split(nums: &Vec<i32>, k: i32, max_sum: i32) -> bool {
    let mut current_sum = 0;
    let mut splits = 1;
    for &num in nums {
        if current_sum + num > max_sum {
            splits += 1;
            current_sum = num;
            if splits > k {
                return false;
            }
        } else {
            current_sum += num;
        }
    }
    true
}

fn split_array(nums: Vec<i32>, k: i32) -> i32 {
    let mut low = *nums.iter().max().unwrap();
    let mut high: i32 = nums.iter().sum();
    let mut result = high;
    while low <= high {
        let mid = low + (high - low) / 2;
        if can_split(&nums, k, mid) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    result
}

fn main() {
    let arr = vec![7, 2, 5, 10, 8];
    let k = 2;
    println!("Minimum largest sum: {}", split_array(arr, k));
}

fun canSplit(nums: IntArray, k: Int, maxSum: Int): Boolean {
    var currentSum = 0
    var splits = 1
    for (num in nums) {
        if (currentSum + num > maxSum) {
            splits++
            currentSum = num
            if (splits > k) return false
        } else {
            currentSum += num
        }
    }
    return true
}

fun splitArray(nums: IntArray, k: Int): Int {
    var low = nums.maxOrNull() ?: 0
    var high = nums.sum()
    var result = high
    while (low <= high) {
        val mid = (low + high) / 2
        if (canSplit(nums, k, mid)) {
            result = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return result
}

fun main() {
    val arr = intArrayOf(7, 2, 5, 10, 8)
    val k = 2
    println("Minimum largest sum: ${splitArray(arr, k)}")
}

function canSplit(nums: number[], k: number, maxSum: number): boolean {
  let currentSum = 0;
  let splits = 1;
  for (const num of nums) {
    if (currentSum + num > maxSum) {
      splits++;
      currentSum = num;
      if (splits > k) return false;
    } else {
      currentSum += num;
    }
  }
  return true;
}

function splitArray(nums: number[], k: number): number {
  let low = Math.max(...nums);
  let high = nums.reduce((a, b) => a + b);
  let result = high;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (canSplit(nums, k, mid)) {
      result = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return result;
}

const arr = [7, 2, 5, 10, 8];
const k = 2;
console.log("Minimum largest sum:", splitArray(arr, k));

Time complexity

Space complexity

O(1)

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