DAY 81 - 410. Split Array Largest Sum

Hey Guys!, It's day 81 and today we are going to solve another leetcode problem.

This is a problem based on binary search, so if you are unfamiliar with that, I suggest reading articles before this to get a little comfortable around it.

Question: 410. Split Array Largest Sum

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.

Problem Breakdown and Intuition:

• Let's start with breaking down the problem into different parts.
• This problem can be said to an advanced version of Capacity to Ship N packages withing D days.
• Let's get some observations clear, the maximum sum a subarray can have is total array itself. So we choose that to be our highest point.
• The question asks us the largest minimized sum, so if we just divide everything into individual elements, the element with greatest value should be our answer. Since we can never do more partitions than the number of elements themselves, It will be our left extreme ans.
• Now we are going to apply binary Search like we did in the previous problems.
• We get our mid values from our extreme low and high answers.
• We check if we can get this ans in one of our subarrays and maintain the partitions we need to.
• If we can do that, this is our answer and we divided our subarray in half by shifting end otherwise we shift our left ahead to mid+1.

Algorithm:

• Initialize the search range for the largest sum. The lower bound (low) is set to the maximum element in the nums array, and the upper bound (end) is set to the sum of all elements in the array.
• Within a loop, calculate the midpoint (mid) of the current search range (low to end).
• For the current mid, simulate splitting the array into subarrays while ensuring that the sum of elements in each subarray doesn't exceed mid. Count the number of subarrays created during this simulation.
• If the number of subarrays created is less than or equal to k, it means that the current mid value is feasible. In this case, update the search range by setting end = mid - 1 and record the current mid value as a possible answer.
• If the number of subarrays created exceeds k, it indicates that the mid value is too small. In this case, update the search range by setting low = mid + 1.
• Repeat steps 2-5 until low is no longer less than or equal to end.
• The final value of ans will represent the smallest largest sum that allows the array to be split into k subarrays.

Code:

int splitArray(vector<int>& nums, int k) {
    int low = *max_element(nums.begin(), nums.end());
    int end = accumulate(nums.begin(), nums.end(), 0);  // Initialize end to the sum of all elements

    int mid = 0;
    int ans = 0;
    int n = nums.size();  // Get the size of the nums array

    while (low <= end) {
        mid = low + (end - low) / 2;
        int count = 0;
        int tempSum = 0;

        for (int i = 0; i < n; ++i) {
            if (tempSum + nums[i] <= mid)
                tempSum += nums[i];
            else {
                count++;
                tempSum = nums[i];
            }
        }
        count++;

        if (count <= k)
            end = mid - 1, ans = mid;
        else
            low = mid + 1;
    }
    return ans;
}

Complexity Analysis: