Split Array - Largest Sum

# Question

Given an integer array $a$ of size $n$ and an integer $k$. We need to split the array into $k$ non-empty contiguous subarrays. The goal is to minimize the largest sum among these $k$ subarrays.

Return the value $x$, where $x$ is the minimum possible "maximum subarray sum."

# Solution

# Pattern

Binary Search on Answer Space When the problem asks to "Minimize the Maximum" or "Maximize the Minimum" of a value, and the possibility of achieving that value is monotonic (if $x$ works, $x+1$ also works), we binary search the answer directly.

# How to Identify

• Optimization Goal: Keywords like "minimized largest" or "maximized smallest."
• Contiguous Constraints: The splits must be in order (subarrays, not subsets).
• Feasibility Check: It is easy ($O(n)$) to check if a specific "max sum" can be achieved using $k$ or fewer splits.

# Description

Step-by-step explanation:

• Define the Search Space:
  • The minimum possible "largest sum" is the value of the largest element in the array ($low = \max(a)$).
  • The maximum possible "largest sum" is the sum of all elements ($high = \sum a$).
• The Binary Search:
  • Pick a middle value mid from the range $[low, high]$.
  • Treat mid as the maximum capacity allowed for any subarray.
• Greedy Validation (The Predicate):
  • Iterate through the array and accumulate a current sum.
  • If adding the next element exceeds mid, start a new subarray (increment count) and reset the current sum to that element.
• Decision Choice:
  • If the number of subarrays required is $\le k$, then mid is a potential answer. Try smaller values ($high = mid - 1$).
  • If we need more than $k$ subarrays, mid is too small. Try larger values ($low = mid + 1$).

# The Intuition

Imagine you have a series of boxes and you want to pack them into $k$ trucks. You want to make sure the heaviest truck is as light as possible.

• If you set a weight limit too low, you will need more than $k$ trucks.
• If you set it very high, you only need 1 truck, but it will be very heavy. We use Binary Search to find the "sweet spot"—the lowest weight limit that still allows us to use exactly $k$ (or fewer) trucks.

# Complexity

# Time Complexity

The search space is the sum of the array. Binary search takes $\log(Sum)$ steps. In each step, we traverse the array once ($O(n)$). Total time: $O(n \cdot \log(Sum))$.

# Space Complexity

Only a constant amount of extra space is used for pointers and sum variables. No recursion stack is involved.

# Code

class Solution {
    public int largestSubarraySumMinimized(int[] a, int k) {
        // Range: [max element, total sum]
        long low = 0;
        long high = 0;
        for (int num : a) {
            low = Math.max(low, num);
            high += num;
        }
 
        long ans = high;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            
            if (getRequiredSubarrays(a, mid) <= k) {
                ans = mid;
                high = mid - 1; // Try to minimize the maximum further
            } else {
                low = mid + 1; // Limit too small, need more capacity
            }
        }
        return (int) ans;
    }
 
    private int getRequiredSubarrays(int[] a, long limit) {
        int count = 1; // Start with the first subarray
        long currentSum = 0;
 
        for (int num : a) {
            if (currentSum + num > limit) {
                // Cannot fit in current subarray, start a new one
                count++;
                currentSum = num;
            } else {
                currentSum += num;
            }
        }
        return count;
    }
}

# Caveats

• Integer Overflow: The sum of elements can easily exceed $2^{31}-1$. Always use long for low, high, and mid.
• k > n: If $k$ is greater than the number of elements, it's impossible to split into $k$ non-empty subarrays. Your code should handle this (usually returns -1 or based on problem specs).
• Non-positive values: If the array has negative numbers, the greedy check fails because the sum is no longer monotonic.

# Concepts to Think About

• Binary Search on Answer: This is a meta-pattern. You aren't searching the input; you're searching the solution space.
• Greedy + BS: Notice how the problem combines two paradigms.
• Related Problems: - Capacity to Ship Packages Within D Days
  • Koko Eating Bananas
  • Book Allocation Problem
  • Painter's Partition Problem

# Logical Follow-up

Question: What if the order of elements can be changed? (Subsets instead of Subarrays) Solution: The problem becomes NP-Hard (equivalent to the Bin Packing problem or Partition problem). You would need to use Backtracking or Dynamic Programming with Bitmasking, which only works for very small $n$ (usually n < 20).

Question: How would you modify this to find the split points? Solution: Once you find the optimal mid, run the getRequiredSubarrays logic one last time and record the indices where currentSum + num > limit occurs.