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).
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; }}Video 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.