Binary Search C++ Solution


  • 9

    Obviously, the final result is in the interval [left, right] (where left is the maximal number in the array, right is sum of all numbers).
    So, what we need to do is to find out the first element in [left, right], which exactly we cannot split the array into m subarrays whose sum is no greater than that element. Then its previous one is the final result. The progress is much similar to lower_bound in C++.

    class Solution {
    public:
        using ll = long long;
    
        bool canSplit(vector<int>& nums, int m, ll sum) {
            int c = 1;
            ll s = 0;
            for (auto& num : nums) {
                s += num;
                if (s > sum) {
                    s = num;
                    ++c;
                }
            }
            return c <= m;
        }
    
        int splitArray(vector<int>& nums, int m) {
            ll left = 0, right = 0;
            for (auto& num : nums) {
                left = max(left, (ll)num);
                right += num;
            }
            while (left <= right) {
                ll mid = left + (right-left)/2;
                if (canSplit(nums, m, mid))
                    right = mid-1;
                else
                    left = mid+1;
            }
            return left;
        }
    };
    

  • 0
    F

    Can you explain more about your code?


  • 0

    @fming Yes, I should like to have given out more explanation, but others later on posted a topic with very detailed explanation about this binary search solution, so just take a look at that :)


Log in to reply
 

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