Split Array Largest Sum

JavaView on GFG

Problem Overview

Binary search on the largest sum.

Intuition

Binary search on the largest sum. Check if we can split array into at most k subarrays where each sum <= mid.

Algorithm

1lo=max(nums), hi=sum(nums).
2Feasibility(mid): greedily fill subarrays, count splits. If splits <= k, feasible.
3Return minimum feasible mid.

Common Pitfalls

• Greedy: keep adding to current subarray until exceeds mid, then start new subarray. Count total subarrays needed.

Split Array Largest Sum.java

Java

// Approach: Binary search on the max sum. For each mid, greedily count splits; adjust range.
// Time: O(n log(sum)) Space: O(1)
class Solution {
    public int splitArray(int[] arr, int k) {
        int n = arr.length;
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            max = Math.max(max, arr[i]);
        }

        int ans = sum;

        int high = sum; // if k=0, then the maximized minimum sum = sum of array
        int low = max; // minimum sum will be maximum element of the array.

        // Applying Binary Search
        while (low <= high) {
            
            int mid = low + (high - low) / 2;
            if (isPossible(arr, k, mid)) {
                ans = mid;
                high = mid - 1;
            } else
                low = mid + 1;
        }
        return ans;
    }

    boolean isPossible(int[] arr, int k, int mid) {
        int count = 1;
        int n = arr.length;
        int sum = 0;

        for (int i = 0; i < n; i++) {
            sum += arr[i];
            if (sum > mid) {
                sum = arr[i];
                count++;
            }
        }

        if (count <= k)
            return true;

        return false;
    }
};

Was this solution helpful?