Divide an Array Into Subarrays With Minimum Cost I
EasyPrompt
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 <= 501 <= nums[i] <= 50
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a variable
minCostto 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
ifrom1ton-2(start of the second subarray). - The inner loop iterates with index
jfromi+1ton-1(start of the third subarray). - For each pair of
(i, j), calculate thecurrentCostasnums[0] + nums[i] + nums[j]. - Update
minCostwith the minimum value between the currentminCostandcurrentCost. - After the loops complete,
minCostwill hold the minimum possible sum of costs.
Walkthrough
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.
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; }}Complexity
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`.
Trade-offs
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).
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.
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 sumnums[i] + nums[j]where1 <= 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
numsfrom index 1 ton-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.
Walkthrough
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.
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]; }}Complexity
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.
Trade-offs
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.
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.
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,
min1andmin2, to a very large value (e.g.,Integer.MAX_VALUE). - Iterate through the array
numsfrom index1ton-1. - For each element
num = nums[i]:- If
numis smaller than or equal tomin1, it's the new smallest. Updatemin2 = min1andmin1 = num. - Else if
numis smaller thanmin2, it's the new second-smallest. Updatemin2 = num.
- If
- After the loop,
min1andmin2will hold the two smallest values fromnums[1...n-1]. - The final minimum cost is
nums[0] + min1 + min2.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 + cVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.