Why does the search start with the maximum element in the array?

The largest single element sets the absolute lower floor for our answer. Since every item must be assigned to a subarray, the max element will be in one of the subarrays. Thus, the sum of that subarray can never be less than that element itself.

What if k is equal to the length of the array?

If k matches the array length, every single element becomes its own independent subarray. The largest sum will simply be the largest individual element in the array.

Why does the feasibility check use at most k subarrays instead of exactly k?

If a limit works with fewer than k subarrays, some subarray can be split further to create exactly k non-empty subarrays. Splitting does not increase any subarray sum.

Why does finding a valid sum cause us to move the upper bound down?

Our main objective is to minimize the largest sum. Even if a limit works and satisfies the condition of using k or fewer subarrays, there might still exist a smaller limit that also safely works. Pulling the upper boundary down allows us to keep searching for that smaller optimized number.

Split Array Largest Sum Using Binary Search

Q: What does "contiguous part of the array" mean?

Contiguous means the elements inside the subarray must sit directly next to each other in the original array without any gaps. You cannot skip elements or reorder them when forming a subarray.

Given an integer array and an integer k, your task is to divide the array into k contiguous, non-empty subarrays. You must perform this Split Array Largest Sum operation in such a way that the largest sum among these k subarrays is minimized. Your function needs to return this minimized largest sum.

Example 1

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

Output: 18

Explanation: The best way to divide the array into 2 subarrays is [7, 2, 5] and [10, 8]. The sum of the first subarray is 14, and the sum of the second is 18. The largest sum between the two is 18. Any other division would result in a largest sum greater than 18.

Example 2

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

Output: 9

Explanation: The best way to divide the array is [1, 2, 3] and [4, 5]. The sums are 6 and 9. The largest sum is 9, which is the absolute minimum possible for 2 contiguous subarrays.

Practice it by yourself before moving onto the solutionTry now

Brute Force Approach

The smallest possible answer cannot be less than the largest element in the array. Every element must belong to some subarray, so the subarray containing the largest element will have at least that much sum.

The largest answer we ever need is the total sum of the array. That happens when all elements are kept in one subarray. So the answer must lie between: max(nums) and sum(nums)

The direct idea is to try every possible value in this range as the allowed maximum subarray sum. For each value, greedily scan the array and count how many subarrays are needed if no subarray is allowed to cross that value. If the needed number of subarrays is at most k, that value is possible. The first possible value is the answer because values are checked from small to large.

Algorithm

Find the largest element and the total sum of the array. The largest element becomes the smallest answer worth trying, and the total sum becomes the largest answer worth trying.
Try every possible maximum sum from the lower bound to the upper bound. This is done in increasing order so the first valid value is guaranteed to be minimum.
For each chosen value, scan the array from left to right and keep the sum of the current subarray. The scan must stay left to right because subarrays must be contiguous.
If adding the next number would cross the chosen maximum sum, start a new subarray from that number. This gives the minimum number of subarrays needed for that chosen limit.
If the number of subarrays needed is at most k, return the chosen value. Even if fewer than k subarrays are formed, they can be split further without increasing the largest sum.

Dry Run

Split Array Largest Sum Brute Dry Run

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
  /*
  Counts how many subarrays are needed
  when no subarray sum can exceed maxAllowed.
  */
  int countSubarrays(vector<int>& nums, int maxAllowed) {
      // At least one subarray is needed when nums is not empty.
      int subarrays = 1;
13
      // This stores the sum of the current subarray.
      int currentSum = 0;
16
      for (int num : nums) {
          // Start a new subarray when adding num
          // would cross the allowed maximum sum.
          if (currentSum + num > maxAllowed) {
              subarrays++;
22
              // The current number begins the next subarray.
              currentSum = num;
          } else {
              // The current number still fits,
              // so keep it in the same subarray.
              currentSum += num;
          }
      }
31
      return subarrays;
  }
34
  /*
  Returns the minimized largest subarray sum
  by trying every possible answer.
  */
  int splitArray(vector<int>& nums, int k) {
      // The answer cannot be smaller than the largest element.
      int low = *max_element(nums.begin(), nums.end());
42
      // The answer never needs to be larger than the total sum.
      int high = accumulate(nums.begin(), nums.end(), 0);
45
      for (int maxAllowed = low; maxAllowed <= high; maxAllowed++) {
          // The first valid value is minimum because
          // values are checked from small to large.
          if (countSubarrays(nums, maxAllowed) <= k) {
              return maxAllowed;
          }
      }
53
      return high;
  }
56};
57
58// Driver code starts
59int main() {
  vector<int> nums = {7, 2, 5, 10, 8};
  int k = 2;
62
  Solution obj;
  cout << obj.splitArray(nums, k) << endl;
65
  return 0;
67}

Complexity Analysis

Time Complexity: O(N x (Sum - Max + 1)), N is the length of nums array, because every possible maximum sum may scan the whole array.

Space Complexity: O(1), because constant space is used.

Optimal Approach

The important observation is how the chosen maximum allowed sum affects the number of subarrays. If the allowed maximum sum is small, each subarray can hold only a little, so more subarrays are needed. If the allowed maximum sum is large, each subarray can hold more elements, so fewer subarrays are needed. That creates a monotonic pattern:

not possible, not possible, possible, possible, possible

The answer is the first possible value. For a fixed value, the best way to count subarrays is greedy. Keep adding elements to the current subarray while the sum stays within the limit. Start a new subarray only when the next element would overflow the limit.

This greedy check uses the fewest subarrays for that limit because it keeps every subarray as full as possible before cutting. If even this greedy method needs more than k subarrays, no other split can make that limit work.

One small doubt often appears here: the problem asks for exactly k subarrays, but the check uses at most k. This works because if a limit can make fewer than k subarrays, any subarray with more than one element can be split further. Splitting only makes sums smaller or equal, so the largest sum does not increase.

Algorithm

Set the search range from max(nums) to sum(nums). The lower bound is needed because every element must fit inside some subarray, and the upper bound is enough because the whole array can be one subarray.
Pick the middle value of the range. Treat this value as the maximum allowed subarray sum, not as an array index.
Check whether the array can be split with this limit. Scan from left to right, add numbers to the current subarray, and start a new subarray only when adding the next number would cross the limit.
If the check uses at most k subarrays, the limit is valid. Store it as a possible answer and search the left half because a smaller valid limit may exist.
If the check uses more than k subarrays, the limit is too small. Search the right half because larger limits allow subarrays to carry more sum.
When the search ends, return the smallest valid value found.

Key Points

Checking <= k is correct even though the final split needs exactly k subarrays.
k == 1 makes the answer equal to sum(nums).
k == nums.length makes the answer equal to max(nums).

Dry Run

Split array Largest Sum Optimal Dry Run

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
  /*
  Checks whether nums can be split into at most k subarrays
  when no subarray sum can exceed maxAllowed.
  */
  bool canSplit(vector<int>& nums, int k, int maxAllowed) {
      // At least one subarray is needed when nums is not empty.
      int subarrays = 1;
13
      // This stores the sum of the current subarray.
      int currentSum = 0;
16
      for (int num : nums) {
          // Start a new subarray when adding num
          // would make the current sum too large.
          if (currentSum + num > maxAllowed) {
              subarrays++;
22
              // The current number begins the new subarray.
              currentSum = num;
25
              // More than k subarrays means this limit is too small.
              if (subarrays > k) {
                  return false;
              }
          } else {
              // The number fits in the current subarray,
              // so no new split is needed here.
              currentSum += num;
          }
      }
36
      // The limit works when at most k subarrays are needed.
      return subarrays <= k;
  }
40
  /*
  Returns the minimized largest subarray sum
  using binary search on possible answer values.
  */
  int splitArray(vector<int>& nums, int k) {
      // The answer cannot be smaller than the largest element.
      int low = *max_element(nums.begin(), nums.end());
48
      // The answer never needs to be larger than the total sum.
      int high = accumulate(nums.begin(), nums.end(), 0);
51
      // This stores the smallest valid limit found so far.
      int answer = high;
54
      while (low <= high) {
          // mid is the maximum subarray sum being tested.
          int mid = low + (high - low) / 2;
58
          // If mid works, try to find a smaller valid limit.
          if (canSplit(nums, k, mid)) {
              answer = mid;
              high = mid - 1;
          } else {
              // If mid fails, a larger limit is required.
              low = mid + 1;
          }
      }
68
      return answer;
  }
71};
72
73// Driver code starts
74int main() {
  vector<int> nums = {7, 2, 5, 10, 8};
  int k = 2;
77
  Solution obj;
  cout << obj.splitArray(nums, k) << endl;
80
  return 0;
82}

Complexity Analysis

Time Complexity: O(N x log₂(Sum - Max + 1)), N is the length of nums array, because every binary-search check scans the array once. Binary search has a range of Sum-Max+1 giving complexity of log₂(Sum-Max+1).

Space Complexity: O(1), because constant space is used.

Interview follow-up Questions

Contiguous means the elements inside the subarray must sit directly next to each other in the original array without any gaps. You cannot skip elements or reorder them when forming a subarray.

Split Array Largest Sum Using Binary Search

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Key Points

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Row wise traversal

Main Diagonal Print

Search Element in Matrix