✂️ Beginner-Friendly Guide 'Divide an Array Into Subarrays With Minimum Cost I' - Problem 3010 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

You’re given:

• An array of integers nums of length n.
• The cost of a subarray is defined as the value of its first element.

Your goal:

• Split the array into exactly three contiguous subarrays.
• Minimize the total cost, i.e., the sum of the first elements of the three subarrays.

Intuition

Because the subarrays must be contiguous, the first element of the original array (nums[0]) will always be the first element of the first subarray, so it is inevitably part of the total cost.

To minimize the sum, we need to choose two additional starting points for the second and third subarrays from the remaining elements (nums[1:]). The optimal choice is simply the two smallest values in that suffix, as they will become the first elements of the second and third subarrays.

Walkthrough: Understanding the Examples

Example 1

nums = [1, 2, 3, 12]

• First element: 1
• Remaining elements: [2, 3, 12]
• Two smallest values: 2 and 3
• Minimum total cost: 1 + 2 + 3 = 6

Example 2

nums = [10, 3, 1, 1]

• First element: 10
• Remaining elements: [3, 1, 1]
• Two smallest values: 1 and 1
• Minimum total cost: 10 + 1 + 1 = 12

Code Blocks

C++

class Solution {
public:
    int minimumCost(vector& nums) {
        // The maximum possible value based on constraints
        int min1 = 51;
        int min2 = 51;

        // Start from index 1 because nums[0] is always included
        for (int i = 1; i  // (loop logic omitted in original)
    }
};

Python

# nums[0] is always the start of the first subarray
first_val = nums[0]

# Get the rest of the array and sort to find the two smallest elements
remaining = nums[1:]
remaining.sort()

# Sum the first element and the two smallest from the rest
return first_val + remaining[0] + remaining[1]

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumCost = function(nums) {
    const firstVal = nums[0];

    // Extract everything after the first element
    let remaining = nums.slice(1);

    // Sort numerically in ascending order
    remaining.sort((a, b) => a - b);

    // The result is the sum of the first element and the two smallest remaining
    return firstVal + remaining[0] + remaining[1];
};

Key Takeaways

• Fixed Constraint: Recognizing that nums[0] is always part of the cost reduces the problem to selecting two additional elements.
• Greedy Selection: Picking the two smallest values from the remaining array guarantees the minimal possible sum.
• Efficiency: The solution runs in O(n) time if we find the two minima in a single pass, or O(n log n) if we sort. With the given constraints, both approaches are fast.

Final Thoughts

This problem illustrates how a seemingly complex partitioning task can become trivial once we focus on the actual cost definition. By observing that only the first elements of each subarray matter, we turn the problem into a simple greedy selection—an approach that often appears in real‑world optimization scenarios such as minimizing entry‑point latency in load balancers.