Coding

Split array - largest sum

Asked at

Google

Zeta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer array a of size n and an integer k. Split the array a into k non-empty subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split.

Input: a = [1, 2, 3, 4, 5], k = 3 Output:6 Explanation: There are many ways to split the array a[] into k consecutive subarrays. The best way to do this is to split the array a[] into [1, 2, 3], [4], and [5], where the largest sum among the three subarrays is only 6.

Input: a = [3,5,1], k = 3 Output: 5 Explanation: There is only one way to split the array a[] into 3 subarrays, i.e., [3], [5], and [1]. The largest sum among these subarrays is 5.

Input: a = [1, 2, 3, 4, 5], k = 2

1 ≤ n ≤ 104
1 ≤ k ≤ n
1 ≤ a[i] ≤ 104

cpp

class Solution {
public:
    int largestSubarraySumMinimized(vector<int> &a, int k) {
        
    }
};

java

class Solution {
    public int largestSubarraySumMinimized(int[] a, int k) {
     
    }
}

python

class Solution:
    def largestSubarraySumMinimized(self, a, k):

javascript

class Solution {
    largestSubarraySumMinimized(a, k) {
        
    }
}

csharp

public class Solution
{
    public int LargestSubarraySumMinimized(int[] a, int k)
    {
     
    }
}

func largestSubarraySumMinimized(a []int, k int) int {
    //your code goes here
}

Stuck? Show a way to structure it+

01Search between the maximum item and total sum.
02Greedily count partitions needed for a candidate limit.
03Start a new partition when adding an item exceeds the limit.
04Use partition count as the feasibility predicate.
05Return the first feasible limit.

Reference answer

The answer lies between the largest element, which cannot be split, and the total sum, which is one partition. Binary-search a candidate maximum sum limit. To test it, scan left to right, greedily add each number to the current partition; when the next addition would exceed limit, start a new partition and increment the count. This greedy rule minimizes the number of partitions for that limit, so the limit is feasible when the count is at most m. Feasibility is monotonic: if a limit works, any larger limit works. Therefore return the first working value. Each check is O(N) and the full algorithm is O(N log(sum)) time with O(1) extra space. This assumes non-negative numbers, which should be stated.

Then expect these follow-ups

How would you reconstruct the partitions?
Tests: greedy reconstruction
Why do negative values break this approach?
Tests: assumptions

Hiring now

Zeta has 99 open roles right now

Also hiring: Google

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer
New York, NY
Lead Software Engineer
Bangalore, India
Senior Software Engineer, Data Platform
San Francisco, CA

Or practice this question first

Next question