Skip to main content
Talentd

Divide an Array Into Subarrays With Minimum Cost I - Solution & Explanation

EasyArraySortingEnumeration15 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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 <= 50
  • 1 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(1), owing to a straightforward evaluation.
Space complexity: O(1), fixed due to the lack of dependency on dynamically allocated space.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming

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.

Greedy Technique

Time complexity: O(1), owing to a straightforward evaluation.
Space complexity: O(1), fixed due to the lack of dependency on dynamically allocated space.

Traverse to Find the Smallest and Second Smallest Values—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Pair Enumeration / DPO(n²)O(n)Useful for understanding the split selection process or extending to more complex partition rules
Greedy with SortingO(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

Video Solution

Divide an Array Into Subarrays With Minimum Cost I | Simple Intuition | Leetcode 3010 | MIK • codestorywithMIK • 6,218 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Divide an Array Into Subarrays With Minimum Cost I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays