410. Split Array Largest Sum – Leetcode Solutions

Example 1:

Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        # Helper function to check if a target maximum sum is feasible
        def canSplit(target: int) -> bool:
            current_sum = 0
            subarrays = 1  # Start with one subarray
            for num in nums:
                if current_sum + num > target:
                    # Create a new subarray
                    subarrays += 1
                    current_sum = num
                    # If we exceed k subarrays, the target is not feasible
                    if subarrays > k:
                        return False
                else:
                    current_sum += num
            return True
        
        # Binary search range
        left, right = max(nums), sum(nums)
        result = right  # Initialize result to the upper bound
        
        while left <= right:
            mid = (left + right) // 2
            if canSplit(mid):
                # If it's feasible, try a smaller maximum sum
                result = mid
                right = mid - 1
            else:
                # If it's not feasible, try a larger maximum sum
                left = mid + 1
        
        return result

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        // Helper function to determine if we can split the array into
        // k or fewer subarrays such that no subarray has a sum greater than `maxSum`.
        auto canSplit = [&](int maxSum) -> bool {
            int currentSum = 0;
            int splits = 1; // Start with one subarray
            
            for (int num : nums) {
                // If adding this element exceeds maxSum, start a new subarray
                if (currentSum + num > maxSum) {
                    splits++;
                    currentSum = num; // Start a new subarray with the current number
                    if (splits > k) return false; // Too many subarrays needed
                } else {
                    currentSum += num; // Add to the current subarray
                }
            }
            return true; // Successfully split into k or fewer subarrays
        };

        // Binary search bounds
        int left = *max_element(nums.begin(), nums.end()); // Minimum possible max sum
        int right = accumulate(nums.begin(), nums.end(), 0); // Maximum possible max sum

        int result = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canSplit(mid)) {
                result = mid; // Update the result as we found a feasible solution
                right = mid - 1; // Try for a smaller max sum
            } else {
                left = mid + 1; // Increase max sum as the current one is not feasible
            }
        }

        return result;
    }
};

var splitArray = function(nums, k) {
    /**
     * Helper function to determine if it's possible to split the array into
     * `k` or fewer subarrays where the largest subarray sum is <= maxSum.
     * @param {number} maxSum - Maximum allowable sum for a subarray
     * @return {boolean} - True if it's possible to split, false otherwise
     */
    const canSplit = (maxSum) => {
        let subarrayCount = 1; // Start with one subarray
        let currentSum = 0;    // Sum of the current subarray

        for (const num of nums) {
            if (currentSum + num > maxSum) {
                // Create a new subarray if adding this number exceeds maxSum
                subarrayCount++;
                currentSum = num;

                // If the number of subarrays exceeds k, return false
                if (subarrayCount > k) {
                    return false;
                }
            } else {
                // Otherwise, add the number to the current subarray
                currentSum += num;
            }
        }

        return true; // Successfully split into k or fewer subarrays
    };

    // The smallest possible max sum is the largest number in the array
    let left = Math.max(...nums);
    // The largest possible max sum is the sum of all numbers in the array
    let right = nums.reduce((a, b) => a + b, 0);

    // Perform binary search to find the minimized largest sum
    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (canSplit(mid)) {
            // If it's possible to split with this max sum, try a smaller value
            right = mid;
        } else {
            // Otherwise, increase the max sum
            left = mid + 1;
        }
    }

    // The left pointer now points to the minimized largest sum
    return left;
};

class Solution {
    public int splitArray(int[] nums, int k) {
        // Initialize the lower and upper bounds for binary search
        int left = getMax(nums); // Minimum possible largest sum
        int right = getSum(nums); // Maximum possible largest sum

        // Perform binary search to find the minimum largest sum
        while (left < right) {
            int mid = left + (right - left) / 2;
            // Check if it's possible to split the array with the current mid as the largest sum
            if (canSplit(nums, k, mid)) {
                right = mid; // Try for a smaller largest sum
            } else {
                left = mid + 1; // Increase the largest sum
            }
        }

        return left; // The minimum largest sum
    }

    // Helper method to find the maximum value in the array
    private int getMax(int[] nums) {
        int max = nums[0];
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }

    // Helper method to calculate the sum of all elements in the array
    private int getSum(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }

    // Helper method to determine if the array can be split into k subarrays with the largest sum <= mid
    private boolean canSplit(int[] nums, int k, int mid) {
        int currentSum = 0; // Sum of the current subarray
        int subarrays = 1; // Count of subarrays (at least one)

        for (int num : nums) {
            // If adding this number exceeds the mid value, start a new subarray
            if (currentSum + num > mid) {
                subarrays++;
                currentSum = num;
                // If the number of subarrays exceeds k, return false
                if (subarrays > k) {
                    return false;
                }
            } else {
                currentSum += num; // Add the number to the current subarray
            }
        }

        return true; // The array can be split into k or fewer subarrays
    }
}