Watch 10 video solutions for Divide an Array Into Subarrays With Minimum Cost I, a easy level problem involving Array, Sorting, Enumeration. This walkthrough by codestorywithMIK has 6,006 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 50Problem Overview: You divide the array into exactly three non‑empty subarrays. The cost of each subarray equals its first element. The goal is to choose two split points so the sum of the three starting elements is minimized.
Approach 1: Dynamic Programming Enumeration (O(n²) time, O(n) space)
Model the process as selecting two split indices i and j where 0 < i < j < n. The cost becomes nums[0] + nums[i] + nums[j]. A simple DP or enumeration scans all valid pairs. Maintain the best prefix candidate for the second segment while iterating possible j positions. This mirrors a DP transition where you track the minimum possible starting cost for earlier segments. The approach works but does unnecessary work because the order constraint alone already guarantees a simpler solution.
Approach 2: Greedy with Two Minimum Values (O(n) time, O(1) space)
The first subarray must start at index 0, so its contribution is fixed: nums[0]. The remaining task is choosing two starting indices for the next two subarrays. Since only the values matter and the order constraint i < j always holds when picking two different indices, you simply need the two smallest values in nums[1..n-1]. Scan the array once and track the smallest and second smallest numbers. The final answer is nums[0] + min1 + min2. This greedy observation removes the need for sorting or pair enumeration.
An alternative greedy variant sorts the suffix nums[1..] using sorting and takes the first two values. Sorting makes the logic obvious but costs O(n log n) time. The single-pass minimum tracking is the optimal implementation.
The core reasoning relies on properties of arrays and simple enumeration. Since the first element of each subarray defines its cost, minimizing the result reduces to picking the smallest valid starting points.
Recommended for interviews: Use the greedy single-pass approach. It shows you recognize that the first segment is fixed and the remaining cost depends only on the two smallest values after index 0. Mentioning the enumeration or DP formulation first demonstrates problem understanding, but the greedy solution highlights optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pair Enumeration / DP | O(n²) | O(n) | Useful for understanding the split selection process or extending to more complex partition rules |
| Greedy with Sorting | O(n log n) | O(1) or O(n) | Simple implementation when sorting is acceptable |
| Greedy Two-Min Scan (Optimal) | O(n) | O(1) | Best choice for interviews and production code |