Interview Notes Search

This page uses the site's newer layout, so only the problem statement and the section outline survive in the public payload — open the original for the rest.

Binary Search

Split Array Largest Sum

hard

DESCRIPTION (inspired by Leetcode.com)

You are given an array nums and an integer k. nums represents the weights of n consecutive tasks while k represents the number of workers. Tasks are assigned to the workers as contiguous blocks.

Your goal is to distribute the work so that the heaviest workload (sum of task weights for any single worker) is as small as possible.

Return the minimum possible value of the maximum workload.

Example 1 :

Input:

nums = [4, 8, 15, 7, 3], k = 3

Output: 15

Explanation: One optimal split is [4, 8] (sum=12), [15] (sum=15), [7, 3] (sum=10). The maximum workload among workers is 15.

Example 2 :

Input:

nums = [6, 3, 9, 2, 1, 8], k = 2

Output: 18

Explanation: Split into [6, 3, 9] (sum=18) and [2, 1, 8] (sum=11). The heaviest workload is 18. Any other split with 2 groups results in a higher maximum.

Understanding the Problem

Key Observation: The Answer Has Bounds

The Binary Search Algorithm

The Feasibility Check (Helper Function)

Walkthrough

Visualization

Solution

When to Use Binary Search on Answer