Clear Explanation: 8ms Binary Search Java


  • 114
    D
    1. The answer is between maximum value of input array numbers and sum of those numbers.
    2. Use binary search to approach the correct answer. We have l = max number of array; r = sum of all numbers in the array;Every time we do mid = (l + r) / 2;
    3. Use greedy to narrow down left and right boundaries in binary search.
      3.1 Cut the array from left.
      3.2 Try our best to make sure that the sum of numbers between each two cuts (inclusive) is large enough but still less than mid.
      3.3 We'll end up with two results: either we can divide the array into more than m subarrays or we cannot.
      If we can, it means that the mid value we pick is too small because we've already tried our best to make sure each part holds as many non-negative numbers as we can but we still have numbers left. So, it is impossible to cut the array into m parts and make sure each parts is no larger than mid. We should increase m. This leads to l = mid + 1;
      If we can't, it is either we successfully divide the array into m parts and the sum of each part is less than mid, or we used up all numbers before we reach m. Both of them mean that we should lower mid because we need to find the minimum one. This leads to r = mid - 1;
    public class Solution {
        public int splitArray(int[] nums, int m) {
            int max = 0; long sum = 0;
            for (int num : nums) {
                max = Math.max(num, max);
                sum += num;
            }
            if (m == 1) return (int)sum;
            //binary search
            long l = max; long r = sum;
            while (l <= r) {
                long mid = (l + r)/ 2;
                if (valid(mid, nums, m)) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            return (int)l;
        }
        public boolean valid(long target, int[] nums, int m) {
            int count = 1;
            long total = 0;
            for(int num : nums) {
                total += num;
                if (total > target) {
                    total = num;
                    count++;
                    if (count > m) {
                        return false;
                    }
                }
            }
            return true;
        }
    }
    
    • list item

  • 1

    @dax1ng
    Brilliant Solution
    but Its giving TLE unless you replace mid by ( l + r )/2


  • 0
    D

    @findsaumyahere Thanks, u r right


  • 13

    Nice solution @dax1ng !
    Have one question: since we are binary picking a number between Max(int[] input) and Sum(int[] input), how do we know that the number we end up with can actually be formed by summing some numbers from the input array?


  • 0
    N

    @dax1ng I don't think the long array preSum is doing anything. Thanks for the solution, this is really cool!


  • 0
    Y

    Typo:

    mid = l + 1;
    

    should be

    l = mid + 1;
    

  • 0
    P

    This was a real tricky solution. Took me a while to understand it. Great Job !


  • 0
    Y

    @piyush121 @dax1ng I think I understand what is the solution is doing there, but I don't understand why the process start splitting it from the left, if the starting point say from the right, wonder if the valid is going to return the same value, Do you have some hint?
    Say it in another way why start split the array from the left will guarantee that m is too small or too big


  • 0
    P

    @yliang I think going from left to right is a natural way to approach a problem. But I don't think going from right to left will create any problem in this case.


  • 0
    C

    @yliang If you can split the array into more than m subarrays (each does its best to sum up to target), you can also do so from right. Both make it invalid. Because for those numbers you've scanned from left that form those m + 1 sub-arrays will also need to be split when you go from right.


  • 3
    C

    The solution is brilliant! One question: since the answer will always have true returned in valid(). What if we do r = mid - 1 and miss the correct answer?


  • 1

    @dax1ng
    Great solution! But it is a quite tricky one. Here is my TLE solutions:

    public class Solution {
        Map<String, Integer> map;
        int[][] sumMap;
        public int splitArray(int[] nums, int m) {
            map = new HashMap<String, Integer>();
            sumMap = new int[nums.length][nums.length];
            
            for(int i = 0; i < nums.length; i ++){
                int sum = 0; 
                for(int j = i; j < nums.length; j++){
                    sum += nums[j];
                    sumMap[i][j] = sum;
                }
            }
            
            return helper(nums, m, 0, nums.length - 1);
        }
        
        public int helper(int[] nums, int m, int low, int high){
            String key = String.format("%d#%d#%d", low, high, m);
            
            if(m == 1){
                int sum = sumMap[low][high];
                map.put(key, sum);
                return sum;
            }
            
            int max = Integer.MAX_VALUE; 
            
            if(map.containsKey(key)){
                return map.get(key);
            }
            
            for(int i = low; i <= high - m + 1; i++){
                int tmp = Math.max(sumMap[low][i], helper(nums, m - 1, i + 1, high));
                max = Math.min(tmp, max);
            }
            
            map.put(key, max);
            return max;
            
        }
    }
    

    Could you please compare the time complexity of Both binary Search solutions and mine. Thank you!


  • 0
    7

    Why we return the sum when m == 1? I think if we only allow to have 1 subarray, then the answer is the max?..


  • 0
    D

    @7734sss Write an algorithm to minimize the largest sum among these m subarrays.


  • 0
    C

    @7734sss

    Here 'm' is number of sub arrays original array needs to be split into. When m=1, it means original array need not be split at all. Hence for m=1 sum represents the answer. 'm' does not indicate size of the resultant sub-arrays, which I think is the cause of your confusion.


  • 0
    E

    Great solution!
    Thanks :)


  • 0
    Q
    This post is deleted!

  • 0
    D

    What's the time complexity? Is O(log(max - min) * n)?


  • 0

    i think we can calculate the mid without the declaration of long,
    just use int left and int right
    and let mid = left+(right-left)/2 to avoid overflow


  • 0
    C

    @dax1ng amazing solution. After looking at your code its very simple to visualize the problem!


Log in to reply
 

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