Last updated on March 1st, 2025 at 09:23 pm
Here, we see a Split Array Largest Sum LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Companies
Baidu, Facebook
Level of Question
Hard
Split Array Largest Sum LeetCode Solution
Table of Contents
1. 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.
2. Coding Pattern Used in Solution
The coding pattern used in this code is Modified Binary Search. The problem involves finding the minimum largest sum of subarrays when splitting an array into k subarrays. The solution uses binary search to efficiently narrow down the range of possible answers, combined with a helper function or logic to validate whether a given mid-point value is feasible.
3. Code Implementation in Different Languages
3.1 Split Array Largest Sum C++
class Solution {
public:
int splitArray(vector<int>& nums, int k) {
int l=0,r=0,n=nums.size();
for(int i=0;i<n;++i) l=max(l,nums[i]), r+=nums[i];
int mid=0,ans=0;
while(l<=r){
mid=(l+r)/2;
int count=0,tempsum=0;
for(int i=0;i<n;++i){
if(tempsum+nums[i]<=mid) tempsum+=nums[i];
else count++,tempsum=nums[i];
}
count++;
if(count<=k) r=mid-1, ans=mid;
else l=mid+1;
}
return ans;
}
};
3.2 Split Array Largest Sum Java
class Solution {
int[] nums;
public int splitArray(int[] nums, int k) {
this.nums = nums;
int low = 0, high = 0, min = Integer.MAX_VALUE;
for(int i=0;i<nums.length;i++){
low = Math.max(low, nums[i]);
high += nums[i];
}
while(low <= high) {
int mid = (low + high) / 2;
if(required_no_of_chunks(mid, k)){
min = Math.min(min, mid);
high = mid - 1;
}
else low = mid + 1;
}
return min;
}
private boolean required_no_of_chunks(int mid, int k){
int chunks = 0, i=0;
while(i < nums.length){
int val = 0;
while(i < nums.length && nums[i] + val <= mid) val += nums[i++];
chunks++;
}
return chunks <= k;
}
}
3.3 Split Array Largest Sum JavaScript
var splitArray = function(nums, k) {
let n=nums.length;
let low=Math.max(...nums)
let high=nums.reduce((acc,curr)=>{
return acc+curr
},0)
while(low<=high)
{
let mid=Math.floor((low+high)/2)
let sum=LargestSum(nums,mid)
if(sum>k)
{
low=mid+1
}
else
{
high=mid-1
}
}
return low
};
const LargestSum=(nums,mid)=>{
let n=nums.length;
let count=1;
let array=0;
for(let i=0;i<n;i++)
{
if(array+nums[i]<=mid)
{
array+=nums[i]
}
else
{
count++;
array=nums[i]
}
}
return count
}
3.4 Split Array Largest Sum Python
class Solution(object):
def splitArray(self, nums, k):
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo+hi)//2
tot, cnt = 0, 1
for num in nums:
if tot+num<=mid:
tot += num
else:
tot = num
cnt += 1
if cnt>k: lo = mid+1
else: hi = mid
return hi
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n * log(S)) | O(1) |
| Java | O(n * log(S)) | O(1) |
| JavaScript | O(n * log(S)) | O(1) |
| Python | O(n * log(S)) | O(1) |
where S is the range of sums (max to total).