Split Array Largest Sum

HardBinary Searchbinary search on answer

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an array of non-negative integers nums and an integer k. Your task is to partition nums into exactly k non-empty **contiguous** subarrays. For any given partition, define its *cost* as the largest sum among the k subarrays. Among all the ways to split the array into k contiguous pieces, return the **minimum possible cost**. In other words, you want to break the array into k consecutive segments so that the heaviest segment (the one with the greatest total) is as light as possible, and you must return that heaviest segment's sum.

Examples

Input: nums = [7, 2, 5, 10, 8], k = 2
Output: 18
The best split is [7, 2, 5] and [10, 8], producing subarray sums of 14 and 18. The largest is 18, and no other 2-way split does better.
Input: nums = [1, 2, 3, 4, 5], k = 2
Output: 9
Splitting into [1, 2, 3] and [4, 5] gives sums 6 and 9. The maximum, 9, is the smallest achievable for two parts.
Input: nums = [1, 4, 4], k = 3
Output: 4
With k equal to the array length, every element forms its own subarray, so the answer is simply the maximum element, 4.

Constraints

  • `1 <= nums.length <= 1000`
  • `0 <= nums[i] <= 10^6`
  • `1 <= k <= nums.length`
  • Each of the `k` subarrays must be non-empty and contiguous.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More binary search on answer problems