Problem Statement in English

You’re given an array nums.

You need to divide the array into 3 subarrays such that the cost is minimized.

The cost of a subarray is defined as the sum of its first element and the minimum element among all other elements in that subarray.

Your task is to find the minimum possible total cost after dividing the array into subarrays.

Approach

The first element of the array will always contribute to the cost, as it will be the first element of the first subarray.

We just need to find the two smallest elements in the rest of the array to minimize the cost of the other two subarrays.

So we can sort the array excluding the first element and pick the two smallest elements from it.

And we’re done!

Solution in Python


class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        return nums[0] + sum(sorted(nums[1:])[:2])

Complexity

  • Time: $O(n \log n)$
    Since we sort the array.

  • Space: $O(n)$
    Since we store the sorted array.

And we are done.