410. Split Array Largest Sum - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
Given an array of non-negative integers nums and an integer m, split the array into exactly m non-empty contiguous subarrays. Your task is to minimize the largest sum among these m subarrays and return that minimized largest sum.

Example Inputs & Outputs:

Example 1:
- Input: nums = [7, 2, 5, 10, 8], m = 2
- Process:
  One optimal split is [7, 2, 5] and [10, 8].
  - Sum of first subarray: 7 + 2 + 5 = 14
  - Sum of second subarray: 10 + 8 = 18
    The largest subarray sum is 18.
- Output: 18
Example 2:
- Input: nums = [1, 2, 3, 4, 5], m = 2
- Process:
  One optimal split is [1, 2, 3] and [4, 5].
  - Sum of first subarray: 1 + 2 + 3 = 6
  - Sum of second subarray: 4 + 5 = 9
    The largest subarray sum is 9.
- Output: 9
Example 3:
- Input: nums = [1, 4, 4], m = 3
- Process:
  Since each subarray must be non-empty and we need exactly 3 parts, the only split is [1], [4], and [4].
  The largest sum is 4.
- Output: 4

Constraints:

$(1 \leq \text{nums.length} \leq 10^3$ ) (or higher in some variations)
$(1 \leq m \leq \text{nums.length}$ )
$(0 \leq \text{nums}[i] \leq 10^6$ )

Hints to Approach the Problem

Hint 1:
The minimized largest sum must be at least the maximum element in the array (because every subarray must contain at least one number) and at most the total sum of all elements (if you do not split the array at all).
Hint 2:
You can use binary search on this range—[max(nums), sum(nums)]—to guess a potential answer and then check if it is possible to split the array into m or fewer subarrays without exceeding that sum.
Hint 3:
A greedy approach can be used for the checking process: iterate through the array and form subarrays such that the sum of each subarray does not exceed your current guess.

Approaches

Approach 1: Dynamic Programming (Conceptual / Brute Force)

Idea:
Use a DP formulation where dp[i][j] represents the minimum possible largest sum when splitting the first i elements into j subarrays.
Transition:
For each index i and for each possible partition point k, update
$[ dp[i][j] = \min_{k < i} \max(dp[k][j-1], \text{sum}(k+1, i)) ]$
Downside:
This approach has a time complexity of approximately $(O(n^2 \times m)$ ) and is impractical for larger inputs.

Approach 2: Binary Search + Greedy Checking (Optimal)

Idea:
Instead of exploring all splits, perform binary search over the possible range of largest sums. For a given guess (x), use a greedy strategy to see if you can split the array into at most m subarrays such that each subarray’s sum is ≤ (x).
Steps:
1. Determine Bounds:
  - Lower bound: low = max(nums)
  - Upper bound: high = sum(nums)
2. Binary Search:
  - While low < high, set mid = (low + high) // 2.
  - Check if it is possible to form at most m subarrays with each subarray sum ≤ mid.
    - Iterate through the array, accumulating a running sum.
    - When adding the next element would exceed mid, increment the subarray count and reset the running sum.
  - If you can form at most m subarrays, then mid might be a valid answer—set high = mid. Otherwise, set low = mid + 1.
3. Return:
  - Once the search finishes, low (or high) is the minimized largest sum.
Why It’s Optimal:
The greedy check runs in (O(n)) and the binary search over the range (which is proportional to the total sum) takes $(O(\log(S))$ ), where (S) is the sum of the array. Hence, the overall time complexity is $(O(n \log S)$ ).

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
- The greedy check (inside can_split or canSplit) iterates through the array in (O(n)).
- The binary search runs in $(O(\log S)$ ), where (S) is the sum of the array.
- Overall: $(O(n \log S)$ ).
Space Complexity:
- Only a constant amount of extra space is used, i.e., (O(1)).

Step-by-Step Walkthrough and Visual Example

Consider the input nums = [7, 2, 5, 10, 8] with m = 2:

Determine Bounds:
- Lower bound (low): max(nums) = 10
- Upper bound (high): sum(nums) = 32
Binary Search Iterations:
- Iteration 1:
  - mid = (10 + 32) // 2 = 21
  - Check if possible with max subarray sum = 21:
    - Subarray 1: [7, 2, 5] → Sum = 14
    - Subarray 2: [10, 8] → Sum = 18
    - Total subarrays = 2, which is ≤ m
  - Valid → set high = 21.
- Iteration 2:
  - Now low = 10, high = 21 → mid = (10 + 21) // 2 = 15
  - Check if possible with max subarray sum = 15:
    - Subarray 1: [7, 2, 5] → Sum = 14
    - Next, adding 10 would exceed 15 → start new subarray
    - Subarray 2: [10] → Sum = 10
    - Next, adding 8 → 10 + 8 = 18 > 15 → new subarray
    - Subarray 3: [8]
    - Total subarrays = 3, which is > m
  - Not valid → set low = mid + 1 = 16.
- Iteration 3:
  - low = 16, high = 21 → mid = (16 + 21) // 2 = 18
  - Check if possible with max subarray sum = 18:
    - Subarray 1: [7, 2, 5] → Sum = 14
    - Subarray 2: [10, 8] → Sum = 18
    - Total subarrays = 2, valid
  - Valid → set high = 18.
- Iteration 4:
  - low = 16, high = 18 → mid = (16 + 18) // 2 = 17
  - Check if possible with max subarray sum = 17:
    - Subarray 1: [7, 2, 5] → Sum = 14
    - Subarray 2: [10] → Sum = 10
    - Adding 8 to subarray 2 would exceed 17 (10 + 8 = 18)
    - Subarray 3: [8]
    - Total subarrays = 3, not valid
  - Not valid → set low = mid + 1 = 18.
- Now low == high == 18, so the answer is 18.

Visual Summary:

Range: [10, 32]
Iteration mid=21: Can split into 2 subarrays? Yes.   → New range: [10, 21]
Iteration mid=15: Can split into 3 subarrays? No.   → New range: [16, 21]
Iteration mid=18: Can split into 2 subarrays? Yes.   → New range: [16, 18]
Iteration mid=17: Can split into 3 subarrays? No.    → New range: [18, 18]
Final Answer: 18

Common Mistakes

Incorrect Bounds:
Setting the lower bound lower than max(nums) or the upper bound lower than sum(nums) may lead to incorrect results.
Faulty Greedy Check:
Not resetting the running sum when starting a new subarray or not counting the subarrays correctly can cause errors.
Off-by-One Errors in Binary Search:
Ensure that your binary search loop correctly updates the bounds and terminates when low equals high.

Edge Cases

Single Element Array:
When nums contains only one element, the answer is that element regardless of m (which would be 1).
m Equals Length of Array:
Every element becomes its own subarray; the answer is the maximum element in nums.
m Equals 1:
The entire array is one subarray; the answer is the sum of all elements.
All Elements are the Same:
The optimal split can still be found by the binary search; careful handling of the greedy check is needed.

Alternative Variation:
Variants where you might want to maximize the minimum sum among subarrays or split the array into a variable number of subarrays under different constraints.
Related Problems for Further Practice:
- Book Allocation Problem: Partition books among students such that the maximum number of pages assigned is minimized.
- Capacity To Ship Packages Within D Days: Find the least weight capacity needed to ship packages within D days.
- Partition Array for Maximum Sum: Other partitioning problems that involve optimizing subarray sums.