Scale Engineer

Split Array Largest Sum

Hard
#0397Time: O(k * n^2), where `n` is the number of elements and `k` is the number of splits. There are three nested loops to fill the DP table.Space: O(k * n), for the 2D DP table of size `(k+1) x (n+1)` and the prefix sum array of size `n+1`.9 companies
Patterns
Dynamic ProgrammingGreedyPrefix Sum
Algorithms
Binary Search
Data structures
Array
Companies
TekionPornHubSalesforceZeta

Prompt

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:

Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

Example 2:

Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.

 

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 106
  • 1 <= k <= min(50, nums.length)

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem by breaking it down into smaller, overlapping subproblems. We build a table dp[i][j] which stores the minimum largest subarray sum for splitting the first j elements of the array into i parts. The final answer is found by computing the value for splitting the entire array into k parts.

Algorithm

  • Define a 2D array dp[i][j] to store the minimum largest subarray sum for splitting the first j elements of nums into i subarrays.
  • The goal is to compute dp[k][n], where n is the length of the array.
  • To avoid recomputing sums, pre-calculate a prefixSum array where prefixSum[i] is the sum of elements from nums[0] to nums[i-1].
  • The base case is for i=1: dp[1][j] = prefixSum[j], as splitting j elements into one subarray results in the sum of those j elements.
  • The transition to compute dp[i][j] involves trying all possible split points p (where 0 <= p < j). The last subarray would be nums[p...j-1], and the first p elements would have been split into i-1 subarrays.
  • The recurrence relation is: dp[i][j] = min(dp[i][j], max(dp[i-1][p], prefixSum[j] - prefixSum[p])) for all valid p.
  • The final answer is dp[k][n].

Walkthrough

In this dynamic programming approach, we define dp[i][j] as the minimum largest sum required to split the subarray nums[0...j-1] (the first j elements) into i non-empty subarrays. Our objective is to find dp[k][n], where n is the length of nums.

The state transition is formulated by considering all possible split points for the last (i-th) subarray. If we decide the i-th subarray is nums[p...j-1], then the first p elements (nums[0...p-1]) must have been optimally split into i-1 subarrays. The largest sum for this specific split would be the maximum of the sum of the last subarray (sum(nums[p...j-1])) and the result for the prefix (dp[i-1][p]). We want to choose a split point p that minimizes this value.

To make the calculation of subarray sums efficient, we pre-compute a prefix sum array. This allows us to find the sum of any subarray in O(1) time.

class Solution {    public int splitArray(int[] nums, int k) {        int n = nums.length;        long[] prefixSum = new long[n + 1];        for (int i = 0; i < n; i++) {            prefixSum[i + 1] = prefixSum[i] + nums[i];        }         long[][] dp = new long[k + 1][n + 1];        for (int i = 0; i <= k; i++) {            for (int j = 0; j <= n; j++) {                dp[i][j] = Long.MAX_VALUE;            }        }        dp[0][0] = 0;         for (int i = 1; i <= k; i++) { // Number of subarrays            for (int j = 1; j <= n; j++) { // Number of elements                for (int p = 0; p < j; p++) { // Split point                    long lastSum = prefixSum[j] - prefixSum[p];                    if (dp[i - 1][p] != Long.MAX_VALUE) {                        long currentMax = Math.max(dp[i - 1][p], lastSum);                        dp[i][j] = Math.min(dp[i][j], currentMax);                    }                }            }        }        return (int) dp[k][n];    }}

Complexity

Time

O(k * n^2), where `n` is the number of elements and `k` is the number of splits. There are three nested loops to fill the DP table.

Space

O(k * n), for the 2D DP table of size `(k+1) x (n+1)` and the prefix sum array of size `n+1`.

Trade-offs

Pros

  • It is a systematic approach that guarantees finding the optimal solution.

  • The logic is relatively straightforward to formulate for those familiar with dynamic programming.

Cons

  • The time complexity of O(k * n^2) can be too slow if n is large.

  • The space complexity of O(k * n) can be substantial for large k and n.

Solutions

class Solution {public  int splitArray(int[] nums, int k) {    int left = 0, right = 0;    for (int x : nums) {      left = Math.max(left, x);      right += x;    }    while (left < right) {      int mid = (left + right) >> 1;      if (check(nums, mid, k)) {        right = mid;      } else {        left = mid + 1;      }    }    return left;  }private  boolean check(int[] nums, int mx, int k) {    int s = 1 << 30, cnt = 0;    for (int x : nums) {      s += x;      if (s > mx) {        ++cnt;        s = x;      }    }    return cnt <= k;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem