How to Solve Split Array Largest Sum

Written By
Adam Bhula

Split Array Largest Sum Introduction

The Split Array Largest Sum problem asks us to divide the given array into k non-empty subarrays, such that the largest sum is minimized. This problem requires us to perform a binary search while initializing an appropriate range from the largest element to the total sum of the array. We iterate through the array while progressively narrowing down our search range until we find the minimum sum that meets our requirements.

Split Array Largest Sum Problem

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 Inputs and Outputs

Example 1

Input: nums = [7,2,5,10,8], k = 3
Output: 14

Example 2

Input: nums = [1,2,3,4,5], k = 2
Output: 9

Split Array Largest Sum Solutions

To solve the this problem, we'll use a binary search approach. By performing a binary search on the possible range of values for the minimum largest sum, we can find the solution. We initialize the search range with the left boundary as the maximum element in the input array nums and the right boundary as the sum of all elements in nums. This allows us to narrow down the search space and close in on the minimum largest sum that satisfies the splitting condition.

During each iteration of the binary search, we calculate the mid value within the search range and check if it is a valid choice for the minimum largest sum. To determine if it's valid, we utilize the 'canSplit' helper function we created. This function iterates through nums, keeping track of the running total and the count of subarrays. If the running total exceeds the mid value, we increment the count and reset the total to the current element. If the count exceeds the given k, it let's us know that it is not possible to split nums with the current mid value. Based on this information, we adjust the search range accordingly. We progressively narrow down the search range until we find the minimum largest sum that satisfies the splitting condition. The left boundary of the search range represents this minimum largest sum, which we return as the solution to the problem.

We also add a few early checks for the edge cases where K is 1 or K is the size of array in which makes the process much simpler and we can solve it more efficiently.

def splitArray(nums, k):
    # Edge case: Small k
    if k == 1:
        return sum(nums)
    # Edge case: Large k
    if k == len(nums):
        return max(nums)
    # Binary search to find the minimum largest sum
    left, right = max(nums), sum(nums)
    while left < right:
        mid = (left + right) // 2
        if canSplit(nums, k, mid):
            right = mid
            left = mid + 1
    return left

def canSplit(nums, k, target):
    count = 1
    total = 0
    for num in nums:
        total += num
        if total > target:
            count += 1
            total = num
            if count > k:
                return False
    return True

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

result = splitArray(nums, k)
print(f"The minimized largest sum of the split is: {result}")

Time/Space Complexity Analysis

  • Time Complexity: O(N log(S)), where N is the length of the Array and S is the total sum of nums.
  • Space Complexity: O(1), as we only use a constant amount of additional space to store variables and perform the binary search.

About interviewing.io

interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.