Split Array Largest Sum LeetCode Solution

Here, We see Split Array Largest Sum LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Split Array Largest Sum LeetCode Solution

Split Array Largest Sum LeetCode Solution

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.

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.

Split Array Largest Sum LeetCode Solution 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;
    }
};Code language: PHP (php)

Split Array Largest Sum LeetCode Solution 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;
    }
}Code language: JavaScript (javascript)

Split Array Largest Sum LeetCode Solution 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
}Code language: JavaScript (javascript)

Split Array Largest Sum Solution 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  
Scroll to Top