410. Split Array Largest Sum

HardGreedyArrayBinary SearchDynamic ProgrammingPrefix Sum

Problem Description

The goal of this problem is to find a way to divide an array nums into k non-empty contiguous subarrays in such a manner that the largest sum among those subarrays is as small as possible. In other words, we are trying to balance out the sums of these k subarrays so that no single subarray has a disproportionately large sum compared to the others.

When we split the array, every subarray has its own sum. The "largest sum" refers to the sum of subarray with highest total. If we distribute the integers in nums skillfully among the k subarrays, we can minimize this value. The challenge lies in determining the optimal way to distribute these numbers to achieve our goal.

Here's a simple example to illustrate the problem: Let's say nums = [10, 5, 30, 20] and k = 2. A possible way to split this array into two subarrays that minimize the largest sum would be [10, 5] and [30, 20], where the largest sum among subarrays is 50.

Intuition

To solve this problem, we can use binary search. The first step is to determine the search space. We know that the minimum possible value of the largest sum could be the largest number in nums (since each subarray must contain at least one number, and we cannot go lower than the maximum value). The maximum possible value would be the sum of all elements in nums (if we didn't need to split the array at all).

Once we have our search space, we can use binary search to find the minimum possible largest sum. Here's the intuition behind using binary search:

We set a middle value (mx) that could potentially be our minimized largest sum.
We create subarrays from the nums array such that each subarray has a sum that does not exceed our chosen middle value (mx).
We then count how many subarrays we form. If we can form at most k subarrays, the middle value (mx) might be too high and we could possibly divide the array in a better way, which means we should search the lower half (reduce mx).
Conversely, if we end up with more than k subarrays, that means our middle value (mx) is too low and we have not minimized the sum efficiently.
We continue the binary search, adjusting our range and mx accordingly, until we find the optimal value.

The solution employs a helper function check that uses the current mx to see if we can split the array within the desired constraints. To find the correct answer, the code uses the bisect_left function from Python's bisect module, which is a binary search implementation that returns the insertion point (as left) to the left side of a sorted array.

Learn more about Greedy, Binary Search, Dynamic Programming and Prefix Sum patterns.

Solution Approach

The solution uses a binary search to iteratively narrow down the search space for the minimum possible largest sum of the k subarrays. This approach is a clever application of binary search on an answer range instead of the traditional usage on sorted arrays.

Binary Search

Binary search begins with a left and right pointer, where left is initialized as the maximum value in nums (because this is the minimum possible sum for the largest subarray), and right is initialized as the sum of all elements in nums (since this is the maximum possible sum if all elements were in one subarray).

The `check` Function

The check function is vital to the binary search. It takes a middle value mx and iterates over nums, creating subarrays of elements whose sums do not exceed mx. If adding an element x causes the current subarray sum to exceed mx, a new subarray starts with x as the first element, incrementing the subarray count cnt.

The check function ensures we do not exceed the number of allowed subarrays (k). If cnt surpasses k, it implies that mx is too low and cannot accommodate the division of nums into k parts. Conversely, if cnt is less than or equal to k, mx could potentially be our answer or there might be a lower possible mx. Therefore, check returns a boolean indicating whether the current mx can result in k or fewer subarrays.

Narrowing the Search Space

The bisect_left function from the bisect module uses the check function as a key to perform the binary search. It looks for the place in the range from left to right where switching check from False to True would occur, which corresponds to the smallest mx that allows for the division into k or fewer subarrays.

Thus, the binary search continues to narrow the search range by adjusting the left and right pointers based on the result from the check function. The left pointer is increased if the check function returns True, and the right pointer is decreased if it returns False. When left and right converge, the left pointer marks the smallest mx that successfully divides nums into k non-empty, contiguous subarrays while minimizing the largest sum of any subarray. This is our desired answer.

Time Complexity

The time complexity of this solution is O(n log(sum(nums)-max(nums))) since the binary search requires O(log(sum(nums)-max(nums))) iterations, and during each iteration, the entire nums array of size n is traversed by the check function.

In summary, this solution approach efficiently applies binary search by utilizing the bisect module and a custom condition to ascertain the optimal way to split the array into k parts.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let us consider an example where nums = [7, 2, 5, 10, 8] and k = 2. Our goal is to divide the array nums into k contiguous subarrays such that the largest sum among these subarrays is minimized.

Step 1: Initialize Binary Search Parameters We set left equal to the maximum value in nums, which is 10 in this case, and right equal to the sum of all elements in nums, which sums up to 32.

Step 2: Binary Search Execution Now we execute the binary search with our left at 10 and our right at 32.

Iteration 1: Middle Value Calculation We take the middle value mx = (left + right) / 2, which is (10 + 32) / 2 = 21.

Step 3: The check Function Execution Using the check function with mx=21, we start summing values from nums to form subarrays where the sum does not exceed 21.

We start with 7, and then add 2 for a subtotal of 9. We can also add 5 and reach 14 which still is less than 21, but adding 10 would exceed our middle value mx. Therefore, we form a subarray [7, 2, 5] with sum 14 and start a new subarray with 10. Now 10 and 8 form the second subarray with sum 18.

We've successfully created 2 subarrays without exceeding the middle value 21 which matches our k value.

Step 4: Adjusting Binary Search Bounds Since we can create 2 subarrays that do not exceed the sum of 21 (k=2), we know that it is possible to have the largest sum as 21 or maybe even smaller. Therefore, we bring down our right bound to 21.

Now left is 10 and right is 21. We repeat the binary search process.

Iteration 2: The new mx becomes (10 + 21) / 2 = 15.5, we'll use 15 for simplicity's sake.

Reapplying the check function with mx=15, we get the following subarrays:

[7, 2, 5] which has a sum of 14. Adding 10 would exceed 15, so we stop here.
[10] starts a new subarray, and adding 8 would again exceed 15, so 10 remains its own subarray.
[8] is forced to be a subarray on its own because adding it to any previous subarray would exceed 15.

We now have 3 subarrays which exceed our k value. Therefore, the mx of 15 is too low. We need to increase our left bound to 16.

Iteration 3: We now have left as 16 and right as 21. New mx is 18.

With mx=18, we test the check function again:

[7, 2, 5] has a sum of 14. We can add 10, but the sum would be 24, exceeding 18. So again, [7, 2, 5] becomes the first subarray.
[10, 8] can be the next subarray with a sum of 18 which matches our new middle value mx.

Now we have 2 subarrays, which is equal to our desired k value. As this is valid and potentially still not optimal (it could be lower), we lower our right bound to 18.

Step 5: Convergence of Binary Search Now left is 16 and right is 18. Our new mx is 17. Applying the check with mx=17 would also result in 2 subarrays.

With the left and right bounds converging and achieving the required k subarrays, we find that our minimized largest sum across the subarrays is 17.

In this example, subarrays [7, 2, 5] and [10, 8] represent the division of nums with a minimized largest sum, which is 17. This binary search process ensures that we explore all possible configurations efficiently by focusing only on valid ranges defined by the check function's results.

This walkthrough illustrates the power of binary search in optimizing a search space to find the minimum possible largest sum for k contiguous subarrays in a given nums array.

Solution Implementation

1from typing import List
2from bisect import bisect_left
3from math import inf
4
5class Solution:
6    def splitArray(self, nums: List[int], k: int) -> int:
7        # Helper function to check if a given max array sum is feasible by counting subarray splits
8        def is_feasible(max_sum):
9            current_sum, splits = 0, 0
10            for number in nums:
11                current_sum += number
12                # If current subarray sum exceeds max_sum, we need a new subarray
13                if current_sum > max_sum:
14                    current_sum = number
15                    splits += 1
16            return splits <= k
17
18        # Set initial bounds for binary search
19        # left is the maximum value (since we cannot have a smaller sum than a single element)
20        # right is the sum of all the numbers (if we put all nums in one subarray)
21        left, right = max(nums), sum(nums)
22
23        # Perform a binary search to find the smallest feasible maximum sum
24        # We use bisect_left to find the first value in range(left, right+1)
25        # such that is_feasible returns True
26        smallest_max_sum = left + bisect_left(range(left, right + 1), True, key=is_feasible)
27
28        # Return the smallest feasible maximum sum for splitting nums into k or fewer subarrays
29        return smallest_max_sum
30

1class Solution {
2    public int splitArray(int[] nums, int maxSplits) {
3        // Initialize 'maxElement' to the largest number in the array to set the minimum possible sum,
4        // 'sumRange' to the total sum of the array to set the maximum possible sum
5        int maxElement = 0, sumRange = 0;
6
7        // Calculate the maxElement and sumRange
8        for (int num : nums) {
9            maxElement = Math.max(maxElement, num);
10            sumRange += num;
11        }
12
13        // Binary search between maxElement and sumRange to find the minimum largest sum
14        while (maxElement < sumRange) {
15            int mid = (maxElement + sumRange) >> 1; // Find the mid value between maxElement and sumRange
16          
17            // Check if the current mid can be the maximum subarray sum with at most maxSplits splits
18            if (isSplitPossible(nums, mid, maxSplits)) {
19                sumRange = mid; // If it's possible, try to find a smaller subarray sum
20            } else {
21                maxElement = mid + 1; // Otherwise, increase the subarray sum and check again
22            }
23        }
24
25        // maxElement now represents the minimum largest sum for the subarrays
26        return maxElement;
27    }
28
29    private boolean isSplitPossible(int[] nums, int maxSubarraySum, int maxSplits) {
30        int subarraySum = (1 << 30), subarrayCount = 0; // Initialize subarraySum with a large value
31      
32        // Iterate over the numbers and try to split the array into subarrays that do not exceed maxSubarraySum
33        for (int num : nums) {
34            subarraySum += num;
35
36            // When current subarraySum exceeds maxSubarraySum, increment subarrayCount
37            // and start a new subarray with the current number
38            if (subarraySum > maxSubarraySum) {
39                subarrayCount++;
40                subarraySum = num;
41            }
42        }
43
44        // Check if the number of splits required is less than or equal to the allowed maxSplits
45        return subarrayCount <= maxSplits;
46    }
47}
48

1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7    int splitArray(vector<int>& nums, int k) {
8        // Initialize the bounds for binary search.
9        int minMax = 0, sum = 0;
10        // Calculate the largest number in nums as the lower bound and the sum for the upper bound.
11        for (int num : nums) {
12            minMax = max(minMax, num);
13            sum += num;
14        }
15      
16        // Lambda function to check if it's possible to split the array into at most 'k' parts with max sum 'maxSum'.
17        auto canSplit = [&](int maxSum) {
18            int cumulativeSum = 0, parts = 1;
19            for (int num : nums) {
20                // Add current number to the cumulative sum.
21                cumulativeSum += num;
22                // If the cumulative sum exceeds maxSum, we need a new part.
23                if (cumulativeSum > maxSum) {
24                    cumulativeSum = num; // start a new part
25                    ++parts;
26                }
27            }
28            // If the number of parts required is less than or equal to k, return true.
29            return parts <= k;
30        };
31
32        // Binary search to find the minimum largest sum with which we can split the array into at most k parts.
33        while (minMax < sum) {
34            int mid = (minMax + sum) / 2;
35            // If we can split the array into at most k parts with max sum 'mid', search in the left half.
36            if (canSplit(mid)) {
37                sum = mid;
38            } 
39            // Otherwise, search in the right half.
40            else {
41                minMax = mid + 1;
42            }
43        }
44
45        // 'minMax' is now the minimum largest sum to split the array into at most k parts.
46        return minMax;
47    }
48};
49

1function splitArray(nums: number[], maxSubarrays: number): number {
2    let maxElement = 0; // Initialize the max element in the array
3    let totalSum = 0; // Initialize the total sum of the array
4
5    // Calculate the max element and total sum of the array
6    for (const num of nums) {
7        maxElement = Math.max(maxElement, num);
8        totalSum += num;
9    }
10
11    // Helper function to determine if the current maximum subarray sum 'maxSum' is valid
12    const canSplitWithMaxSum = (maxSum: number) : boolean => {
13        let subarraySum = 0; // Initialize current subarray sum
14        let subarrayCount = 1; // Initialize the subarray count, start with 1
15
16        // Check if the array can be split into subarrays with the sum not exceeding 'maxSum'
17        for (const num of nums) {
18            subarraySum += num;
19            // If adding the current element exceeds 'maxSum', start a new subarray
20            if (subarraySum > maxSum) {
21                subarraySum = num; // Current number becomes the start of the new subarray
22                subarrayCount++; // Increment the number of subarrays
23            }
24        }
25        // Return true if the required number of subarrays is less than or equal to 'maxSubarrays'
26        return subarrayCount <= maxSubarrays;
27    };
28  
29    // Binary search to find the minimum possible maximum subarray sum
30    let start = maxElement; // Lower bound for the maximum subarray sum
31    let end = totalSum; // Upper bound for the maximum subarray sum
32
33    // Perform binary search
34    while (start < end) {
35        const mid = start + ((end - start) >> 1); // Calculate mid avoiding possible overflow
36
37        // If it's possible to split with 'mid' as the maximum subarray sum
38        if (canSplitWithMaxSum(mid)) {
39            end = mid; // We might find a smaller maximum sum, search the left half
40        } else {
41            start = mid + 1; // Search the right half
42        }
43    }
44
45    // Once binary search is complete, 'start' will contain the minimum possible maximum sum
46    return start;
47}
48

Time and Space Complexity

Time Complexity

The time complexity of the splitArray function is determined by the binary search it performs and the check function it uses to validate splits.

Binary Search: The binary search is performed on a range from left (which is the maximum element in nums) to right which is the sum of all elements in nums. The number of iterations in binary search is O(log(Sum-Max)) where Sum is the sum of all elements and Max is the maximum element in the list.
Check Function: For each iteration of binary search, the check function is called, which iterates over all elements of the nums list to verify if the current maximum sum split (mx) is valid. The iteration over all n elements results in a time complexity of O(n) for the check function.

Combining these two gives us an overall time complexity of O(n * log(Sum-Max)), as the check function is called for each step of the binary search.

Space Complexity

The space complexity of the function is O(1) not including the input. This is because the check function uses only a constant amount of extra space (s and cnt) and the space used by the inputs or outputs is not counted towards the space complexity of the algorithm. The binary search itself also doesn’t consume additional space that scales with the input size, as it works on the range of ints and not on additional data structures.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know

410. Split Array Largest Sum

Problem Description

Intuition

Solution Approach

Binary Search

The check Function

Narrowing the Search Space

Time Complexity

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings

The `check` Function