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.
The Dynamic Programming approach helps efficiently explore all possible ways to partition the array into subarrays and track the minimal cost achievable. The cost of any subarray is the value of its first element, and in this problem, you can consider breaking down the array such that each partition minimizes the starting costs. You essentially create a function that recursively finds the best division points that lead to the minimal overall start cost of subarrays.
The solution iterates through possible divisions of the array into three subarrays. We continuously check the cost of potential first elements of the subarrays and maintain the minimal cost found. This nested loop approach explores all configurations efficiently given constraints.
Time complexity: O(n^2), since we're using a nested loop to explore potential divisions.
Space complexity: O(1), as we utilize a constant amount of space outside the input array.
The Greedy approach involves picking partitions of the array based on specific criteria, optimizing each choice to attempt to achieve a globally minimal result. Here, we can focus on selecting ends that guarantee maximizing the cost reduction across splits. Breaking the array in greedy increments may be explored due to small size constraints.
This solution uses a simplified greedy technique, returning the sum of first possible fixed elements of subarrays, assuming that such setup tends to produce generally minimal starting sum. Note: This basic attempt showcases logic's potential, ensuring complete solution iteration might still hold most benefits.
Time complexity: O(1), owing to a straightforward evaluation.
Space complexity: O(1), fixed due to the lack of dependency on dynamically allocated space.
We set the first element of the array nums as a, the smallest element among the remaining elements as b, and the second smallest element as c. The answer is a+b+c.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time complexity: O(n^2), since we're using a nested loop to explore potential divisions. |
| Greedy Technique | Time complexity: O(1), owing to a straightforward evaluation. |
| Traverse to Find the Smallest and Second Smallest Values | — |
| 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 |
Divide an Array Into Subarrays With Minimum Cost I | Simple Intuition | Leetcode 3010 | MIK • codestorywithMIK • 6,006 views views
Watch 9 more video solutions →Practice Divide an Array Into Subarrays With Minimum Cost I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor