Crack the Backend

Problem Statement

Given an integer array nums and an integer k, split nums into k non-empty contiguous subarrays. Minimize the largest sum among these k subarrays. Return that minimum possible largest sum.

We must preserve order: each subarray is a contiguous block. The "largest sum" is the maximum of the k subarray sums. We want to choose k-1 split points so that this maximum is as small as possible.
Binary search on the answer: the answer is in [max(nums), sum(nums)]. For a candidate maxSum, check if we can split into at most k subarrays such that each has sum <= maxSum (greedy: fill each subarray until adding the next element would exceed maxSum, then start a new one).

Key Observations

possible(maxSum): Greedily form subarrays: start a new subarray when adding the next element would make the current sum exceed maxSum. Count the number of subarrays. If count <= k, we can achieve that maxSum (we might use fewer than k subarrays). So if possible(mid), try smaller (high = mid); else low = mid + 1. Return low.
Lower bound is max(nums) (one element per subarray); upper bound is sum(nums) (one subarray).

Approach

High-level: Binary search maxSum in [max(nums), sum(nums)]. For each mid, greedy: count how many subarrays we need so that each has sum <= mid. If count <= k, high = mid; else low = mid + 1. Return low.

Steps:

low = max(nums), high = sum(nums). While low < high: mid = low + (high - low) / 2. count = 1, cur = 0; for each x in nums: if cur + x > mid then count++, cur = 0; cur += x. If count <= k, high = mid; else low = mid + 1.
Return low.

Implementation

Java

public int splitArray(int[] nums, int k) {
    long low = 0, high = 0;

    for (int x : nums) { low = Math.max(low, x); high += x; }
    while (low < high) {
        long mid = low + (high - low) / 2;
        int parts = 1;
        long cur = 0;

        for (int x : nums) {
            if (cur + x > mid) { parts++; cur = 0; }
            cur += x;
        }

        if (parts <= k) {
            high = mid;
        }
        else {
            low = mid + 1;
        }
    }

    return (int) low;
}

Test Cases

Example 1

Input

nums = [7,2,5,10,8], k = 2

Expected

18

Explanation

Best split [7,2,5] and [10,8].

Complexity Analysis

Time: O(n log(sum)).
Space: O(1).

Follow-ups

Same as capacity to ship: minimize maximum.