Problem

You are given an array of integers nums of length n.

The cost of an array is the value of its first element. For example, the cost of [1,2,3] is 1 while the cost of [3,4,1] is 3.

You need to divide nums into 3 disjoint contiguous subarrays.

Return theminimum possible sum of the cost of these subarrays.

Examples

Example 1

1
2
3
4
5
6

Input: nums = [1,2,3,12]
Output: 6
Explanation: The best possible way to form 3 subarrays is: [1], [2], and [3,12] at a total cost of 1 + 2 + 3 = 6.
The other possible ways to form 3 subarrays are:
- [1], [2,3], and [12] at a total cost of 1 + 2 + 12 = 15.
- [1,2], [3], and [12] at a total cost of 1 + 3 + 12 = 16.

Example 2

1
2
3
4

Input: nums = [5,4,3]
Output: 12
Explanation: The best possible way to form 3 subarrays is: [5], [4], and [3] at a total cost of 5 + 4 + 3 = 12.
It can be shown that 12 is the minimum cost achievable.

Example 3

1
2
3
4

Input: nums = [10,3,1,1]
Output: 12
Explanation: The best possible way to form 3 subarrays is: [10,3], [1], and [1] at a total cost of 10 + 1 + 1 = 12.
It can be shown that 12 is the minimum cost achievable.

Constraints

  • 3 <= n <= 50
  • 1 <= nums[i] <= 50

Solution

Method 1 – Brute Force Enumeration

Intuition

Since the array is small (n <= 50), we can try all possible ways to split the array into 3 contiguous subarrays and compute the sum of their first elements. The minimum sum among all possible splits is the answer.

Approach

  1. For every possible first split point i (from 1 to n-2), and every possible second split point j (from i+1 to n-1):
    • The subarrays are: nums[0:i], nums[i:j], nums[j:n].
    • The cost is nums[0] + nums[i] + nums[j].
  2. Track the minimum cost found.
  3. Return the minimum cost.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int minimumCost(vector<int>& nums) {
        int n = nums.size(), ans = INT_MAX;
        for (int i = 1; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                ans = min(ans, nums[0] + nums[i] + nums[j]);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func minimumCost(nums []int) int {
    n := len(nums)
    ans := 1 << 30
    for i := 1; i < n-1; i++ {
        for j := i + 1; j < n; j++ {
            cost := nums[0] + nums[i] + nums[j]
            if cost < ans {
                ans = cost
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int minimumCost(int[] nums) {
        int n = nums.length, ans = Integer.MAX_VALUE;
        for (int i = 1; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                ans = Math.min(ans, nums[0] + nums[i] + nums[j]);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minimumCost(nums: IntArray): Int {
        val n = nums.size
        var ans = Int.MAX_VALUE
        for (i in 1 until n - 1) {
            for (j in i + 1 until n) {
                ans = minOf(ans, nums[0] + nums[i] + nums[j])
            }
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def minimumCost(self, nums: list[int]) -> int:
        n = len(nums)
        ans = float('inf')
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                ans = min(ans, nums[0] + nums[i] + nums[j])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn minimum_cost(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = i32::MAX;
        for i in 1..n - 1 {
            for j in i + 1..n {
                ans = ans.min(nums[0] + nums[i] + nums[j]);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    minimumCost(nums: number[]): number {
        const n = nums.length;
        let ans = Number.MAX_SAFE_INTEGER;
        for (let i = 1; i < n - 1; ++i) {
            for (let j = i + 1; j < n; ++j) {
                ans = Math.min(ans, nums[0] + nums[i] + nums[j]);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), since we try all pairs of split points.
  • 🧺 Space complexity: O(1), only a constant amount of extra space is used.