1
\$\begingroup\$

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) {
        
    }
};
\$\endgroup\$
  • 1
    \$\begingroup\$ You can change the following lines in your source-code: lo = *std ::max_element(nums.begin(), nums.end()) and hi = std :: accumulate(nums.begin(), nums.end(), 0) and remove the for loop. Do make sure that to use this functions you need to include <algorithm> header file which by default is included in the Leet-Code default template. \$\endgroup\$ – strikersps Jul 3 at 7:13
1
\$\begingroup\$

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;
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 1 ≤ n ≤ 1000 so overflow is not an issue here unless you're using an 8-bit type, which you are not. \$\endgroup\$ – Reinderien Jul 2 at 16:08
  • 1
    \$\begingroup\$ On second read they leave the range of the actual array entries ambiguous? So maybe it's safe to keep the overflow-conscious version. \$\endgroup\$ – Reinderien Jul 2 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.