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 {
        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;
            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;
                    left = mid+1;
            return left;

  • 0

    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.