Leetcode Sunday #1

Leetcode 3010: Divide an Array Into Subarrays With Minimum Cost I

Difficulty: Easy

Time Spent: ~1 hour 47 minutes

This problem looks simple at first glance, but it took me some time to fully understand what actually matters and what doesn’t.

This post documents my thinking process, my initial (overcomplicated) solution, and how I eventually arrived at a clean and optimal approach.

---

Problem Summary

You are given an integer array nums.

• You must split it into 3 contiguous, non-empty subarrays
• The cost of a subarray is the value of its first element
• Return the minimum possible sum of the costs

---

First Observation: nums[0] Is Always Included

The first thing I noticed is that the first subarray always starts at index 0.

For example, given:

[1, 2, 3, 4, 5]

The first subarray can be:

• [1]
• [1, 2]
• [1, 2, 3]

But the cost is always 1, because the cost only depends on the first element.

So I started treating:

nums[0]

as a constant.

---

What Actually Affects the Minimum Cost

Since addition is addition, and nums[0] is always included, the real problem becomes:

Which two values should start the second and third subarrays to minimize the total cost?

For example:

[1, 2, 33, 44, 55, 5, 77, 3]

Even though the array looks large and messy, the minimum cost is:

1 + 2 + 3

Why?

• 1 → first subarray (always)
• 2 → second subarray
• 3 → third subarray

The exact shape of the subarrays doesn’t matter —

what matters is where the subarrays start, not how long they are.

---

Early Implementation (Accepted but Fragile)

My first solution worked and was accepted, but it was not robust.

I tried to manually manage indices to avoid conflicts when finding minimum values.

func minimumCost(nums []int) int {
    numLen := len(nums)
    if numLen < 3 {
        return 0 // array too short
    }

    sum := 0
    currentSum := 0

    // Handle first 3 elements directly
    for x := 0; x < 3; x++ {
        sum += nums[x]
        currentSum += nums[x]
    }

    if numLen > 3 {
        currentSum = nums[0]
        firstCheck := nums[1]
        idx := 1
        lastCheck := nums[1]

        // Find first minimum
        for x := 1; x < numLen; x++ {
            if firstCheck > nums[x] {
                firstCheck = nums[x]
                idx = x
            }
        }

        // Find second minimum (avoid index conflict)
        for x := 1; x < numLen; x++ {
            if x == idx {
                continue
            }
            if nums[x] < lastCheck {
                lastCheck = nums[x]
            }
        }

        currentSum += firstCheck + lastCheck
    }

    if currentSum < sum {
        sum = currentSum
    }

    return sum
}

Why I Needed the Index

Without tracking the index of the first minimum, both firstCheck and lastCheck could end up referencing the same value.

Example:

[2, 3, 4, 7, 3, 1]

Without index tracking:

• both minimums could incorrectly become 3 (same index)

With index tracking:

• first minimum = 1
• second minimum = 3

This solution passed, but it felt forced, duplicated logic, and was hard to reason about.

---

The Key Realization

Eventually, I realized something important:

I don’t need to simulate splitting the array at all.

As long as:

• the first subarray starts at index 0
• the other two start somewhere after it

I can always split the array like this:

[0 : i] | [i : j] | [j : n]

So the problem reduces to:

Find the two smallest values in nums[1:].

That’s it.

---

Final Refactored Solution (Clean & Optimal)

This part took me an additional 15 minutes to produce.

func minimumCost(nums []int) int {
    firstMin, lastMin := int(1e9), int(1e9)

    for x := 1; x < len(nums); x++ {
        num := nums[x]
        if num < firstMin {
            lastMin = firstMin
            firstMin = num
        } else if num < lastMin {
            lastMin = num
        }
    }

    return nums[0] + firstMin + lastMin
}

---

Why I initialised with a large number?

To find a minimum, you must compare against something larger than any possible input.

firstMin, lastMin := int(1e9), int(1e9)

This guarantees the first real value replaces them.

---

Understanding the else if Clause

Consider the array:

[1, 4, 8, 2]

We start scanning from index 1.

Step	num	firstMin	lastMin
init	—	∞	∞
4	4	4	∞
8	8	4	8
2	2	2	4

Explanation:

• If num < firstMin, the old firstMin becomes lastMin
• If num is not smaller than firstMin but smaller than lastMin, it becomes the second minimum

This maintains the invariant:

firstMin ≤ lastMin

at all times.

---

Final Takeaways

• nums[0] is always part of the cost → treat it as constant
• The problem is about choosing start indices, not subarrays
• You don’t need to split the array — the split is implicit
• A single-pass O(n) solution is enough

This problem taught me an important lesson:

When a problem looks structural, it’s often really about values.

Sometimes the clean solution only appears after you overthink it once.

---

Happy coding 🚀