Split Array Largest Sum - Practice Coding Problems

Split Array Largest Sum - Problem

Array Binary Search Dynamic Programming Greedy Prefix Sum Hard

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.

Input & Output

Example 1 — Basic Split

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

› Output: 18

💡 Note: Split into [7,2,5] and [10,8]. The sums are 14 and 18, so the largest sum is 18, which is minimal among all possible splits.

Example 2 — Multiple Small Subarrays

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

› Output: 9

💡 Note: Split into [1,2,3,4] and [5]. The sums are 10 and 5, giving largest sum 10. Better split: [1,2,3] and [4,5] gives sums 6 and 9, so answer is 9.

Example 3 — Edge Case k=1

$ Input: nums = [1,4,4], k = 1

› Output: 9

💡 Note: Cannot split array when k=1, so return sum of entire array: 1+4+4=9.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ k ≤ min(50, nums.length)
0 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [7,2,5,10,8] with k=2 splits needed

Process

Find split positions that minimize largest subarray sum

Output

Minimum largest sum = 18

Key Takeaway

🎯 Key Insight: Binary search on the answer range combined with greedy validation gives optimal O(n log sum) solution

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is that we can binary search on the answer space - the minimum possible largest sum lies between max(nums) and sum(nums). Best approach is Binary Search on Answer with greedy validation. Time: O(n log(sum)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Splits	O(k^n)	O(k)	Generate all possible ways to split array into k parts and find minimum largest sum
Binary Search on Answer Space	O(n log(sum))	O(1)	Binary search on the possible range of largest sums, checking if each candidate is achievable with k splits
Dynamic Programming - 2D Table	O(n²k)	O(nk)	Build optimal solution using 2D DP table where dp[i][j] = min largest sum for first i elements with j splits

Brute Force - Try All Splits — Algorithm Steps

Recursively try all positions for k-1 split points
Calculate sum of each subarray for current split
Track minimum of maximum sums across all valid splits

Visualization

Tap to expand

Step-by-Step Walkthrough

Split Point 1

Try every position for first split

Recursion

For each split, recursively find remaining splits

Track Minimum

Keep track of minimum largest sum found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int helper(int* nums, int n, int start, int splitsLeft) {
    if (splitsLeft == 1) {
        int sum = 0;
        for (int i = start; i < n; i++) {
            sum += nums[i];
        }
        return sum;
    }
    
    int minMaxSum = INT_MAX;
    int currentSum = 0;
    
    for (int i = start; i <= n - splitsLeft; i++) {
        currentSum += nums[i];
        int remainingMax = helper(nums, n, i + 1, splitsLeft - 1);
        int maxSum = (currentSum > remainingMax) ? currentSum : remainingMax;
        minMaxSum = (minMaxSum < maxSum) ? minMaxSum : maxSum;
    }
    
    return minMaxSum;
}

int solution(int* nums, int n, int k) {
    if (k == 1) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        return sum;
    }
    if (k >= n) {
        int maxVal = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] > maxVal) maxVal = nums[i];
        }
        return maxVal;
    }
    
    return helper(nums, n, 0, k);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, n, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

Each position can be a split point, leading to exponential combinations

✓ Linear Growth

Space Complexity

O(k)

Recursion stack depth up to k splits

✓ Linear Space

120.0K Views

High Frequency

~25 min Avg. Time

2.7K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Splits — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler