LeetCode 3010 - Divide an Array Into Subarrays With Minimum Cost I

The problem asks us to split a given array nums into exactly three disjoint contiguous subarrays and minimize the sum of their costs. The important detail is how cost is defined. The cost of a subarray is simply its first element.

leetcodeeasyarraysortingenumeration

LeetCode Problem 3010

Difficulty: 🟢 Easy
Topics: Array, Sorting, Enumeration

Solution

Problem Understanding

The problem asks us to split a given array nums into exactly three disjoint contiguous subarrays and minimize the sum of their costs.

The important detail is how cost is defined. The cost of a subarray is simply its first element. For example:

  • [1,2,3] has cost 1
  • [10,5] has cost 10

Since we must divide the array into exactly three contiguous pieces, we are effectively choosing two cut positions in the array. These cuts determine where one subarray ends and the next begins.

Suppose we divide:

nums = [a, b, c, d, e]

into:

[a, b] | [c] | [d, e]

Then the total cost is:

a + c + d

because those are the first elements of the three subarrays.

An important observation is that the first subarray always starts at index 0, meaning the first cost is always:

nums[0]

The only choices we actually control are where the second and third subarrays begin. Since the second and third subarrays must each start somewhere after index 0, we need to choose two additional elements whose sum is as small as possible.

The constraints are very small:

  • 3 <= n <= 50
  • 1 <= nums[i] <= 50

This tells us that even brute-force approaches are feasible because the input size is tiny. We do not need sophisticated optimizations for performance, but we should still aim for a clean and elegant solution.

Several edge cases are worth noting upfront. When n = 3, every element must form its own subarray, so the answer is simply the sum of all elements. Arrays with repeated minimum values should still work correctly since we only care about selecting two positions after index 0. Also, the optimal partition may place multiple elements into the first subarray if that allows the second and third subarrays to begin at smaller values.

Approaches

Brute Force

A straightforward approach is to try every possible way to place two cuts.

If we place the first cut after index i and the second cut after index j, where:

0 <= i < j < n - 1

then the subarrays become:

nums[0:i+1]
nums[i+1:j+1]
nums[j+1:]

The cost is:

nums[0] + nums[i+1] + nums[j+1]

We compute this cost for every valid pair of cuts and return the minimum.

This works because we exhaustively evaluate every valid partition into three contiguous pieces. Since n <= 50, the worst-case runtime is perfectly acceptable.

Optimal Insight

The key observation is that the first subarray always begins at index 0, so its contribution to the cost is fixed:

nums[0]

The second and third subarrays can start at any two positions among indices:

1 to n - 1

Since the total cost only depends on the starting values of subarrays, we simply need to choose the two smallest elements after index 0.

Why does this work?

Because any two positions after index 0 can always define valid contiguous subarrays. If we pick positions i < j, we can construct:

nums[0:i]
nums[i:j]
nums[j:]

Thus, minimizing cost reduces to selecting the two smallest values from:

nums[1:]

This turns the problem into a simple sorting problem.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Try every possible pair of cut positions
Optimal O(n log n) O(n) Sort elements after index 0 and take the two smallest

Algorithm Walkthrough

Optimal Algorithm

  1. Take the first element nums[0] as the initial cost.

This value is unavoidable because the first subarray must always start at index 0. 2. Extract all elements after index 0.

These represent all possible starting points for the second and third subarrays. 3. Sort this remaining portion of the array.

Sorting makes it easy to identify the two smallest possible starting values. 4. Take the first two elements from the sorted list.

These are the smallest candidates for the second and third subarray costs. 5. Add them to nums[0].

This gives the minimum achievable total cost.

Why it works

The correctness comes from the fact that the cost depends only on the first element of each subarray. Since the first subarray always starts at index 0, its cost is fixed. Any pair of indices after 0 can legally define the beginnings of the second and third contiguous subarrays. Therefore, minimizing the total cost reduces to selecting the two smallest values among nums[1:]. Sorting guarantees we find these minimum values.

Python Solution

from typing import List

class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        remaining = sorted(nums[1:])
        return nums[0] + remaining[0] + remaining[1]

The implementation follows the algorithm directly.

We first isolate the elements after the first index using nums[1:]. These are the only candidates for the starts of the second and third subarrays.

Next, we sort this slice so that the smallest values appear first. Since we only need the two minimum values, we take:

remaining[0]
remaining[1]

Finally, we add them to nums[0], which is always part of the answer because the first subarray necessarily starts there.

The implementation is concise because the problem's key insight eliminates the need for explicit partition simulation.

Go Solution

import "sort"

func minimumCost(nums []int) int {
    remaining := make([]int, len(nums)-1)
    copy(remaining, nums[1:])

    sort.Ints(remaining)

    return nums[0] + remaining[0] + remaining[1]
}

The Go implementation closely mirrors the Python version.

One small difference is that we create a copy of nums[1:] before sorting. In Go, slices reference the original underlying array, so sorting directly would mutate the input. Creating remaining avoids modifying nums.

Integer overflow is not a concern because the maximum possible sum is:

50 + 50 + 50 = 150

which easily fits within Go's int.

Worked Examples

Example 1

nums = [1,2,3,12]

We begin with:

fixed cost = nums[0] = 1

The remaining candidates are:

[2,3,12]

After sorting:

Step Value
Remaining [2,3,12]
Sorted [2,3,12]
Two smallest 2, 3

Final cost:

1 + 2 + 3 = 6

Result:

6

Example 2

nums = [5,4,3]

Initial cost:

5

Remaining values:

[4,3]

After sorting:

Step Value
Remaining [4,3]
Sorted [3,4]
Two smallest 3, 4

Final cost:

5 + 3 + 4 = 12

Result:

12

Example 3

nums = [10,3,1,1]

Initial cost:

10

Remaining values:

[3,1,1]

After sorting:

Step Value
Remaining [3,1,1]
Sorted [1,1,3]
Two smallest 1, 1

Final cost:

10 + 1 + 1 = 12

Result:

12

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting the n - 1 remaining elements dominates runtime
Space O(n) Extra space is used to store the sliced and sorted elements

The sorting step dominates the complexity. Since n <= 50, performance is trivial in practice. Even though a linear scan for the two smallest values is possible, sorting keeps the implementation clean and easy to understand.

Test Cases

solution = Solution()

# Provided examples
assert solution.minimumCost([1, 2, 3, 12]) == 6  # standard example
assert solution.minimumCost([5, 4, 3]) == 12  # minimum size array
assert solution.minimumCost([10, 3, 1, 1]) == 12  # optimal split uses later elements

# Boundary cases
assert solution.minimumCost([1, 1, 1]) == 3  # smallest valid n
assert solution.minimumCost([50, 50, 50]) == 150  # maximum values

# Repeated minimum values
assert solution.minimumCost([8, 2, 2, 2]) == 12  # duplicate minimums

# Descending order
assert solution.minimumCost([10, 9, 8, 7, 6]) == 23  # choose smallest later values

# Ascending order
assert solution.minimumCost([1, 2, 3, 4, 5]) == 6  # smallest values already early

# Large first value
assert solution.minimumCost([100, 1, 2, 3]) == 103  # first element always included

# Optimal split near end
assert solution.minimumCost([9, 8, 7, 1, 2]) == 12  # later elements are optimal
Test Why
[1,2,3,12] Validates standard example
[5,4,3] Tests minimum array size
[10,3,1,1] Verifies optimal cuts can occur late
[1,1,1] Ensures smallest valid input works
[50,50,50] Tests upper element bounds
[8,2,2,2] Confirms duplicate minimum values
[10,9,8,7,6] Checks descending arrays
[1,2,3,4,5] Checks ascending arrays
[100,1,2,3] Ensures first element is always included
[9,8,7,1,2] Verifies smallest values can appear near the end

Edge Cases

One important edge case occurs when n = 3. Since exactly three subarrays are required and there are only three elements, each element must form its own subarray. A naive implementation might accidentally assume flexibility in partitioning, but our solution handles this naturally because nums[1:] contains exactly two elements, both of which are added.

Another tricky case is when the smallest elements appear near the end of the array. For example:

[10, 9, 8, 1, 2]

A naive greedy strategy might incorrectly choose earlier cut positions. Our approach works because contiguity does not restrict which later positions can begin subarrays, so choosing the globally smallest two values is always valid.

Repeated values are another potential source of bugs. Consider:

[8, 2, 2, 2]

Some implementations may accidentally select the same position twice or mishandle duplicates. Sorting and taking the first two elements works correctly because duplicates are preserved naturally.

Finally, very large first elements can be misleading. For example:

[100, 1, 2, 3]

The first cost cannot be avoided because the first subarray always begins at index 0. Our implementation explicitly includes nums[0], ensuring correctness.