What is the brute force approach and complexity for Split Array Largest Sum?

Try limit max, max+1, … and return the first that needs at most k parts with time complexity O((S − M) · N) and space complexity O(1).

What is the optimal approach and complexity for Split Array Largest Sum?

Binary search the limit in [max, sum]; check with a greedy part count ≤ k with optimal time complexity O(N log S) and space complexity O(1).

How do you identify the pattern for Split Array Largest Sum?

Look for key signals in the prompt: "minimise the largest sum" indicates "Minimise the maximum" → guess the maximum, check if it's possible → binary search on the answer.; "k non-empty contiguous parts" indicates Order is fixed, only the cut points are chosen → greedy left-to-right part count for a fixed limit.; "a bigger limit is always easier" indicates If X is reachable, X + 1 is reachable → monotonic check, ✗✗✗✓✓✓..

Split Array Largest Sum

Hard·LeetCode #410 Pro OnlyInterview-Level

LeetCode

Problem Statement

You are given an array nums and a number k. Cut the array into exactly k non-empty, contiguous parts. Every number stays in its place; you only choose where to cut.

Each part has a sum. Look at the largest of those k sums. Choose the cuts so that this largest sum is as small as possible, and return it.

Input

An integer array nums and an integer k.

Output

One integer: the smallest possible value of the largest part sum.

Example 1

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

Output: 18

Cut into [7, 2, 5] and [10, 8]. The sums are 14 and 18, so the largest is 18. No other cut does better.

Example 2

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

Output: 9

Cut into [1, 2, 3] and [4, 5]. The sums are 6 and 9.

Constraints

• 1 ≤ nums.length ≤ 1000
• 0 ≤ nums[i] ≤ 10^6
• 1 ≤ k ≤ min(50, nums.length)
• The total sum can reach 10^9, so lo + hi can pass the int limit.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“minimise the largest sum”

→ "Minimise the maximum" → guess the maximum, check if it's possible → binary search on the answer.

“k non-empty contiguous parts”

→ Order is fixed, only the cut points are chosen → greedy left-to-right part count for a fixed limit.

“a bigger limit is always easier”

→ If X is reachable, X + 1 is reachable → monotonic check, ✗✗✗✓✓✓.

Approach Complexity Ladder

Brute Force — try every limit from max upwardO((S − M) · N)O(1)

Try limit max, max+1, … and return the first that needs at most k parts

Better — DP over cut pointsO(k · N²)O(k · N)

dp[j][i] = best largest sum for the first i numbers in j parts; try every last cut

Optimal — binary search on the largest sumO(N log S)O(1)

Binary search the limit in [max, sum]; check with a greedy part count ≤ k

Brute Force Intuition

Turn the question around: for a limit X, can we cut the array so that every part sums to at most X, using at most k parts? Count the parts greedily. Then try X = max, max + 1, max + 2, … and return the first limit that needs at most k parts.

Recognition rule for this sub-pattern:

"Minimum capacity / speed / days such that it is possible." Guess an answer, check feasibility greedily, shrink the range.

Remember this · Binary Search

Trigger

Sorted data, "minimum X such that…", "maximum X such that…", rotated arrays, answers that are monotonic (if X works, X+1 also works).

Think

Is there a yes/no question whose answers look like NNNNYYYY? Then binary search for the first Y.

Key question

What is my check function, and is it monotonic?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Order Book Price Level Matching

std::lower_bound lookup in sorted price ticks for limit orders.

Explore Track

C++ Internals

CPU Branch Prediction & Cache Efficiency

Branch mispredictions in binary search and branchless mid-point arithmetic.

Explore Track

Minimum Number of Days to Make m Bouquets