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)

# Optimal Solution - Binary Search

We can use binary search to find the minimized largest sum of the split.

## Algorithm

1.  **Define Search Space:** The minimum possible largest sum is the maximum element in the array, and the maximum possible largest sum is the sum of all elements in the array.
2.  **Binary Search:**
    *   Pick a `mid` value between the minimum and maximum possible largest sum.
    *   Check if it's possible to split the array into `k` subarrays such that the sum of each subarray is less than or equal to `mid`.
    *   If it's possible, it means `mid` is a valid candidate, and we can try to minimize the largest sum further by searching in the lower half of the search space.
    *   If it's not possible, it means `mid` is too small, and we need to search in the upper half of the search space.
3.  **Return:** After the binary search, we will find the minimized largest sum.

## Code

```python
class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def is_possible(max_sum):
            count = 1
            current_sum = 0
            for num in nums:
                if current_sum + num > max_sum:
                    count += 1
                    current_sum = num
                else:
                    current_sum += num
            return count <= k

        left = max(nums)
        right = sum(nums)
        ans = right

        while left <= right:
            mid = (left + right) // 2
            if is_possible(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1

        return ans

Example

Let's consider the example nums = [7, 2, 5, 10, 8] and k = 2.

1. The minimum possible largest sum is max(nums) = 10.

2. The maximum possible largest sum is sum(nums) = 32.

3. We perform binary search in the range [10, 32].

   • mid = (10 + 32) // 2 = 21. We check if it's possible to split the array into 2 subarrays such that the sum of each subarray is less than or equal to 21. Yes, it's possible: [7, 2, 5, 10] and [8]. We update ans = 21 and search in the range [10, 20].
   • mid = (10 + 20) // 2 = 15. We check if it's possible to split the array into 2 subarrays such that the sum of each subarray is less than or equal to 15. No, it's not possible. We need at least 3 subarrays: [7, 2, 5], [10], and [8]. We search in the range [16, 20].
   • mid = (16 + 20) // 2 = 18. We check if it's possible to split the array into 2 subarrays such that the sum of each subarray is less than or equal to 18. Yes, it's possible: [7, 2, 5] and [10, 8]. We update ans = 18 and search in the range [16, 17].
   • mid = (16 + 17) // 2 = 16. We check if it's possible to split the array into 2 subarrays such that the sum of each subarray is less than or equal to 16. No, it's not possible. We need at least 3 subarrays: [7, 2, 5], [10], and [8]. We search in the range [17, 17].
   • mid = (17 + 17) // 2 = 17. We check if it's possible to split the array into 2 subarrays such that the sum of each subarray is less than or equal to 17. No, it's not possible. We need at least 3 subarrays: [7, 2, 5], [10], and [8]. We search in the range [18, 17]. The loop terminates.

4. The minimized largest sum is 18.

Big(O) Time Complexity Analysis

• The is_possible function iterates through the nums array once, so its time complexity is O(n), where n is the length of the nums array.
• The binary search loop runs log(sum(nums) - max(nums)) times. In the worst case, sum(nums) - max(nums) can be O(sum(nums)).
• Therefore, the overall time complexity is O(n * log(sum(nums))), where n is the length of the nums array.

Big(O) Space Complexity Analysis

• The space complexity is O(1) because we are only using a few variables to store the left, right, mid, and answer values.

Edge Cases

• Empty array: If the input array is empty, the function should return 0. However, the constraint specifies 1 <= nums.length, so this case does not need to be handled.
• k = 1: If k is 1, the function should return the sum of all elements in the array.
• k = nums.length: If k is equal to the length of the array, the function should return the maximum element in the array.
• Large values in the array: If the array contains very large values, the sum of all elements may overflow. This can be avoided by using 64-bit integers.

Brute Force Solution

A brute force solution would involve trying all possible splits of the array into k subarrays and finding the minimum of the largest sums among all splits.

Algorithm

1. Generate all possible combinations of splitting the array into k subarrays.
2. For each combination, calculate the sum of each subarray.
3. Find the maximum sum among the k subarrays.
4. Keep track of the minimum of the maximum sums among all combinations.
5. Return the minimum of the maximum sums.

Code

import itertools

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if k == 1:
            return sum(nums)
        if k == n:
            return max(nums)

        min_largest_sum = float('inf')

        for i in range(1 << (n - 1)):
            splits = []
            current_subarray = []
            subarray_count = 1

            for j in range(n):
                current_subarray.append(nums[j])
                if j < n - 1 and (i >> j) & 1:
                    splits.append(current_subarray)
                    current_subarray = []
                    subarray_count += 1

            splits.append(current_subarray)

            if subarray_count == k:
                largest_sum = 0
                for subarray in splits:
                    largest_sum = max(largest_sum, sum(subarray))
                min_largest_sum = min(min_largest_sum, largest_sum)

        return min_largest_sum

Big(O) Time Complexity Analysis

The brute force solution has an exponential time complexity because it needs to iterate through all possible splits. In the worst case, it has O(2^n).

Big(O) Space Complexity Analysis

The space complexity is O(n), due to storing the splits.