410. Split Array Largest Sum
Split Array Largest Sum (LeetCode 410) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the On Answer / Condition Function subpattern.
How to solve Split Array Largest Sum
Split Array Largest Sum is a Binary Search on Answer Space problem, part of Binary Search Patterns. Learn binary search on answer space for optimization problems like Koko eating bananas and capacity to ship packages.
Work towards the solution in these steps:
- Think about how you can use binary search to efficiently guess the answer instead of checking all possible sums.
- Consider the range for your binary search: what is the minimum and maximum possible largest subarray sum?
- Design a helper function that checks if it's possible to split the array into at most k subarrays without exceeding a given largest sum.
The reference solution runs in O(nlogs) time and O(1) space.
The Split Array Largest Sum solution and editorial walks through the full approach with reference code.
Problem statement
Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.
Return the minimized largest sum of the split.
A subarray is a contiguous part of the array.
Example 1:
Input: nums = [7,2,5,10,8], k = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
Example 2:
Input: nums = [1,2,3,4,5], k = 2 Output: 9 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.
Constraints:
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 106
- 1 <= k <= min(50, nums.length)
Topics and companies
Topics: Array, Binary Search, Dynamic Programming, Greedy, Prefix Sum.
Reported in interviews at Amazon, Google.
How to practise Split Array Largest Sum on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogs) time and O(1) space.
Open Split Array Largest Sum in the code editor, or read the Split Array Largest Sum editorial for a worked solution with its approach and complexity analysis.
Where Split Array Largest Sum sits in the DSA pattern sheet
- Binary Search Patterns pattern guide
- On Answer / Condition Function subpattern
- The full DSA patterns sheet
Problems related to Split Array Largest Sum
Other problems that use the same On Answer / Condition Function and Binary Search Patterns techniques:
- Capacity To Ship Packages Within D Days — Medium, same subpattern
- Koko Eating Bananas — Medium, same subpattern
- Maximum Candies Allocated to K Children — Medium, same subpattern
- Minimized Maximum of Products Distributed to Any Store — Medium, same subpattern
- Minimize Max Distance to Gas Station — Hard, same subpattern
- Minimum Limit of Balls in a Bag — Medium, same subpattern
Split Array Largest Sum FAQ
What is the LeetCode number of Split Array Largest Sum?
Split Array Largest Sum is LeetCode problem 410, rated Hard.
What pattern is used to solve Split Array Largest Sum?
Split Array Largest Sum is a Binary Search on Answer Space problem. It belongs to the Binary Search Patterns pattern, in the On Answer / Condition Function subpattern.
What is the time complexity of Split Array Largest Sum?
The reference solution runs in O(nlogs) time and O(1) space.
Which companies ask Split Array Largest Sum?
Split Array Largest Sum has been reported in interviews at Amazon, Google.