Skip to content

Divide an Array Into Subarrays With Minimum Cost I⚓︎

Link

Solution⚓︎

Sorting⚓︎

1
2
3
4
5
6
7
class Solution {
public:
    int minimumCost(vector<int>& nums) {
        sort(nums.begin() + 1, nums.end());
        return accumulate(nums.begin(), nums.begin() + 3, 0);
    }
};
  • Time complexity: \(O(n\log n)\);
  • Space complexity: \(O(1)\).

Maintain the First and Second Smallest Elements⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int minimumCost(vector<int>& nums) {
        int first = 0x3f3f3f3f, second = 0x3f3f3f3f;
        for (int i = 1; i < nums.size(); i++) {
            int x = nums[i];
            if (x < first) {
                second = first;
                first = x;
            } else if (x < second) {
                second = x;
            }
        }
        return nums[0] + first + second;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).