Split Array to Minimize the Largest Sum
Updated
Problem statement
You are given an integer array nums and an integer k. Split nums into exactly k non-empty subarrays that do not overlap and together cover the whole array, keeping the original order. A subarray is a run of neighboring elements.
Each subarray has a sum. Among all ways to split, find the one whose largest subarray sum is as small as possible, and return that largest sum.
Function
splitArray(nums: int[], k: int) → intExamples
Example 1
nums = [3,1,4,1,5,9,2]k = 3return = 11Split into [3,1,4], [1,5], [9,2]. The sums are 8, 6, and 11, so the largest is 11. To get 10 or less, 9 and 2 would have to be in different parts, which forces [3,1,4,1,5] (sum 14) or [5,9] (sum 14) into one part. So 11 is the best.
Example 2
nums = [2,2,2,2]k = 4return = 2With k equal to the length, every element is its own subarray, and the largest sum is 2.
Example 3
nums = [10,5,0,5]k = 2return = 10Split into [10] and [5,0,5]. Both sums are 10. The part with 10 can never be smaller than 10, so this is the best.
Constraints
1 <= nums.length <= 10000 <= nums[i] <= 10^61 <= k <= min(50, nums.length)
More Infosys Online Assessment questions
- Lowest Common Ancestor with a Changing RootOA · Seen Nov 2026
- Minimum Leaf Path Sum over All RootsOA · Seen Nov 2026
- Cherry PickupOA · Seen Nov 2026
- Lexicographically Smallest Grid Path with One Letter ChangeOA · Seen Nov 2026
- Minimum Cost to Supply Water with Wells and PipesOA · Seen Nov 2026
- Minimum Cost to Tile a Strip with Widths 1, 2, and 3OA · Seen Nov 2026
- Minimum Rounds to Complete All TasksOA · Seen Nov 2026
- Count Equal-Distinct Character PartitionsOA · Seen Oct 2026
- Maximum Alternating-Index Packet ValueOA · Seen Oct 2026
- Usable Water with Contaminated PillarsOA · Seen Oct 2026
Similar questions at other companies
- Split Array Largest SumAuxoAI · OA
- Split Array to Minimize the Largest SumNation with NaMo · PHONE SCREEN
- Minimize the Largest Part BeautyAdobe · PHONE SCREENAdobe interview questions
- Split Array Largest SumBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Maximum Non-Decreasing Array LengthVisa · OAVisa interview questions
- Get Minimum IncrementIBM · OAIBM interview questions
- Maximize Array Beauty After DeletionsPoint72 · OAPoint72 interview questions
- Data ReorganizationGoldman Sachs · OAGoldman Sachs interview questions
- Min Elements to Remove to Make Almost Sorted ArraySalesforce · OASalesforce interview questions
- Find Optimal LevelAmazon · OA