Problem Description

You have an array of integers nums with length n.

The cost of an array is defined as the value of its first element. For example:

• The cost of [1,2,3] is 1 (the first element)
• The cost of [3,4,1] is 3 (the first element)

Your task is to divide the array nums into exactly 3 disjoint contiguous subarrays. This means:

• You split the array into 3 consecutive parts
• Each part must be non-empty
• Together, these 3 parts contain all elements from the original array
• No element appears in more than one part

The total cost is the sum of the costs of all 3 subarrays (i.e., the sum of the first elements of each subarray).

You need to find the minimum possible sum of these costs.

For example, if nums = [1, 2, 5, 3, 4], one way to split it could be:

• First subarray: [1] with cost 1
• Second subarray: [2, 5] with cost 2
• Third subarray: [3, 4] with cost 3
• Total cost: 1 + 2 + 3 = 6

The goal is to find the splitting strategy that minimizes this total cost.

Intuition

Let's think about what happens when we split the array into 3 contiguous subarrays. We need to make two cuts in the array to create three parts.

The key insight is that the first subarray must always start with nums[0], since we're splitting the original array into contiguous parts. This means nums[0] will always contribute to our total cost, no matter how we split the array.

Now, where should we make our two cuts? Each cut creates a new subarray, and each new subarray contributes its first element to the total cost. So after making two cuts:

• The first subarray contributes nums[0] (fixed)
• The second subarray contributes its first element (depends on where we cut)
• The third subarray contributes its first element (depends on where we cut)

Here's the crucial observation: the first elements of the second and third subarrays can be any elements from nums[1] onwards (since we can place our cuts anywhere after position 0).

To minimize the total cost, we want the first elements of the second and third subarrays to be as small as possible. This means we should:

1. Find the smallest element in nums[1:] - this will be the first element of one subarray
2. Find the second smallest element in nums[1:] - this will be the first element of the other subarray

The minimum possible sum is therefore: nums[0] + (smallest element after index 0) + (second smallest element after index 0)

This explains why the solution simply finds the two smallest values among nums[1:] and adds them to nums[0]. We can always arrange our cuts to make these two elements the starting points of the second and third subarrays.

Learn more about Sorting patterns.

Solution Approach

Based on our intuition, we need to find the two smallest elements from nums[1:] and add them to nums[0]. The implementation uses a simple traversal with three variables:

1. Initialize three variables:

   • a = nums[0]: This is the fixed cost from the first subarray
   • b = inf: Will store the smallest element from nums[1:]
   • c = inf: Will store the second smallest element from nums[1:]

2. Traverse through the remaining elements (starting from index 1): For each element x in nums[1:]:

   • If x < b: This means we found a new smallest element
     • Move the current smallest b to become the second smallest: c = b
     • Update b with the new smallest: b = x
   • Else if x < c: This means x is not the smallest but is smaller than the current second smallest
     • Update c with this value: c = x

3. Return the sum: a + b + c

This approach efficiently finds the two minimum values in a single pass through the array. The algorithm maintains the invariant that b is always the smallest element seen so far (after index 0), and c is the second smallest.

Time Complexity: O(n) - We traverse the array once
Space Complexity: O(1) - We only use three extra variables regardless of input size

The elegance of this solution lies in its simplicity - instead of trying all possible ways to split the array (which would be expensive), we directly compute the minimum possible cost by identifying which elements must contribute to it.

Example Walkthrough

Let's walk through the solution with nums = [10, 2, 8, 5, 1, 9].

Step 1: Initialize variables

• a = nums[0] = 10 (first subarray's cost is fixed)
• b = inf (will track smallest element after index 0)
• c = inf (will track second smallest element after index 0)

Step 2: Process each element from index 1 onwards

Processing nums[1] = 2:

• Is 2 < b (inf)? Yes!
• Update: c = b = inf, b = 2
• Current state: a=10, b=2, c=inf

Processing nums[2] = 8:

• Is 8 < b (2)? No
• Is 8 < c (inf)? Yes!
• Update: c = 8
• Current state: a=10, b=2, c=8

Processing nums[3] = 5:

• Is 5 < b (2)? No
• Is 5 < c (8)? Yes!
• Update: c = 5
• Current state: a=10, b=2, c=5

Processing nums[4] = 1:

• Is 1 < b (2)? Yes!
• Update: c = b = 2, b = 1
• Current state: a=10, b=1, c=2

Processing nums[5] = 9:

• Is 9 < b (1)? No
• Is 9 < c (2)? No
• No updates needed
• Final state: a=10, b=1, c=2

Step 3: Calculate result

• Minimum sum = a + b + c = 10 + 1 + 2 = 13

Verification: We found that the two smallest elements after index 0 are 1 (at index 4) and 2 (at index 1). The algorithm correctly identifies these values. One possible split achieving this cost would be:

• First subarray: [10, 2, 8, 5] with cost 10
• Second subarray: [1] with cost 1
• Third subarray: [9] with cost 2 (wait, this would be 9!)

Actually, let me reconsider. We need the split where index 1 and index 4 are starting positions:

• First subarray: [10] with cost 10
• Second subarray: [2, 8, 5] with cost 2
• Third subarray: [1, 9] with cost 1
• Total: 10 + 2 + 1 = 13 ✓

The algorithm correctly identifies that regardless of how we arrange our cuts, the minimum possible sum is 13 by ensuring the two smallest elements after position 0 become the starting elements of the second and third subarrays.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the code iterates through the array once starting from index 1 (through nums[1:]), performing constant-time operations (comparisons and assignments) for each element.

The space complexity is O(1). The algorithm only uses three variables (a, b, c) to store values regardless of the input size, requiring constant extra space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Incorrect Update Order When Finding Two Minimum Values

A common mistake when tracking the two smallest elements is updating the variables in the wrong order or forgetting to cascade the updates properly.

Incorrect Implementation:

for current_num in nums[1:]:
    if current_num < smallest:
        smallest = current_num  # ❌ Lost the previous smallest value!
        second_smallest = smallest  # This assigns the NEW smallest, not the old one
    elif current_num < second_smallest:
        second_smallest = current_num

In this buggy version, when we find a new smallest element, we lose track of the previous smallest value that should become the new second smallest. The line second_smallest = smallest executes AFTER we've already updated smallest, so both variables end up with the same value.

Another Common Mistake:

for current_num in nums[1:]:
    if current_num < second_smallest:  # ❌ Checking second_smallest first
        second_smallest = current_num
    if current_num < smallest:
        smallest = current_num

This approach uses two independent if statements instead of if-elif, which can cause the same element to update both variables. Also, checking second_smallest before smallest breaks the logic since an element smaller than smallest is definitely smaller than second_smallest.

Correct Solution:

for current_num in nums[1:]:
    if current_num < smallest:
        second_smallest = smallest  # Save old smallest BEFORE updating
        smallest = current_num
    elif current_num < second_smallest:
        second_smallest = current_num

The key points to remember:

1. Always save the old value before overwriting it
2. Use if-elif structure to ensure each element only updates variables once
3. Check against smallest first, then second_smallest
4. When updating smallest, cascade the old value to second_smallest

This pattern of maintaining the top-k minimum (or maximum) values is useful in many problems and getting the update logic right is crucial for correctness.