Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The first subarray must start at index zero, so its cost is fixed. The other two costs are the values at two distinct later starting positions. Any two such positions, ordered by index, define three nonempty contiguous subarrays, so only their values matter when minimizing the total.

Approach

Scan the array after its first element while retaining the smallest and second-smallest values seen. When a new value is smaller than the smallest, move the old smallest into second place. Otherwise, update the second-smallest when appropriate.

Return nums[0] plus those two minima. Equal values at different positions can occupy both minima because the subarrays need distinct starting indices, not distinct values. The length constraint guarantees that at least two later positions exist.

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        # res = nums[0]
        # nums = nums[1:]
        # nums.sort()
        # return res + nums[0] + nums[1]

        n = len(nums)
        mn1 = inf
        mn2 = inf

        for i in range(1, n):
            if nums[i] < mn1:
                mn2 = mn1
                mn1 = nums[i]
            elif nums[i] < mn2:
                mn2 = nums[i]

        return nums[0] + mn1 + mn2

Complexity analysis

Let n = nums.length. Time: O(n). Auxiliary space: O(1).