algoadvance

Leetcode 3046. Split the Array

Problem Statement

You are given an integer array nums and an integer k. Partition the array into k adjacent (non-empty) subarrays, where the largest sum of these subarrays is minimized.

Return the minimized largest sum of the partition.

Example:

  1. Input: nums = [7,2,5,10,8], k = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays:
    • [7,2,5] and [10,8], with sums 14 and 18 respectively.
    • [7,2,5,10] and [8], with sums 24 and 8 respectively.
    • [7,2], and [5,10,8], with sums 9 and 23 respectively.
    • [7], and [2,5,10,8], with sums 7 and 25 respectively. The minimized largest sum among these is 18.

Constraints:

Clarifying Questions

  1. Should the subarrays be contiguous?
    • Yes, they should be adjacent or contiguous subarrays.
  2. Can the k subarrays contain different lengths?
    • Yes, we only care about dividing them into k adjacent subarrays.
  3. Is there a specific range for k in relation to the length of nums?
    • 1 <= k <= min(50, nums.length), so it will always be valid to partition in a meaningful way.

Strategy

  1. Binary Search for the Solution Space: The largest sum we aim to minimize will lie between the maximum element (max(nums)) and the sum of all elements (sum(nums)).
  2. Greedy Subarray Division: For a middle value in our binary search space, check if it can be a valid largest sum by trying to divide the array into k parts. If you can partition nums within this limit, the value is valid.

Code

public class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0;
        int right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

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

        for (int num : nums) {
            if (currentSum + num > maxSum) {
                subarrays++;
                currentSum = num;
                if (subarrays > k) {
                    return false;
                }
            } else {
                currentSum += num;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {7, 2, 5, 10, 8};
        int k = 2;
        System.out.println(sol.splitArray(nums, k)); // Outputs: 18
    }
}

Time Complexity

  1. Binary Search: Between max(nums) and sum(nums) gives a time complexity of O(log(sum(nums) - max(nums)))
  2. Partition Check: Each check takes O(n) where n is the length of nums.

Thus, the overall time complexity is O(n * log(sum(nums) - max(nums))). This is efficient given the constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI