Divide an Array Into Subarrays With Minimum Cost I solution and explanation
Google
9 more videos on this problem
Divide an Array Into Subarrays With Minimum Cost I | Simple Intuition | Leetcode 3010 | MIKcodestorywithMIK · 9:20 · 6K views
3010. Divide an Array Into Subarrays With Minimum Cost I | Leetcode Daily - PythonLeetcode Daily · 7:41 · 1K views
Leetcode | 3010. Divide an Array Into Subarrays With Minimum Cost I | Easy | Java SolutionDeveloper Docs · 4:03 · 799 views
3010. Divide an Array Into Subarrays With Minimum Cost I (Leetcode Easy)Programming Live with Larry · 3:58 · 494 views
Divide an Array Into Subarrays With Minimum Cost I | LeetCode 3010 | Sorting + Optimal Greedy Study Placement · 13:08 · 488 views
Divide an Array Into Subarrays With Minimum Cost I | LeetCode 3010 | Java Code | Developer CoderDeveloper Coder · 8:07 · 437 views
Divide an Array Into Subarrays With Minimum Cost I | LeetCode 3010 | Sorting | Single PasscodeTips · 8:55 · 359 views
Daily Leetcode #2133: Feb 01, 2026 - 3010. Divide an Array Into Subarrays With Minimum Cost IProgramming Live with Larry · 4:06 · 243 views
Divide an Array Into Subarrays With Minimum Cost I | LeetCode 3010 - Python (2 Solutions)impoldev · 8:25 · 202 views
LeetCode 3010 - Divide an Array Into Subarrays With Minimum Cost I - PythonAlpha-Code · 9:38 · 180 views
The 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 <= 501 <= nums[i] <= 50
Approach overview
Problem 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 1: Dynamic Programming
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.
def divideIntoSubarrays(nums):
n = len(nums)
min_cost = float('inf')
for i in range(1, n - 1):
for j in range(i + 1, n):
cost = nums[0] + nums[i] + nums[j]
min_cost = min(min_cost, cost)
return min_cost
nums = [1, 2, 3, 12]
print(divideIntoSubarrays(nums))import java.util.*;
public class Solution {
public static int divideIntoSubarrays(int[] nums) {
int n = nums.length;
int min_cost = Integer.MAX_VALUE;
for (int i = 1; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int cost = nums[0] + nums[i] + nums[j];
min_cost = Math.min(min_cost, cost);
}
}
return min_cost;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 12};
System.out.println(divideIntoSubarrays(nums));
}
}#include <vector>
#include <limits>
#include <iostream>
using namespace std;
int divideIntoSubarrays(vector<int>& nums) {
int n = nums.size();
int min_cost = INT_MAX;
for (int i = 1; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int cost = nums[0] + nums[i] + nums[j];
min_cost = min(min_cost, cost);
}
}
return min_cost;
}
int main() {
vector<int> nums = {1, 2, 3, 12};
cout << divideIntoSubarrays(nums) << endl;
return 0;
}function divideIntoSubarrays(nums) {
const n = nums.length;
let minCost = Infinity;
for (let i = 1; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
const cost = nums[0] + nums[i] + nums[j];
minCost = Math.min(minCost, cost);
}
}
return minCost;
}
const nums = [1, 2, 3, 12];
console.log(divideIntoSubarrays(nums));#include <stdio.h>
#include <limits.h>
int divideIntoSubarrays(int* nums, int n) {
int min_cost = INT_MAX;
for (int i = 1; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int cost = nums[0] + nums[i] + nums[j];
if (cost < min_cost) {
min_cost = cost;
}
}
}
return min_cost;
}
int main() {
int nums[] = {1, 2, 3, 12};
int n = sizeof(nums)/sizeof(nums[0]);
int result = divideIntoSubarrays(nums, n);
printf("%d", result);
return 0;
}using System;
public class Solution {
public static int DivideIntoSubarrays(int[] nums) {
int n = nums.Length;
int minCost = int.MaxValue;
for (int i = 1; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int cost = nums[0] + nums[i] + nums[j];
if (cost < minCost) {
minCost = cost;
}
}
}
return minCost;
}
public static void Main(string[] args) {
int[] nums = {1, 2, 3, 12};
Console.WriteLine(DivideIntoSubarrays(nums));
}
}In Python, this approach still revolves around checking all valid configurations with nested loops and refining down to the lowest cost achievable by such subarrays' partitions starts.
Time complexity: O(n^2), by carrying out the loops to determine valid beginnings.
Space complexity: O(1), due to no additional auxiliary data structures.
Approach 2: Greedy Technique
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.
def greedyDivide(nums):
return nums[0] + nums[1] + nums[2] # Naive deterministic segmentation.
nums = [1, 2, 3, 12]
print(greedyDivide(nums))import java.util.*;
public class Solution {
public static int greedyDivide(int[] nums) {
return nums[0] + nums[1] + nums[2];
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 12};
System.out.println(greedyDivide(nums));
}
}#include <vector>
#include <iostream>
using namespace std;
int greedyDivide(vector<int>& nums) {
return nums[0] + nums[1] + nums[2];
}
int main() {
vector<int> nums = {1, 2, 3, 12};
cout << greedyDivide(nums) << endl;
return 0;
}function greedyDivide(nums) {
return nums[0] + nums[1] + nums[2];
}
const nums = [1, 2, 3, 12];
console.log(greedyDivide(nums));#include <stdio.h>
#include <limits.h>
int greedyDivide(int* nums, int n) {
return nums[0] + nums[1] + nums[2]; // Simplified decision being minimal fixed parts.
}
int main() {
int nums[] = {1, 2, 3, 12};
int n = sizeof(nums)/sizeof(nums[0]);
int result = greedyDivide(nums, n);
printf("%d", result);
return 0;
}using System;
public class Solution {
public static int GreedyDivide(int[] nums) {
return nums[0] + nums[1] + nums[2];
}
public static void Main(string[] args) {
int[] nums = {1, 2, 3, 12};
Console.WriteLine(GreedyDivide(nums));
}
}Python realization expects the first simple greedy step benefits from utilizing initial array's plain low computation burden, consuming naturally gradual first-step standpoint adherence given it finds desired quasi-usual cost peak efficiency outcomes.
Time complexity: O(1), with each part steadfastly determined.
Space complexity: O(1), kept constant without stark investment vis-a-vis effective leveraged state calculations.
Approach 3: Traverse to Find the Smallest and Second Smallest Values
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).
function minimumCost(nums: number[]): number {
let [a, b, c] = [nums[0], 100, 100];
for (const x of nums.slice(1)) {
if (x < b) {
[b, c] = [x, b];
} else if (x < c) {
c = x;
}
}
return a + b + c;
}func minimumCost(nums []int) int {
a, b, c := nums[0], 100, 100
for _, x := range nums[1:] {
if x < b {
b, c = x, b
} else if x < c {
c = x
}
}
return a + b + c
}impl Solution {
pub fn minimum_cost(nums: Vec<i32>) -> i32 {
let a: i32 = nums[0];
let mut b: i32 = i32::MAX;
let mut c: i32 = i32::MAX;
for &x in nums.iter().skip(1) {
if x < b {
c = b;
b = x;
} else if x < c {
c = x;
}
}
a + b + c
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time complexity: O(n^2), by carrying out the loops to determine valid beginnings. |
| Greedy Technique | Time complexity: O(1), with each part steadfastly determined. |
| Traverse to Find the Smallest and Second Smallest Values | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Divide an Array Into Subarrays With Minimum Cost I easy or hard?
Divide an Array Into Subarrays With Minimum Cost I is classified as an Easy problem. The key insight is recognizing that the cost depends only on the first element of each subarray, which reduces the problem to finding the two smallest values after the first element.
Divide an Array Into Subarrays With Minimum Cost I Python/Java solution
The typical implementation scans the array once, updating two variables for the smallest and second smallest numbers after index 0. The result is nums[0] plus those two values. The same logic translates directly across Python, Java, C++, and other languages.
How to solve Divide an Array Into Subarrays With Minimum Cost I in O(n)?
Iterate through nums[1..n-1] and keep track of the smallest and second smallest elements. Add those two values to nums[0], which represents the first subarray's cost. This single-pass technique avoids sorting and produces the minimum total cost in linear time.
What is the best approach for Divide an Array Into Subarrays With Minimum Cost I?
The optimal approach is a greedy scan that finds the two smallest values in the array after index 0. Since the first subarray must start at nums[0], the total cost becomes nums[0] plus the smallest two values from the remaining elements. This runs in O(n) time and O(1) space.
Is Divide an Array Into Subarrays With Minimum Cost I asked at Google/Amazon/Meta?
Problems with similar greedy array reasoning appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may not appear verbatim, the pattern of minimizing cost by selecting optimal elements is common in coding interviews.
What data structure is used in Divide an Array Into Subarrays With Minimum Cost I?
The solution primarily uses basic array traversal. The optimal greedy approach only tracks two minimum values during a single pass, so no additional data structures like heaps or hash maps are required.
What is the time complexity of Divide an Array Into Subarrays With Minimum Cost I?
The optimal greedy solution runs in O(n) time because it scans the array once to track the two smallest values after index 0. Space complexity is O(1) since only two variables are maintained.