Java easy binary search solution 8ms


  • 30
    Z
    1. Given a result, it is easy to test whether it is valid or not.
    2. The max of the result is the sum of the input nums.
    3. The min of the result is the max num of the input nums.
      Given the 3 conditions above we can do a binary search. (need to deal with overflow)
    public class Solution {
        public int splitArray(int[] nums, int m) {
            long sum = 0;
            int max = 0;
            for(int num: nums){
                max = Math.max(max, num);
                sum += num;
            }
            return (int)binary(nums, m, sum, max);
        }
        
        private long binary(int[] nums, int m, long high, long low){
            long mid = 0;
            while(low < high){
                mid = (high + low)/2;
                if(valid(nums, m, mid)){
                    //System.out.println(mid);
                    high = mid;
                }else{
                    low = mid + 1;
                }
            }
            return high;
        }
        
        private boolean valid(int[] nums, int m, long max){
            int cur = 0;
            int count = 1;
            for(int num: nums){
                cur += num;
                if(cur > max){
                    cur = num;
                    count++;
                    if(count > m){
                        return false;
                    }
                }
            }
            return true;
        }
    }
    

  • 2
    T

    Hi @zrythpzhl ,
    looks like this is good solution, but I have one question about that. how did you make sure there result return from binary search function is reachable?

    such as , you are returning 18 from function binary, but how did you make sure 18 is a sum of subarray ?

    i'm not sure if it is possible : every sum of subarray is small than 18 but NO equals.

    Thanks
    Huang Tang


  • 0
    P

    @tangalai If none sum of the subarrays is 18, then there exists a sum that is the largest sum of these subarrays, say, 17. The binary search returns the FIRST one that is feasible, so 17 will be returned instead.


  • 0
    T

    @peterfyj oh, yes, I got that, thanks


  • 0
    This post is deleted!

  • 3
    N

    " 3. The min of the result is the max num of the input nums. "

    Say there is a test case [1,1, ... ,1] lots of 1s, and m=2. The min result in your code is 1, but it can be improved if you change the min result to (sum of input nums)/m.

    It can be better if you change
    return (int)binary(nums, m, sum, max);
    to
    return (int)binary(nums, m, sum, Math.max(max,sum/m));
    in case of that crazy test case.


  • 1
    T

    @niwota Should be Math.max(max, Math.ceil(sum/m)) in case when sum cannot be exactly divided by m.


  • 1
    X

    Great idea! Recursive solution:

    public class Solution {
        public int splitArray(int[] nums, int m) {
            long max = 0, min = 0;
            for(int num: nums) {
                max += num;
                min = Math.max(num, min);
            }
            return (int) binarySearch(nums, min, max, m);
        }
        private long binarySearch(int[] nums, long min, long max, int m) {
            if(min == max) return min;
            long mid = (max - min) / 2 + min;
            if(isValid(nums, mid, m)) {
                if(mid == min || !isValid(nums, mid - 1, m)) return mid;
                else return binarySearch(nums, min, mid - 1, m);
            } else return binarySearch(nums, mid + 1, max, m);
        }
        private boolean isValid(int[] nums, long sum, int m) {
            long curSum = 0;
            for(int num: nums) {
                if(curSum + num <= sum) {
                    curSum += num;
                } else {
                    if((--m) == 0) return false;
                    curSum = num;
                }
            }
            return curSum <= sum;
        }
    }
    

  • 0
    H

    So the runtime complexity is O(nlog(sum-max))?


  • 0
    E

    The code of valid() is not correct for one case. If there is a big value, it will be counted as a single group. Try:
    nums: {1, 100, 3}
    m = 3, max = 10,
    valid(nums, 3, 10) will return true, saying 10 is a valid max value of three groups {1}, {100}, {3}, which is not correct.


  • 0
    H

    @EricZ Actually for your example, max won't run to 10. The range of max is 100 to 104


  • 0
    O

    @tangalai This is a very good question though. Thanks.


  • 0
    L

    @zrythpzhl Thanks for posting your solution.. I have a question on 'valid' method.

    Shouldn't we check for 'count==m' (i.e exactly m Split) at the last 'return' statement.
    Otherwise we will return true even if the split is < m. is that fine ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.