Divide an Array Into Subarrays With Minimum Cost I

Difficulty: Easy | Acceptance: 80.60% | Paid: No Topics: Array, Sorting, Enumeration

You are given an integer array nums of length n.

You need to divide the array into exactly three non-empty subarrays.

The cost of a subarray is the first element of that subarray.

Return the minimum possible total cost of dividing the array into three subarrays.

• Examples
• Constraints
• Single Pass
• Sorting
• Brute Force

Examples

Input: nums = [1,2,3,12]
Output: 6
Explanation: The best way to divide the array is [1], [2], [3,12] with a total cost of 1 + 2 + 3 = 6.

Input: nums = [5,4,3,2,1]
Output: 8
Explanation: The best way to divide the array is [5,4,3], [2], [1] with a total cost of 5 + 2 + 1 = 8.

Input: nums = [10,1,2,3,4,5]
Output: 13
Explanation: The best way to divide the array is [10], [1], [2,3,4,5] with a total cost of 10 + 1 + 2 = 13.

Constraints

3 <= nums.length <= 50
1 <= nums[i] <= 50

Single Pass

Intuition The first subarray always starts at index 0, so its cost is fixed at nums[0]. We need to choose two more starting positions for the second and third subarrays from indices 1 to n-1. To minimize total cost, we should pick the two smallest values from nums[1:].

Steps

• Initialize nums[0] as the first cost
• Track the two smallest values while iterating through nums[1:]
• Return the sum of nums[0] and the two smallest values

class Solution:
    def minimumCost(self, nums: list[int]) -> int:
        first = nums[0]
        min1 = float('inf')
        min2 = float('inf')
        for i in range(1, len(nums)):
            if nums[i] < min1:
                min2 = min1
                min1 = nums[i]
            elif nums[i] < min2:
                min2 = nums[i]
        return first + min1 + min2

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution with single pass through the array

Sorting

Intuition Extract elements from index 1 onwards, sort them, and pick the two smallest values. The total cost is nums[0] plus these two smallest values.

Steps

• Create a copy of nums[1:]
• Sort the copy
• Return nums[0] + sorted_copy[0] + sorted_copy[1]

class Solution:
    def minimumCost(self, nums: list[int]) -> int:
        rest = sorted(nums[1:])
        return nums[0] + rest[0] + rest[1]

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Simpler code but less efficient due to sorting overhead

Brute Force

Intuition Try all possible pairs of indices (i, j) where 1 <= i < j < n, representing the start of the second and third subarrays. Calculate the cost for each pair and return the minimum.

Steps

• Initialize minimum cost to infinity
• Iterate through all valid pairs (i, j)
• Calculate cost as nums[0] + nums[i] + nums[j]
• Track and return the minimum cost

class Solution:
    def minimumCost(self, nums: list[int]) -> int:
        n = len(nums)
        min_cost = float('inf')
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                cost = nums[0] + nums[i] + nums[j]
                min_cost = min(min_cost, cost)
        return min_cost

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple but inefficient for larger arrays