Split Array Largest Sum

XXX. Split Array Largest Sum

Binary Search

Greedy

Problem Statement:

Given an array nums and an integer k, split the array into k non-empty contiguous subarrays such that the largest sum among these subarrays is minimized.

Return the minimized largest sum.

Algorithm:

This problem can be solved using a combination of binary search and a greedy approach to validate possible solutions.

1. Define the Search Space:
   • The smallest possible largest sum is the maximum single element in the array (l).
   • The largest possible largest sum is the sum of all elements in the array (r).
2. Binary Search:

   Perform binary search within the range [l, r] to find the smallest possible largest sum that satisfies the condition of splitting the array into k subarrays.

   • Calculate the midpoint mid of the current range.
   • Use a helper function to determine if it is possible to split the array into k subarrays such that no subarray sum exceeds mid.
   • If valid, update the result and narrow the search range to smaller values (r = mid - 1).
   • If not valid, increase the range (l = mid + 1).
3. Greedy Validation:

   The helper function iterates through the array, maintaining a running total for the current subarray. If adding a new element exceeds mid, it starts a new subarray and increments the count. If the count exceeds k, the solution is invalid.

Complexity:

Time Complexity: O(n log(sum - max)), where n is the length of the array, sum is the total sum of the array, and max is the maximum element in the array.
Space Complexity: O(1), as no additional data structures are used.

Java Implementation:

class Solution {
    public int splitArray(int[] nums, int k) {
        long r = 0; // Upper bound for binary search: the sum of all elements
        long l = 0; // Lower bound: the maximum element in the array
        long result = 0; // To store the smallest valid maximum sum

        // Calculate initial bounds
        for (int num : nums) {
            r += num; // The maximum possible sum is the sum of all elements
            l = Math.max(num, l); // The minimum possible sum is the largest single element
        }

        // Perform binary search to find the smallest valid maximum sum
        while (l <= r) {
            long mid = (l + r) / 2; // Midpoint of current range
            if (valid(mid, nums, k)) { // Check if mid is a valid maximum sum
                result = mid; // Update result if valid
                r = mid - 1; // Try for a smaller maximum sum
            } else {
                l = mid + 1; // Increase the range to find a valid sum
            }
        }

        return (int) result;
    }

    // Helper method to check if a given maximum sum is valid
    public boolean valid(long target, int[] nums, int k) {
        int count = 1; // Number of subarrays
        long total = 0; // Current subarray sum

        for (int num : nums) {
            total += num; // Add current element to subarray sum
            if (total > target) { // If subarray sum exceeds target
                total = num; // Start a new subarray with current element
                count++; // Increment subarray count
                if (count > k) return false; // Too many subarrays, invalid
            }
        }

        return true; // Valid if number of subarrays <= k
    }
}