# Divide an Array Into Subarrays With Minimum Cost I
**Difficulty:** EASY
[External](https://leetcode.com/problems/divide-an-array-into-subarrays-with-minimum-cost-i)
Canonical: https://scaleengineer.com/dsa/problems/divide-an-array-into-subarrays-with-minimum-cost-i
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [American Express](https://scaleengineer.com/companies/american-express)
---
## 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 _the **minimum** possible **sum** of the cost of these subarrays_.

**Example 1:**

**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:**

**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:**

**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`

# Approaches
## Brute Force with Nested Loops
This approach directly translates the problem statement into code. We need to find two split points to create three subarrays. The first subarray always starts at index 0, so its cost is fixed at `nums[0]`. We then need to choose the starting points for the second and third subarrays. Let's say the second subarray starts at index `i` and the third at index `j`. To ensure three non-empty subarrays, `i` must be at least 1, and `j` must be greater than `i`. We can iterate through all possible pairs of `(i, j)` and calculate the total cost for each, keeping track of the minimum cost found.
**Time:** O(n^2), where n is the length of the array. The nested loops iterate through approximately n^2/2 pairs of indices, leading to a quadratic time complexity. · **Space:** O(1), as we only use a constant amount of extra space for variables like `minCost`, `i`, and `j`.
**Pros:** Simple to understand and implement.; Directly models the problem's constraints without requiring complex insights.
**Cons:** Inefficient for large input sizes due to its quadratic time complexity, though it's acceptable for the given constraints (n <= 50).
### Explanation
The core idea is to explore every valid way to partition the array into three contiguous subarrays. The first subarray is `nums[0...i-1]` with cost `nums[0]`, the second is `nums[i...j-1]` with cost `nums[i]`, and the third is `nums[j...n-1]` with cost `nums[j]`. The total cost for a given pair of split points `i` and `j` is `nums[0] + nums[i] + nums[j]`. We use nested loops to iterate through all valid `i` and `j`, where `1 <= i < j < n`, and find the minimum sum.

```java
class Solution {
    public int minimumCost(int[] nums) {
        int n = nums.length;
        int minCost = Integer.MAX_VALUE;
        int firstCost = nums[0];

        // i is the start index of the second subarray
        for (int i = 1; i < n - 1; i++) {
            // j is the start index of the third subarray
            for (int j = i + 1; j < n; j++) {
                int currentCost = firstCost + nums[i] + nums[j];
                if (currentCost < minCost) {
                    minCost = currentCost;
                }
            }
        }
        return minCost;
    }
}
```
### Algorithm
- Initialize a variable `minCost` to a very large value (e.g., `Integer.MAX_VALUE`).
- The cost of the first subarray is always `nums[0]`, which is a fixed part of the total cost.
- Use a nested loop to iterate through all possible starting indices for the second and third subarrays.
- The outer loop iterates with index `i` from `1` to `n-2` (start of the second subarray).
- The inner loop iterates with index `j` from `i+1` to `n-1` (start of the third subarray).
- For each pair of `(i, j)`, calculate the `currentCost` as `nums[0] + nums[i] + nums[j]`.
- Update `minCost` with the minimum value between the current `minCost` and `currentCost`.
- After the loops complete, `minCost` will hold the minimum possible sum of costs.

## Sorting the Subarray
A key observation simplifies the problem. The cost of the first subarray is always `nums[0]`. The total cost is `nums[0] + nums[i] + nums[j]`, where `i` and `j` are the start indices of the second and third subarrays, with `1 <= i < j < n`. To minimize the total cost, we need to minimize the sum `nums[i] + nums[j]`. This is equivalent to finding the two smallest elements in the rest of the array, i.e., the subarray `nums[1...n-1]`. A straightforward way to find the two smallest elements is to sort this subarray and pick the first two.
**Time:** O(n log n), where n is the length of the input array. The dominant operation is sorting the subarray of size `n-1`. · **Space:** O(n), due to creating a copy of the subarray `nums[1...n-1]` using `Arrays.copyOfRange`. If sorting could be done in-place on a slice, space could be reduced to O(log n) for the recursion stack of the sort algorithm.
**Pros:** More efficient than the brute-force approach with a time complexity of O(n log n).; Conceptually simple: reduces the problem to finding the two smallest elements.
**Cons:** Requires extra space (O(n)) to create a copy of the subarray for sorting.; Sorting is more work than necessary, as we only need the two smallest elements, not a fully sorted array.
### Explanation
The problem reduces to finding the two smallest costs for the second and third subarrays. These costs come from the elements `nums[1]` through `nums[n-1]`. We can isolate this relevant part of the array, sort it, and then the two smallest elements will be at the beginning. The final minimum total cost is `nums[0]` plus the sum of these two smallest elements.

```java
import java.util.Arrays;

class Solution {
    public int minimumCost(int[] nums) {
        int n = nums.length;
        // The cost of the first subarray is always nums[0].
        int firstCost = nums[0];

        // We need to find the two smallest elements in the rest of the array.
        // Create a subarray from index 1 to n-1.
        int[] remaining = Arrays.copyOfRange(nums, 1, n);
        
        // Sort the remaining part to find the two smallest elements.
        Arrays.sort(remaining);
        
        // The minimum cost is the sum of the first element of the original array
        // and the two smallest elements from the rest of the array.
        return firstCost + remaining[0] + remaining[1];
    }
}
```
### Algorithm
- The cost of the first subarray is fixed at `nums[0]`.
- To minimize the total cost `nums[0] + nums[i] + nums[j]`, we must minimize the sum `nums[i] + nums[j]` where `1 <= i < j < n`.
- This is equivalent to finding the two smallest elements in the subarray `nums[1...n-1]`.
- Create a new array containing elements of `nums` from index 1 to `n-1`.
- Sort this new array in ascending order.
- The two smallest elements will be the first two elements of the sorted array.
- The minimum total cost is `nums[0]` plus the sum of these two elements.

## Optimal Single Pass
This approach builds on the same observation as the sorting method: we need to find the two smallest elements in the subarray `nums[1...n-1]`. However, instead of sorting the entire subarray, we can find the two smallest elements much more efficiently by iterating through the subarray just once.
**Time:** O(n), where n is the length of the array. We perform a single pass through the subarray `nums[1...n-1]`. · **Space:** O(1), as we only use a constant number of extra variables (`min1`, `min2`) regardless of the input size.
**Pros:** Most efficient solution in terms of both time (O(n)) and space (O(1)) complexity.; Simple to implement and avoids the overhead of sorting.
**Cons:** The logic for tracking two minimums can be slightly more complex to write correctly compared to just calling a sort function.
### Explanation
We can maintain two variables, `min1` and `min2`, to keep track of the smallest and second-smallest elements encountered so far in the subarray `nums[1...n-1]`. We initialize both `min1` and `min2` to a value larger than any possible element in the array. Then, we iterate from `i = 1` to `n-1`. For each element, we compare it with `min1` and `min2` and update them accordingly. After iterating through the subarray, `min1` and `min2` will hold the two smallest values, and the total minimum cost is `nums[0] + min1 + min2`.

```java
class Solution {
    public int minimumCost(int[] nums) {
        int firstCost = nums[0];
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] <= min1) {
                min2 = min1;
                min1 = nums[i];
            } else if (nums[i] < min2) {
                min2 = nums[i];
            }
        }
        
        return firstCost + min1 + min2;
    }
}
```
### Algorithm
- The total cost is `nums[0]` plus the costs of the second and third subarrays.
- To minimize the total cost, we need to find the two smallest elements in the subarray `nums[1...n-1]`.
- Initialize two variables, `min1` and `min2`, to a very large value (e.g., `Integer.MAX_VALUE`).
- Iterate through the array `nums` from index `1` to `n-1`.
- For each element `num = nums[i]`:
  - If `num` is smaller than or equal to `min1`, it's the new smallest. Update `min2 = min1` and `min1 = num`.
  - Else if `num` is smaller than `min2`, it's the new second-smallest. Update `min2 = num`.
- After the loop, `min1` and `min2` will hold the two smallest values from `nums[1...n-1]`.
- The final minimum cost is `nums[0] + min1 + min2`.

# Solutions
### Java

```java
class Solution {
public
  int minimumCost(int[] nums) {
    int a = nums[0], b = 100, c = 100;
    for (int i = 1; i < nums.length; ++i) {
      if (nums[i] < b) {
        c = b;
        b = nums[i];
      } else if (nums[i] < c) {
        c = nums[i];
      }
    }
    return a + b + c;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumCost(vector<int> &nums) {
    int a = nums[0], b = 100, c = 100;
    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] < b) {
        c = b;
        b = nums[i];
      } else if (nums[i] < c) {
        c = nums[i];
      }
    }
    return a + b + c;
  }
};

```

### Python

```python
class Solution:
    def minimumCost(self, nums: List[int]) -> int: a, b, c = nums[0], inf, inf for x in nums[1:]: if x < b: c, b = b, x elif x < c: c = x return a + b + c

```