Naive Approach (Brute Force)

The most straightforward approach is to try all possible ways to split the array into k subarrays. For each split, calculate the maximum sum of the subarrays and keep track of the minimum of these maximum sums.

This approach involves generating all possible combinations of subarrays, calculating their sums, and finding the maximum among those sums. Since we want to minimize the largest sum, we will keep track of the minimum of these maximum subarray sums across all possible splits.

This method is computationally expensive, particularly as the size of the input array increases. Due to its inefficient nature, a brute force solution would likely not be suitable for large input arrays or online assessment scenarios.

Complexity Analysis

• Time Complexity: O(2^n-1), where n is the length of the nums array. This is because we are essentially exploring every possible split point between the elements.
• Space Complexity: O(n), to store the sums and intermediate results.

Optimal Approach (Binary Search)

A more efficient approach involves using binary search. The idea is to binary search for the minimized largest sum within a feasible range. The lower bound of the range is the maximum element in the array (since each element must belong to a subarray), and the upper bound is the sum of all elements in the array.

For a given potential mid value (a potential minimized largest sum), we check if it's possible to split the array into k or fewer subarrays such that the sum of each subarray does not exceed mid. We can determine this greedily by iterating through the array and creating new subarrays whenever the current subarray sum exceeds mid.

If it's possible to split the array into k or fewer subarrays, then mid is a valid minimized largest sum or potentially larger than the actual minimized largest sum. We then try a smaller value for mid by updating the upper bound.

Otherwise, if it's not possible to split the array into k or fewer subarrays, it means mid is too small, and we need to increase it by updating the lower bound.

Edge Cases

• If k is 1, the result is the sum of all numbers.
• If k is equal to the number of elements, the result is the largest number.

Example

nums = [7, 2, 5, 10, 8], k = 2

1. Lower bound: 10 (max element)
2. Upper bound: 32 (sum of all elements)

Binary search between 10 and 32:

• mid = (10 + 32) / 2 = 21 Try to split into 2 or fewer subarrays with a max sum of 21: [7, 2, 5, 10], [8] - This splits into 2. Good.
• mid = (10 + 21) / 2 = 15 Try to split into 2 or fewer subarrays with a max sum of 15: [7, 2, 5], [10], [8] - This splits into 3. Bad.
• Eventually you will converge on 18: [7, 2, 5], [10, 8].

Code

def splitArray(nums, k):
    def is_possible(mid):
        count = 1
        current_sum = 0
        for num in nums:
            if current_sum + num > mid:
                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

Complexity Analysis

• Time Complexity: O(n log(S)), where n is the number of elements in nums, and S is the sum of all elements. The binary search takes O(log(S)) time, and the is_possible function takes O(n) time.
• Space Complexity: O(1), as we are using only a constant amount of extra space.