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;