Split Array Largest Sum

                                            
class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int left = *max_element(nums.begin(), nums.end());
        int right = accumulate(nums.begin(), nums.end(), 0);
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = 1;
            int sum = 0;
            
            for (int num : nums) {
                sum += num;
                if (sum > mid) {
                    sum = num;
                    count++;
                }
            }
            
            if (count > k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
};

                                            
class Solution {
    public int splitArray(int[] nums, int k) {
        int start = 0;
        int end = 0;
        for (int num : nums) {
            start = Math.max(start, num);
            end += num;
        }
        
        while (start < end) {
            int mid = start + (end - start) / 2;
            int sum = 0;
            int parts = 1;
            for (int num : nums) {
                if (sum + num > mid) {
                    parts++;
                    sum = num;
                } else {
                    sum += num;
                }
            }
            if (parts > k) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        
        return start;
    }
}

                                            
class Solution(object):
    def splitArray(self, nums, k):
        def is_valid(mid):
            count = 1
            total = 0
            for num in nums:
                total += num
                if total > mid:
                    total = num
                    count += 1
            return count <= k
            
        left = max(nums)
        right = sum(nums)
        
        while left < right:
            mid = (left + right) // 2
            if is_valid(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

                                            
int splitArray(int* nums, int numsSize, int k) {
    int left = 0, right = 0;
    for (int i = 0; i < numsSize; i++) {
        left = fmax(left, nums[i]);
        right += nums[i];
    }
    while (left < right) {
        int mid = left + (right - left) / 2;
        int sum = 0, count = 1;
        for (int i = 0; i < numsSize; i++) {
            if (sum + nums[i] > mid) {
                count++;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
        }
        if (count > k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

                                            
public class Solution {
    public int SplitArray(int[] nums, int k) {
        int left = 0, right = 0;
        foreach (int num in nums) {
            left = Math.Max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            int sum = 0;
            int count = 1;
            foreach (int num in nums) {
                if (sum + num > mid) {
                    count++;
                    sum = num;
                } else {
                    sum += num;
                }
            }
            if (count <= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

                                            
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var splitArray = function(nums, k) {
    let left = Math.max(...nums);
    let right = nums.reduce((acc, curr) => acc + curr, 0);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let count = 0;
        let sum = 0;
        
        for (let num of nums) {
            sum += num;
            if (sum > mid) {
                count++;
                sum = num;
            }
        }
        
        count++;
        
        if (count > k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
};

                                            
function splitArray(nums: number[], k: number): number {
    let left = Math.max(...nums);
    let right = nums.reduce((acc, curr) => acc + curr, 0);
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        let sum = 0;
        let count = 1;
        
        for (let num of nums) {
            sum += num;
            if (sum > mid) {
                sum = num;
                count++;
            }
        }
        
        if (count > k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer
     */
    function splitArray($nums, $k) {
        $left = max($nums);
        $right = array_sum($nums);
        
        while ($left < $right) {
            $mid = $left + intval(($right - $left) / 2);
            if ($this->validSplit($nums, $mid, $k)) {
                $right = $mid;
            } else {
                $left = $mid + 1;
            }
        }
        return $left;
    }
    
    function validSplit($nums, $max, $k) {
        $count = 1;
        $sum = 0;
        foreach ($nums as $num) {
            $sum += $num;
            if ($sum > $max) {
                $count++;
                $sum = $num;
                if ($count > $k) {
                    return false;
                }
            }
        }
        return true;
    }
}

                                            
class Solution {
    func splitArray(_ nums: [Int], _ k: Int) -> Int {
        var left = nums.max() ?? 0
        var right = nums.reduce(0, +)
        
        while left < right {
            let mid = left + (right - left) / 2
            if isPossible(nums, k, mid) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        
        return left
    }
    
    func isPossible(_ nums: [Int], _ k: Int, _ target: Int) -> Bool {
        var count = 1
        var sum = 0
        
        for num in nums {
            sum += num
            if sum > target {
                count += 1
                sum = num
            }
        }
        
        return count <= k
    }
}

                                            
class Solution {
    fun splitArray(nums: IntArray, k: Int): Int {
        var left = nums.maxOrNull() ?: 0
        var right = nums.sum()
        while (left < right) {
            val mid = left + (right - left) / 2
            if (isValid(nums, k, mid)) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }

    fun isValid(nums: IntArray, k: Int, target: Int): Boolean {
        var count = 1
        var sum = 0
        for (num in nums) {
            sum += num
            if (sum > target) {
                count++
                sum = num
            }
        }
        return count <= k
    }
}

                                            
class Solution {
  int splitArray(List<int> nums, int k) {
    int left = 0;
    int right = 0;
    
    for (int num in nums) {
      left = left > num ? left : num;
      right += num;
    }
    
    while (left < right) {
      int mid = left + (right - left) ~/ 2;
      int count = 1;
      int sum = 0;
      
      for (int num in nums) {
        if (sum + num > mid) {
          count++;
          sum = num;
        } else {
          sum += num;
        }
      }
      
      if (count > k) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    
    return left;
  }
}

                                            
func splitArray(nums []int, k int) int {
    left := 0
    right := 0
    
    for _, num := range nums {
        right += num
        if num > left {
            left = num
        }
    }
    
    for left < right {
        mid := left + (right - left) / 2
        if isValid(nums, k, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return left
}

func isValid(nums []int, k, target int) bool {
    count := 1
    sum := 0
    
    for i := 0; i < len(nums); i++ {
        sum += nums[i]
        if sum > target {
            count++
            sum = nums[i]
        }
    }
    
    return count <= k
}

                                            
# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def split_array(nums, k)
    def valid?(nums, mid, k)
        count = 1
        total = 0
        nums.each do |num|
            total += num
            if total > mid
                total = num
                count += 1
                return false if count > k
            end
        end
        true
    end
    
    left = nums.max
    right = nums.sum
    while left < right
        mid = left + (right - left) / 2
        if valid?(nums, mid, k)
            right = mid
        else
            left = mid + 1
        end
    end
    left
end

                                            
object Solution {
    def splitArray(nums: Array[Int], k: Int): Int = {
        def isValid(mid: Long, nums: Array[Int], k: Int): Boolean = {
            var count = 1
            var sum = 0
            for (num <- nums) {
                sum += num
                if (sum > mid) {
                    count += 1
                    sum = num
                }
            }
            count <= k
        }

        var left = nums.max.toLong
        var right = nums.sum.toLong
        while (left < right) {
            val mid = left + (right - left) / 2
            if (isValid(mid, nums, k)) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        left.toInt
    }
}

                                            
impl Solution {
    pub fn split_array(nums: Vec<i32>, k: i32) -> i32 {
        let mut left = 0;
        let mut right = 0;
        let mut result = 0;
        
        for num in &nums {
            left = left.max(*num);
            right += num;
        }
        
        while left <= right {
            let mid = left + (right - left) / 2;
            if Self::valid_split(&nums, k, mid) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        result
    }
    
    fn valid_split(nums: &Vec<i32>, k: i32, target: i32) -> bool {
        let mut sum = 0;
        let mut count = 1;
        
        for &num in nums {
            sum += num;
            if sum > target {
                sum = num;
                count += 1;
                if count > k {
                    return false;
                }
            }
        }
        
        true
    }
}

To solve this coding challenge, we need to determine the minimum largest sum among all possible splits of the array such that the array is split into exactly

k

subarrays. This problem can be approached using binary search combined with a greedy checking function.

Explanation

Given an array

nums

and an integer

k

, we aim to split the array into

k

subarrays in such a way that the largest sum among these subarrays is minimized. The binary search will help us identify the minimum possible value of the largest sum. Here is why binary search works well in this scenario:

Binary Search Setup :

Lower Bound (left) : This is the maximum element in the array, because in any valid split, the largest sum must be at least as large as the largest individual element (i.e.,
max(nums)

).
Upper Bound (right) : This is the sum of all elements in the array, because in the worst possible split (i.e., not splitting at all), the largest sum is the entire sum of the array (
sum(nums)

).

Greedy Checking Function :

For a possible solution
mid

(the midpoint of
left

and
right

in our binary search), we need to check if it is possible to split the array into
k

or fewer subarrays such that no subarray has a sum greater than
mid

.
This is performed by iterating through the array and maintaining a running total of the current subarray sum. If adding the current element would exceed
mid

, we start a new subarray and increment our subarray count.

Binary Search Process :

Adjust the bounds based on the feasibility of the current midpoint
mid

using the greedy checking function.
If
mid

is feasible, we adjust the upper bound (
right

) to
mid

.
If not, adjust the lower bound (
left

) to
mid + 1

.

In the end, the value of

left

will be the minimum largest sum possible for the valid split.

Detailed Steps in Pseudocode

                                            
# Function to determine if a particular maximum subarray sum is valid for the given k splits
function is_valid(mid, nums, k):
    # Start with one subarray
    subarray_count = 1
    current_sum = 0
    
    # Iterate through each number in nums
    for number in nums:
        current_sum += number
        
        # If the current sum exceeds the mid value, start a new subarray
        if current_sum > mid:
            current_sum = number
            subarray_count += 1
        
        # If the number of subarrays exceeds k, return False
        if subarray_count > k:
            return False
    
    # If we are within the limit of k subarrays, return True
    return True

# Main function to find the minimized largest sum
function splitArray(nums, k):
    # Initial bounds for the binary search
    left = maximum_number_in(nums)
    right = sum_of(nums)
    
    # Binary search for the optimal largest sum
    while left < right:
        mid = (left + right) // 2
        
        # Check if current midpoint is a valid maximum sum for the given k splits
        if is_valid(mid, nums, k):
            right = mid  # If valid, move the upper bound to mid
        else:
            left = mid + 1  # Otherwise, move the lower bound to mid + 1
    
    # Return the lower bound which is the minimized largest sum
    return left

Commentary on the Pseudocode

Function
is_valid

:

This function checks if a given
mid

value can be used to split the array into no more than
k

subarrays, where each subarray has a sum not exceeding
mid

.
It increments the subarray count every time the current sum exceeds
mid

and starts a new subarray with the current number.

Function
splitArray

:

Initializes
left

to the maximum value in the array and
right

to the sum of the array, covering the worst and best case scenarios.
Uses binary search to narrow down the possible minimal largest sum by adjusting the bounds based on the validity check at each midpoint
mid

.

This method ensures that we efficiently find the minimized largest sum for splitting the array into exactly

k

subarrays.