Last updated on October 25th, 2024 at 10:23 pm

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

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.

1. 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;
    }
};

2. 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;
    }
}

3. 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
}

4. 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