MiddleCodeOccasionalNot answered yet
Split an array into 3 parts minimizing total first-element cost
An array of length n (with n >= 3) must be split into 3 contiguous non-empty parts. Each part's cost is its first element. Return the minimum possible total cost. [1,2,3,12] → 6 (parts [1],[2],[3,12]).
Requirements:
- O(n) single pass; sorting is not allowed.
int minSplitCost(const std::vector<int>& nums) {
// your code here
}Write the implementation.
The first part always starts at index 0, so its cost is fixed as nums[0]. The other two parts start at any two indices > 0, so their costs are the two smallest values among nums[1..]. The answer is nums[0] plus those two minima, in one O(n) pass.
- ✗Sorting and missing that the first part's cost is forced to be nums[0]
- ✗Including nums[0] when searching for the two minima of the other parts
- ✗Using an O(n²) double loop when one pass suffices
- →Why is the first part's cost forced and the rest free to be any two later indices?
- →How would the answer change for splitting into k parts?
Contents
Task
Split the array into 3 parts minimizing the total first-element cost, in O(n).
Solution
int minSplitCost(const std::vector<int>& nums) {
int min1 = INT_MAX, min2 = INT_MAX;
for (size_t i = 1; i < nums.size(); ++i) { // only nums[1..]
if (nums[i] < min1) { min2 = min1; min1 = nums[i]; }
else if (nums[i] < min2) { min2 = nums[i]; }
}
return nums[0] + min1 + min2;
}Key points
- The first part is fixed: its cost is
nums[0]. - The other two parts give the two smallest values of
nums[1..]. - One pass, no sorting — track the two minima.
Contents
