Log inSign up
hardleetcodeNot Started

Split Array Largest Sum

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.

Binary Search
Solve on leetcode
Lesson

Problem Statement

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 1 · Example 1: Standard Allocation:

Input: arr = [12, 34, 67, 90], m = 2
Output: 113
Explanation: Student 1 gets [12, 34, 67] (113 pages), Student 2 gets [90] (90 pages). Max pages is 113.

Example 2 · Example 2: Impossible Allocation:

Input: arr = [25, 46, 28, 49, 24], m = 6
Output: -1
Explanation: 6 students but only 5 books, so impossible.

Constraints:

  • 1 <= arr.length <= 105
  • 1 <= arr[i] <= 106
  • 1 <= m <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model contiguous partitioning minimax problems via binary search on answer.
  • Understand why low = max(arr) and high = sum(arr) are mathematically precise bounds.
  • Implement greedy contiguous segment accumulation in O(n).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Partition array into m contiguous subarrays to minimize the maximum sum.
  • Monotonic predicate: larger capacity means fewer or equal students needed.
  • Classic minimax partitioning problem.

Algorithmic Decision Tree:

  • If m > arr.length -> return -1.
  • low = max(arr), high = sum(arr), ans = high.
  • While low <= high: mid = low + (high - low) / 2.
  • If countStudents(mid) <= m -> ans = mid, high = mid - 1.
  • Else low = mid + 1.
  • Return ans.

Connected Patterns:

Allocate Minimum Number of PagesPainter's Partition ProblemSplit Array Largest SumCapacity To Ship Packages Within D Days

1. Linear Page Limit Increment

Intuition

Loop pages from max(arr) to sum(arr). For each limit, simulate greedy student packing. Return the first limit where students <= m.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If m > arr.length return -1.
  2. Step 2: Loop limit from max(arr) to sum(arr).
  3. Step 3: If countStudents(limit) <= m return limit.
  4. Step 4: Return sum(arr).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int findPages(vector<int>& arr, int k) {
8 if (k > (int)arr.size()) return -1;
9 int low = 0, high = 0;
10 for (int x : arr) { low = max(low, x); high += x; }
11 for (int pages = low; pages <= high; ++pages) {
12 int students = 1, current = 0;
13 for (int x : arr) {
14 if (current + x > pages) {
15 students++;
16 current = 0;
17 }
18 current += x;
19 }
20 if (students <= k) return pages;
21 }
22 return high;
23}
24
25int main() {
26 // Sample driver execution
27 cout << "Execution completed successfully." << endl;
28 return 0;
29}
30

Time & Space Complexity

  • Time complexity: O(n * (sum(arr) - max(arr))) — Takes up to sum(arr) iterations of O(n) work each.
  • Space complexity: O(1) — O(1) memory.

2. Bounded Linear Search Starting from Average

Intuition

Mathematically, the answer cannot be less than ceil(sum(arr) / m). Starting linear scan at max(max(arr), sum/m) cuts down iterations.

When to apply: When search range is moderate.

Algorithm

  1. Step 1: If m > n return -1.
  2. Step 2: Start pages = max(max(arr), sum(arr)/m).
  3. Step 3: Test pages sequentially until countStudents(pages) <= m.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int findPages(vector<int>& arr, int k) {
8 if (k > (int)arr.size()) return -1;
9 long long sum = 0; int maxV = 0;
10 for (int x : arr) { maxV = max(maxV, x); sum += x; }
11 int start = max((long long)maxV, (sum + k - 1) / k);
12 for (int pages = start; pages <= sum; ++pages) {
13 int students = 1, current = 0;
14 for (int x : arr) {
15 if (current + x > pages) {
16 students++;
17 current = 0;
18 }
19 current += x;
20 }
21 if (students <= k) return pages;
22 }
23 return sum;
24}
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n * (sum - sum/m)) — Linear scan on the remaining domain.
  • Space complexity: O(1) — O(1) auxiliary space.

3. Binary Search on Answer Range

Intuition

If m > arr.length, return -1. Set low = max(arr), high = sum(arr), ans = high. While low <= high, compute mid. Simulate student count: if countStudents(mid) <= m, ans = mid and high = mid - 1; else low = mid + 1.

When to apply: Standard optimal solution.

Algorithm

  1. Step 1: If m > arr.length return -1.
  2. Step 2: low = max(arr), high = sum(arr), ans = high.
  3. Step 3: While low <= high:
  4. - mid = low + (high - low) / 2.
  5. - students = 1, current = 0.
  6. - For x in arr: if current + x > mid { students++; current = 0; } current += x.
  7. - If students <= m: ans = mid, high = mid - 1.
  8. - Else low = mid + 1.
  9. Step 4: Return ans.

Trace for arr = [12, 34, 67, 90], m = 2

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Range [90, 203]
Visual state
Values and pointers at this exact step
pointers
S
12
34
67
90
0
↑ low
1
2
↑ mid
3
↑ high
Check / comparison
At max pages 146: students needed = 2 <= 2 -> Feasible.
Decision / next transition
Record ans = 146, set high = 145.
Why this step matters

Range [90, 203]. mid=146. Student 1: 12+34+67 = 113 <= 146. Next book 90 exceeds 146 (113+90=203). Student 2 gets 90. Total students = 2 <= 2. Feasible! ans=146. high = mid - 1 = 145.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int findPages(vector<int>& arr, int k) {
8 if (k > (int)arr.size()) return -1;
9 long long low = 0, high = 0;
10 for (int x : arr) {
11 low = max(low, (long long)x);
12 high += x;
13 }
14 long long ans = high;
15 while (low <= high) {
16 long long mid = low + (high - low) / 2;
17 int students = 1;
18 long long current = 0;
19 for (int x : arr) {
20 if (current + x > mid) {
21 students++;
22 current = 0;
23 }
24 current += x;
25 }
26 if (students <= k) {
27 ans = mid;
28 high = mid - 1;
29 } else {
30 low = mid + 1;
31 }
32 }
33 return (int)ans;
34}
35
36int main() {
37 // Sample driver execution
38 cout << "Execution completed successfully." << endl;
39 return 0;
40}
41

Time & Space Complexity

  • Time complexity: O(n * log(sum(arr) - max(arr))) — Search space [max, sum] is bounded by 1011, taking at most 40 binary search steps of O(n) simulation.
  • Space complexity: O(1) — Requires O(1) auxiliary variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Page ScanO(n * range)O(1)Test each page limit sequentially.Iterates through all possible page sums.
2.Bounded Linear SearchO(n * range)O(1)Start from max(max, sum/m).Sequential stepping.
3.Binary Search on AnswerOptimalO(n * log(range))O(1)Binary search on monotonic capacity domain [max, sum].None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • m > n -> return -1 immediately.
  • m == 1 -> return sum(arr).
  • m == n -> return max(arr).
  • All books have the same page count.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify that 'Book Allocation Problem', 'Allocate Minimum Number of Pages', Painters Partition Problem', and 'Split Array Largest Sum' are all mathematically identical.
  2. Explain the greedy choice: filling each student's quota as much as possible without exceeding mid minimizes student count.
  3. Watch for integer overflow in sum(arr) (use long in Java/C++).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the lower bound for the binary search in the Book Allocation Problem?

Back to DSA Sheet