Split Array Largest Sum

Link

Description

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.

Return the minimized largest sum of the split.

A subarray is a contiguous part of the array.

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.

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10^6
• 1 <= k <= min(50, nums.length)

Solution

class Solution {
private:
    bool check(vector<int>& nums, int k, int mid) {
        int sum = 0, cnt = 0;
        for (int x : nums) {
            if (x > mid) return false;
            if (sum + x > mid) {
                cnt++; sum = x;
            } else {
                sum += x;
            }
        }
        if (sum) cnt++;
        return cnt <= k;
    }

public:
    int splitArray(vector<int>& nums, int k) {
        // let l = -1 instead of l = 0 to past the test case: nums = [0]
        int l = -1, r = INT_MAX;
        while (l + 1 < r) {
            int mid = (long long)l + r >> 1;
            if (check(nums, k, mid)) r = mid;
            else l = mid;
        }
        return r;
    }
};

Algorithm and Steps:

1. Binary Search Range Initialization:
   • Initialize two pointers, l and r, to -1 and INT_MAX, respectively. l is set to -1 to handle edge cases (like an array of [0]), and r is the maximum possible value.
2. Binary Search:
   • While l + 1 < r, calculate mid as the average of l and r. This mid value represents a candidate for the maximum sum of subarrays.
   • If check(nums, k, mid) returns true, it means we can split the array into k or fewer subarrays where the maximum sum of any subarray is mid or less. In this case, update r to mid.
   • If check(nums, k, mid) returns false, it means splitting the array into k subarrays with a maximum sum of mid is not possible, so update l to mid.
3. Greedy Check Function:
   • check is a helper function that takes the current mid value and checks if it's possible to split the array into k or fewer parts without exceeding mid in any part.
   • Iterate through the array nums. Accumulate the sum of elements and keep track of the number of parts (cnt) formed.
   • If adding the next element to the current sum exceeds mid, increment cnt and start a new part with the current element as its first element.
   • If an element itself is greater than mid, it's impossible to split the array as required, so return false.
   • After iterating through all elements, if there's a non-zero sum remaining, increment cnt. Then, return whether cnt is less than or equal to k.

Complexity Analysis:

Time Complexity:

• The binary search runs in \(O(\log (\mathrm{INT\_ MAX}))\), which is essentially \(O(\log n)\) since \(\mathrm{INT\_ MAX}\) is a constant.
• Each call to check requires \(O(n)\) time to go through the array.
• Therefore, the total time complexity is \(O(n \log n)\), where n is the size of the array.

Space Complexity:

• The space complexity is \(O(1)\), as only a constant amount of additional space is used for variables and no additional data structures are employed.