#2518

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Great Partitions

Calculate the number of great partitions of an array using state transition dynamic programming with careful sum constraints.

array dynamic programming

Problem Statement

Given an array nums of positive integers and an integer k, divide nums into two ordered groups where each element belongs to exactly one group. A partition is considered great if the sum of elements in each group is at least k.

Return the total number of distinct great partitions modulo 10^9 + 7. If it is impossible to form such partitions because the array sum is less than 2*k, return 0. Optimize the solution using dynamic programming to handle larger arrays efficiently.

Examples

Example 1

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

Output: 6

The great partitions are: ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) and ([4], [1,2,3]).

Example 2

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

Output: 0

There are no great partitions for this array.

Example 3

Input: nums = [6,6], k = 2

Output: 2

We can either put nums[0] in the first partition or in the second partition. The great partitions will be ([6], [6]) and ([6], [6]).

Constraints

1 <= nums.length, k <= 1000
1 <= nums[i] <= 109

Solution Approach

Dynamic Programming Setup

Define a DP array where dp[s] represents the number of subsets with sum equal to s. Iterate through each number and update dp using state transitions to avoid double counting subsets.

Counting Complementary Partitions

After filling the DP array, compute the number of great partitions by considering subsets whose sum is less than k and subtract from the total 2^n possibilities. This ensures that both partitions meet the k threshold.

Modulo and Edge Cases

Apply modulo 10^9 + 7 at every addition to prevent overflow. Check if the total sum of nums is smaller than 2*k; if so, return 0 immediately to handle impossible partition scenarios.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the array length and k, typically O(n*k) for DP updates. Space complexity is O(k) for storing feasible subset sums, optimized by using rolling arrays.

What Interviewers Usually Probe

Candidate recognizes the sum threshold failure mode when total sum is less than 2*k.
Candidate proposes DP state representing subset sums rather than brute force enumeration.
Candidate considers modulo arithmetic to manage large output and prevent overflow errors.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the sum < 2*k edge case leads to incorrect zero partitions.
Double counting subsets if state transitions are not carefully handled.
Ignoring the modulo operation can cause integer overflow on large arrays.

Follow-up variants

Count partitions into three groups each with sum at least k.
Find great partitions when order of elements in each group does not matter.
Calculate partitions with sum exactly equal to k instead of at least k.

FAQ

What is the best approach to solve Number of Great Partitions?

Use state transition dynamic programming to track subset sums and compute the number of partitions that meet the sum threshold for each group.

Why do we need modulo 10^9 + 7 in this problem?

The number of great partitions can be extremely large, so modulo arithmetic prevents integer overflow and keeps results manageable.

How does the total sum being less than 2*k affect the solution?

If the total sum is less than 2*k, it's impossible to form two partitions each with sum >= k, so the answer is 0.

Can this approach handle large nums arrays efficiently?

Yes, by using dynamic programming with subset sums and rolling arrays, time and space complexity are optimized for larger arrays.

What pattern does Number of Great Partitions exemplify?

It exemplifies the state transition dynamic programming pattern for counting subset sums under constraints.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        if sum(nums) < k * 2:
            return 0
        mod = 10**9 + 7
        n = len(nums)
        f = [[0] * k for _ in range(n + 1)]
        f[0][0] = 1
        ans = 1
        for i in range(1, n + 1):
            ans = ans * 2 % mod
            for j in range(k):
                f[i][j] = f[i - 1][j]
                if j >= nums[i - 1]:
                    f[i][j] = (f[i][j] + f[i - 1][j - nums[i - 1]]) % mod
        return (ans - sum(f[-1]) * 2 + mod) % mod

Continue Practicing

#2501 longest square streak in an array #2538 difference between maximum and minimum price sum #2547 minimum cost to split an array