Last updated on July 21st, 2024 at 03:43 am

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

Topics

Binary Search, Dynamic Programming

Companies

Baidu, Facebook

Level of Question

Hard

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