LeetCode 410: Split Array Largest Sum

Question

I'm posting my code for a LeetCode problem copied here. If you would like to review, please do so. Thank you for your time!

Problem

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:

If n is the length of array, assume the following constraints are satisfied:

$$ 1 \le n \le 1000 \\ 1 \le m \le \min(50, n) $$

Example:

Input: nums = [7,2,5,10,8] m = 2

Output: 18

Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

Code

#include <vector>


class Solution {
public: 
    static int splitArray(const std::vector<int> &nums, const int m) {
        size_t lo = 0;
        size_t hi = 0;

        for (int num : nums) {
            lo = std::max(lo, (size_t) num);
            hi += num;
        }

        while (lo < hi) {
            size_t mid = lo + (hi - lo) / 2;
            if (partitioning_is_valid(nums, m - 1, mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        return lo;
    }

private:
    static bool partitioning_is_valid(const std::vector<int> &nums, int partitions, size_t partition_max_sum) {
        size_t accumulate_curr_partition = 0;
        for (int num : nums) {
            if (num > partition_max_sum) {
                return false;
            } else if (accumulate_curr_partition + num <= partition_max_sum) {
                accumulate_curr_partition += num;
            } else {
                partitions--;
                accumulate_curr_partition = num;

                if (partitions < 0) {
                    return false;
                }
            }
        }

        return true;
    }

};

Reference

LeetCode has a template for answering questions. There is usually a class named Solution with one or more public functions which we are not allowed to rename. For this question, the template is:

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        
    }
};

• Problem

• Solution

• Discuss

Answer 1

Function signatures

You've made the best out of a slightly silly situation. I think your function signatures, while abiding to the template, have improved since the last post of yours that I reviewed.

I'm not sure whether this will break LeetCode compatibility, but if you want to enforce that no one can instantiate this class, try making a private default constructor.

Mean

A simpler way to express the arithmetic mean than

        size_t mid = lo + (hi - lo) / 2;

is

        size_t mid = (hi + lo) / 2;