How should I practice Split Array to Minimize the Largest Sum?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Nation with NaMo phone screen problems in FastPrep.

Is Split Array to Minimize the Largest Sum associated with Nation with NaMo?

FastPrep tags this as a Nation with NaMo phone screen coding practice problem when the problem catalog has that company and stage context.

Split Array to Minimize the Largest Sum

Nation with NaMo● HardFULLTIMEPHONE SCREEN

Problem statement

Given a nonnegative integer array nums and an integer k, split the whole array into exactly k nonempty contiguous subarrays. Every element belongs to exactly one subarray, and the order of elements stays unchanged.

For a split, find the sum of each subarray and take the largest of those sums. Return the smallest possible value of that largest sum.

Function

splitArrayLargestSum(nums: int[], k: int) → long

Examples

Example 1

nums = [7,2,5,10,8]k = 2return = 18

Split into [7,2,5] and [10,8], with sums 14 and 18. A limit below 18 would need at least three subarrays, so the minimum largest sum is 18.

Example 2

nums = [0,0,5,0]k = 3return = 5

The split [0], [0], [5,0] has largest sum 5. Every split contains the value 5 somewhere, so a smaller limit is impossible.

Constraints

1 <= nums.length <= 10000.
0 <= nums[i] <= 10^9.
1 <= k <= nums.length.