What is the time and space complexity of Split Array Largest Sum?

Time complexity: O(n log S) where S is sum of array. Space complexity: O(1).

Split Array Largest Sum

Hard

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Split Array Largest Sum

Approach

Binary search on the answer: the maximum subarray sum ranges from max(nums) to sum(nums). For each candidate, greedily partition the array — start a new split whenever the running sum exceeds the candidate. Check if k or fewer splits suffice.

Complexity Analysis

Time: O(n log S) where S is sum of array
Space: O(1)

Pattern

Binary Search on Answer

Why It Works

If we can split with max sum = X, then X+1 also works (monotonic). Binary search on the maximum subarray sum from max(nums) to sum(nums), checking if k or fewer splits suffice.

Updated Mar 2026