← Back to Index

📚 Split Array Largest Sum – Java Cheat Sheet

📌 What Is It?

The Split Array Largest Sum problem involves splitting an array into m non-empty continuous subarrays such that the largest sum among these subarrays is minimized. The goal is to find this minimized largest sum using binary search.

🧱 Pattern Template

class Solution {
    public int splitArray(int[] nums, int m) {
        int left = 0, right = 0;

        for (int num : nums) {
            left = Math.max(left, num); // Minimum possible largest sum
            right += num; // Maximum possible largest sum
        }

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (canSplit(nums, m, mid)) {
                right = mid; // Try a smaller largest sum
            } else {
                left = mid + 1; // Try a larger largest sum
            }
        }

        return left;
    }

    private boolean canSplit(int[] nums, int m, int maxSum) {
        int currentSum = 0, splits = 1;

        for (int num : nums) {
            if (currentSum + num > maxSum) {
                splits++;
                currentSum = num;

                if (splits > m) {
                    return false;
                }
            } else {
                currentSum += num;
            }
        }

        return true;
    }
}

📊 Time Complexity

• Binary Search: O(log(S)), where S is the sum of the array.
• Validation: O(N), where N is the length of the array.
• Overall Complexity: O(N log(S)).

✅ Use Cases

• Splitting arrays into subarrays with minimized largest sums
• Applications in load balancing and resource allocation

📘 Common LeetCode Problems

• 410. Split Array Largest Sum [Hard] Binary Search

🧪 Example: Split Array Largest Sum

Input: nums = [7,2,5,10,8], m = 2
Output: 18

Explanation:
- Split the array into [7,2,5] and [10,8].
- The largest sum among these subarrays is 18, which is minimized.

▶️ View Animation

💡 Pro Tips

• Use binary search to efficiently find the minimized largest sum.
• Edge cases: single-element arrays, large values of m, or when m equals the array length.
• Precompute the sum of the array to set the binary search bounds.