LeetCode Problem 3826

Difficulty: 🔴 Hard
Topics: Array, Divide and Conquer, Dynamic Programming, Queue, Prefix Sum, Monotonic Queue

Solution

LeetCode 3826 - Minimum Partition Score

Problem Understanding

We are given an array nums and must divide it into exactly k contiguous subarrays.

For every subarray, we first compute its sum:

$$\text{sumArr} = \sum \text{elements in the subarray}$$

Its value is then defined as:

$$\text{value} = \frac{\text{sumArr} \cdot (\text{sumArr}+1)}{2}$$

The score of a partition is the sum of the values of all subarrays in that partition.

Our goal is to find the minimum possible score among all ways to partition the array into exactly k contiguous pieces.

The input consists of:

• nums, the array to partition.
• k, the exact number of subarrays required.

The output is a single integer representing the minimum achievable partition score.

The constraints are important:

• n = len(nums) can be as large as 1000.
• Every element is positive.
• k can also be as large as 1000.

A brute force search over all partitions is impossible because the number of ways to place partition boundaries grows exponentially.

Several edge cases are worth noticing immediately:

• k = 1, the entire array must remain one segment.
• k = n, every element becomes its own segment.
• Large values of nums[i] make segment sums large, so intermediate calculations require 64-bit integers.
• Since all numbers are positive, prefix sums are strictly increasing, which becomes a crucial property for the optimal solution.

Approaches

Brute Force

A straightforward solution is to try every possible placement of the k-1 partition boundaries.

For each partition:

1. Compute every segment sum.
2. Compute its value using the triangular-number formula.
3. Sum all segment values.
4. Keep the minimum.

This approach is correct because it examines every valid partition.

However, there are:

$$\binom{n-1}{k-1}$$

possible partitions, which is exponential in the worst case. Even for moderate values of n, this becomes completely infeasible.

Key Observation

Let:

$$P[i]$$

be the prefix sum of the first i elements.

Then the sum of a segment (j+1 \ldots i) is:

$$P[i]-P[j]$$

Its cost is:

$$C(j,i) = \frac{(P[i]-P[j])\big((P[i]-P[j])+1\big)}{2}$$

A natural dynamic programming formulation is:

$$dp[t][i] = \min_{j<i} \left( dp[t-1][j] + C(j,i) \right)$$

where:

• t = number of segments used.
• i = first i elements covered.

The crucial step is expanding the cost function:

$$C(j,i) = \frac{ (P[i]-P[j])^2 + (P[i]-P[j]) }{2}$$

Expanding gives:

$$C(j,i) = \frac{P[i]^2+P[i]}{2} + \frac{P[j]^2-P[j]}{2} - P[i]P[j]$$

Now the transition becomes:

$$dp[t][i] = A(i) + \min_j \Big( dp[t-1][j] + B(j) - P[i]P[j] \Big)$$

where:

$$A(i)=\frac{P[i]^2+P[i]}{2}$$

$$B(j)=\frac{P[j]^2-P[j]}{2}$$

Notice that for a fixed j:

$$(dp[t-1][j]+B(j)) + (-P[j]) \cdot P[i]$$

is a line evaluated at:

$$x=P[i]$$

Therefore each previous state contributes a line:

$$y=mx+b$$

with:

$$m=-P[j]$$

$$b=dp[t-1][j]+B(j)$$

We must repeatedly query the minimum line value at increasing x = P[i].

Because all array elements are positive, prefix sums are strictly increasing. This means:

• Slopes are inserted in monotonic order.
• Query points arrive in monotonic order.

This allows a monotonic Convex Hull Trick implementation in O(1) amortized time per operation.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(k)	Tries every partition
Optimal	O(kn)	O(n)	DP + Convex Hull Trick

Algorithm Walkthrough

1. Compute prefix sums P.
2. Define DP state:

$$dp[t][i]$$

as the minimum score for partitioning the first i elements into exactly t segments. 3. Initialize:

• dp[0][0] = 0
• All other states are infinity.

4. Process segment counts from 1 to k.
5. For each layer t, create an empty convex hull.
6. Insert the line corresponding to j = t-1, because this is the smallest valid split position for a partition using t segments.
7. Iterate i from t to n.
8. Query the hull at:

$$x=P[i]$$

obtaining:

$$\min_j \Big( dp[t-1][j] + B(j) - P[i]P[j] \Big)$$ 9. Add:

$$A(i)$$

to obtain dp[t][i]. 10. After computing dp[t][i], insert the line corresponding to position j=i so that future states may use it. 11. After finishing all layers, return dp[k][n].

Why it works

The DP recurrence considers every valid last partition boundary j. The algebraic expansion separates the transition into an i-dependent part and a linear function of P[i]. Every possible split position becomes a line in a convex hull. Since all valid transitions are represented and the hull always returns the minimum line value at each query point, every DP state receives exactly the minimum transition cost. Therefore the final answer equals the minimum score among all valid partitions.

Python Solution

from collections import deque
from typing import List

class Solution:
    def minPartitionScore(self, nums: List[int], k: int) -> int:
        n = len(nums)

        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        INF = 10**30

        dp_prev = [INF] * (n + 1)
        dp_prev[0] = 0

        class Line:
            __slots__ = ("m", "b")

            def __init__(self, m: int, b: int):
                self.m = m
                self.b = b

            def value(self, x: int) -> int:
                return self.m * x + self.b

        def bad(l1: Line, l2: Line, l3: Line) -> bool:
            return (
                (l3.b - l1.b) * (l1.m - l2.m)
                <= (l2.b - l1.b) * (l1.m - l3.m)
            )

        for t in range(1, k + 1):
            dp_cur = [INF] * (n + 1)
            hull = deque()

            j = t - 1
            if dp_prev[j] < INF:
                b = dp_prev[j] + (prefix[j] * prefix[j] - prefix[j]) // 2
                hull.append(Line(-prefix[j], b))

            for i in range(t, n + 1):
                x = prefix[i]

                while (
                    len(hull) >= 2
                    and hull[0].value(x) >= hull[1].value(x)
                ):
                    hull.popleft()

                best = hull[0].value(x)
                a = (x * x + x) // 2
                dp_cur[i] = a + best

                if dp_prev[i] < INF:
                    new_line = Line(
                        -prefix[i],
                        dp_prev[i]
                        + (prefix[i] * prefix[i] - prefix[i]) // 2,
                    )

                    while (
                        len(hull) >= 2
                        and bad(hull[-2], hull[-1], new_line)
                    ):
                        hull.pop()

                    hull.append(new_line)

            dp_prev = dp_cur

        return dp_prev[n]

Implementation Explanation

The prefix-sum array allows every segment sum to be computed in constant time.

The DP is performed layer by layer. Instead of storing the entire k × n table, only the previous layer and current layer are needed, reducing memory usage to O(n).

Each valid split position j generates a line:

$$y = -P[j] \cdot x + dp[t-1][j] + \frac{P[j]^2-P[j]}{2}$$

These lines are maintained in a monotonic convex hull. Since prefix sums are strictly increasing, slopes are inserted in sorted order and query points also arrive in sorted order. This enables the classic deque-based Convex Hull Trick with amortized constant-time insertions and queries.

The value returned by the hull is combined with:

$$\frac{P[i]^2+P[i]}{2}$$

to obtain the final DP transition value.

Go Solution

package main

import "math"

type Line struct {
	m int64
	b int64
}

func (l Line) value(x int64) int64 {
	return l.m*x + l.b
}

func bad(l1, l2, l3 Line) bool {
	return (l3.b-l1.b)*(l1.m-l2.m) <= (l2.b-l1.b)*(l1.m-l3.m)
}

func minPartitionScore(nums []int, k int) int64 {
	n := len(nums)

	prefix := make([]int64, n+1)
	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + int64(nums[i])
	}

	const INF int64 = math.MaxInt64 / 4

	dpPrev := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		dpPrev[i] = INF
	}

	for t := 1; t <= k; t++ {
		dpCur := make([]int64, n+1)
		for i := range dpCur {
			dpCur[i] = INF
		}

		hull := make([]Line, 0)

		j := t - 1
		if dpPrev[j] < INF {
			b := dpPrev[j] + (prefix[j]*prefix[j]-prefix[j])/2
			hull = append(hull, Line{-prefix[j], b})
		}

		head := 0

		for i := t; i <= n; i++ {
			x := prefix[i]

			for len(hull)-head >= 2 &&
				hull[head].value(x) >= hull[head+1].value(x) {
				head++
			}

			best := hull[head].value(x)
			a := (x*x + x) / 2
			dpCur[i] = a + best

			if dpPrev[i] < INF {
				newLine := Line{
					-prefix[i],
					dpPrev[i] + (prefix[i]*prefix[i]-prefix[i])/2,
				}

				for len(hull)-head >= 2 &&
					bad(hull[len(hull)-2], hull[len(hull)-1], newLine) {
					hull = hull[:len(hull)-1]
				}

				hull = append(hull, newLine)
			}
		}

		dpPrev = dpCur
	}

	return dpPrev[n]
}

Go-Specific Notes

Go uses int64 throughout because segment sums can become large and the quadratic cost function can exceed the range of a 32-bit integer.

The convex hull is implemented with a slice and a moving head pointer instead of a deque. This avoids expensive front removals while preserving amortized constant-time operations.

Worked Examples

Example 1

Input:

nums = [5,1,2,1]
k = 2

Prefix sums:

i	P[i]
0	0
1	5
2	6
3	8
4	9

After computing the first DP layer:

i	dp[1][i]
1	15
2	21
3	36
4	45

Now compute the second layer.

For i=4, the candidate splits are:

Split j	Partition	Cost
1	[5] [1,2,1]	15 + 10 = 25
2	[5,1] [2,1]	21 + 6 = 27
3	[5,1,2] [1]	36 + 1 = 37

Minimum:

25

Answer:

25

Example 2

Input:

nums = [1,2,3,4]
k = 1

Prefix sum:

10

Only one segment exists.

Value:

$$\frac{10 \cdot 11}{2} = 55$$

Answer:

55

Example 3

Input:

nums = [1,1,1]
k = 3

Every element must form its own segment.

Each segment:

$$\frac{1\cdot2}{2}=1$$

Total:

1 + 1 + 1 = 3

Answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(kn)	Each DP layer performs O(n) hull insertions and O(n) hull queries
Space	O(n)	Only two DP rows and one convex hull are stored

The key observation is that every line enters the convex hull exactly once and leaves it at most once. Similarly, each query removes obsolete lines only once. Therefore the convex hull operations are amortized constant time, yielding O(kn) total complexity.

Test Cases

sol = Solution()

assert sol.minPartitionScore([5, 1, 2, 1], 2) == 25      # example 1
assert sol.minPartitionScore([1, 2, 3, 4], 1) == 55      # example 2
assert sol.minPartitionScore([1, 1, 1], 3) == 3          # example 3

assert sol.minPartitionScore([7], 1) == 28              # single element
assert sol.minPartitionScore([1, 1], 1) == 3            # no split
assert sol.minPartitionScore([1, 1], 2) == 2            # every element separate

assert sol.minPartitionScore([10, 10, 10], 3) == 165    # all singleton segments

assert sol.minPartitionScore([1, 2, 3], 2) == 10        # optimal internal split

assert sol.minPartitionScore([10000] * 10, 10) == 500050000  # large values

assert sol.minPartitionScore([2, 3, 5, 7, 11], 5) == (
    3 + 6 + 15 + 28 + 66
)  # k = n

Test Summary

Test	Why
[5,1,2,1], k=2	Official example
[1,2,3,4], k=1	Entire array must remain one segment
[1,1,1], k=3	Every element isolated
[7], k=1	Smallest possible input
[1,1], k=1	No partition allowed
[1,1], k=2	Maximum partition count for length 2
[10,10,10], k=3	All singleton segments
[1,2,3], k=2	Verifies nontrivial split choice
Large values	Checks 64-bit arithmetic
k=n case	Verifies boundary behavior

Edge Cases

When k = 1

The entire array must be treated as a single segment. A buggy implementation might still attempt to place partition boundaries. The DP initialization correctly handles this case because only transitions from dp[0][0] are valid, producing exactly one segment covering the entire array.

When k = n

Every element must become its own segment. This is a common source of indexing mistakes because only one split position is valid at each step. The implementation enforces valid split positions through the j >= t-1 condition, ensuring the DP never creates empty segments.

Large Segment Sums

Since nums[i] can be as large as 10^4 and there can be 1000 elements, prefix sums may reach 10^7. The cost formula contains a square term, producing values around 10^14. Using 32-bit integers would overflow. Both implementations use 64-bit arithmetic for all cost computations, guaranteeing correctness.