410. Split Array Largest Sum

[TODO] Implement prefixSum + binary search in canSplit() method

二刷 07/2022

Version #1 二分答案

注意一个地方就是start不能小于nums里面最大的那个数

Time O(NlogSum) - N is the length of the nums array

Space O(1)

Runtime: 1 ms, faster than 86.51% of Java online submissions for Split Array Largest Sum.

Memory Usage: 42.3 MB, less than 18.28% of Java online submissions for Split Array Largest Sum.

class Solution {

    public int splitArray(int[] nums, int m) {

        int start = 0, end = 0;

        for (int num : nums) {

            end += num;

            start = Math.max(start, num);

        }

        // find the smallest number that can split

        while (start < end) {

            int mid = start + (end - start) / 2;

            if (canSplit(nums, m, mid)) {

                end = mid;

            } else {

                start = mid + 1;

            }

        }

        return start;

    }

    private boolean canSplit(int[] nums, int m, int target) {

        int sum = 0;

        for (int i = 0; i < nums.length; i++) {

            if (sum + nums[i] > target) {

                m--;

                sum = nums[i];

            } else {

                sum += nums[i];

            }

            if (m <= 0) {

                return false;

            }

        }

        return true;

    }

}

一刷
Version #1 二分答案
https://leetcode.com/problems/split-array-largest-sum/discuss/89819/C++-Fast-Very-clear-explanation-Clean-Code-Solution-with-Greedy-Algorithm-and-Binary-Search
Time O(m log(2^31  - 1))
Space O(1)
99.89 %

[1,2147483647] 2


class Solution {
    public int splitArray(int[] nums, int m) {
        // Binary Search Answer
        // Given a max sum x, check if we ensure that every subarray sum is less than x, how many splits do we need
        // If number of split is less than m, then it is an valid answer
        // We want to find the minimum x
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int end = (1 << 31) - 1;
        int start = 0;
        // F F F T
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (canSplit(nums, mid, m)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
    // x = 7, m = 2
    // [7,2,5,10,8]
    // O(m)
    private boolean canSplit(int[] nums, int x, int m) {
        m--;
        // Each subarray sum can't exceed x
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > x) {
                return false;
            }
            if (sum + nums[i] > x) {
                m--;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
            if (m < 0) {
                return false;
            }
        }
        return true;
    }
}