Skip to main content
Talentd

Minimum Partition Score II - Solution & Explanation

HardPremiumFree on FleetCode4 min read
Practice this problem

Problem Statement

You are given an integer array nums and an integer k.

Your task is to partition nums into exactly k subarrays and return an integer denoting the minimum possible score among all valid partitions.

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

The value of a subarray is defined as sumArr * (sumArr + 1) / 2, where sumArr is the sum of its elements.

 

Example 1:

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

Output: 25

Explanation:

  • We must partition the array into k = 2 subarrays. One optimal partition is [5] and [1, 2, 1].
  • The first subarray has sum = 5 and value = 5 * 6 / 2 = 15.
  • The second subarray has sum = 1 + 2 + 1 = 4 and value = 4 * 5 / 2 = 10.
  • The score of this partition is 15 + 10 = 25, which is the minimum possible score.

Example 2:

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

Output: 55

Explanation:

  • Since we must partition the array into k = 1 subarray, all elements belong to the same subarray: [1, 2, 3, 4].
  • This subarray has sum = 1 + 2 + 3 + 4 = 10 and value = 10 * 11 / 2 = 55.​​​​​​​
  • The score of this partition is 55, which is the minimum possible score.

Example 3:

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

Output: 3

Explanation:

  • We must partition the array into k = 3 subarrays. The only valid partition is [1], [1], [1].
  • Each subarray has sum = 1 and value = 1 * 2 / 2 = 1.
  • The score of this partition is 1 + 1 + 1 = 3, which is the minimum possible score.

 

Constraints:

  • 1 <= nums.length <= 5 * 104
  • 1 <= nums[i] <= 103
  • 1 <= k <= nums.length

Approach Overview

Problem Overview: You are given an array and must split it into multiple contiguous partitions so that the total partition score is minimized. The score of each segment depends on values inside that subarray, so the challenge is choosing optimal cut points.

Approach 1: Brute Force Partition Enumeration (O(n^3) time, O(n) space)

The most direct method tries every possible partition configuration. For each index i, treat it as the end of the current segment and iterate over all possible starting points j. Compute the segment score for nums[j..i] and combine it with the best score before j. If computing segment scores requires scanning the subarray, each check costs O(n), leading to O(n^3) total complexity. This approach is useful for understanding the recurrence but becomes impractical for large inputs.

Approach 2: Dynamic Programming with Prefix Precomputation (O(n^2) time, O(n) space)

Define dp[i] as the minimum partition score for the prefix ending at index i. For each i, iterate backward through possible previous partition points j. The transition becomes dp[i] = min(dp[j] + score(j+1, i)). Precompute segment statistics using prefix sums or other auxiliary arrays so the score of any subarray can be evaluated in constant time. This reduces the runtime to O(n^2). Most accepted solutions rely on this DP structure because it is straightforward and handles general scoring functions.

Approach 3: Optimized DP with Segment Tree / Monotonic Structure (O(n log n) time, O(n) space)

When the partition score has monotonic or decomposable properties, the transition can be optimized. Maintain candidate transitions using a segment tree or monotonic structure that stores the best previous DP states. Instead of scanning all j for every i, query the data structure for the optimal value over a valid range. Each update and query costs O(log n), reducing the total complexity to O(n log n). This pattern commonly appears in advanced dynamic programming problems where transitions depend on range queries.

Recommended for interviews: The O(n^2) dynamic programming approach is usually expected. It clearly demonstrates the recurrence and correct state definition. Starting with the brute-force idea shows understanding of the partition structure, while moving to optimized DP demonstrates algorithmic maturity. If constraints are large, discussing a segment tree or monotonic optimization signals strong problem-solving depth.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Partition EnumerationO(n^3)O(n)Understanding the partition recurrence or when constraints are very small
Dynamic Programming with Prefix PrecomputationO(n^2)O(n)General solution that works for most scoring definitions
DP with Segment Tree / Range OptimizationO(n log n)O(n)Large constraints where DP transitions require efficient range minimum queries

Frequently Asked Questions

Is Minimum Partition Score II easy or hard?
Minimum Partition Score II is categorized as a hard problem because it combines partition-based dynamic programming with potential range optimization techniques. Efficient solutions require careful state design and sometimes advanced data structures.
Minimum Partition Score II Python/Java solution
Most implementations follow the same DP recurrence. Maintain a dp array where dp[i] stores the best score up to index i, iterate over previous partition points, and compute the segment score using prefix information. This structure translates directly into Python, Java, and C++ implementations.
How to solve Minimum Partition Score II in O(n log n)?
Optimize the DP transition using a range-query structure. Instead of checking every previous partition index, maintain candidate states inside a segment tree or similar structure. Each step performs a range minimum query and an update, resulting in O(log n) per index and O(n log n) overall complexity.
What is the best approach for Minimum Partition Score II?
Dynamic programming with prefix precomputation is the most practical approach. Define dp[i] as the minimum score for the prefix ending at i and evaluate all previous partition points. With constant-time segment score calculation using prefix arrays, the total complexity becomes O(n^2) time and O(n) space.
Is Minimum Partition Score II asked at Google/Amazon/Meta?
Partition-based dynamic programming problems appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the pattern of defining dp states over prefixes and optimizing transitions is commonly tested in hard interview rounds.
What data structure is used in Minimum Partition Score II?
The solution primarily relies on dynamic programming arrays. For optimized implementations, prefix sum arrays help compute segment scores quickly, and data structures like segment trees or monotonic stacks can accelerate range minimum queries.
What is the time complexity of Minimum Partition Score II?
The common dynamic programming solution runs in O(n^2) time with O(n) space. A naive brute-force solution can reach O(n^3) if segment scores require scanning each subarray. With advanced optimizations such as segment trees or monotonic structures, the complexity can improve to O(n log n).

Ready to solve this problem?

Practice Minimum Partition Score II with our built-in code editor and test cases.

Practice on FleetCode