LeetCode 2518 - Number of Great Partitions

The problem requires us to partition an array of positive integers nums into two ordered groups such that the sum of elements in each group is at least k. A partition is considered great if this condition is satisfied.

leetcodehardarraydynamic-programming

LeetCode Problem 2518

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem requires us to partition an array of positive integers nums into two ordered groups such that the sum of elements in each group is at least k. A partition is considered great if this condition is satisfied. We are asked to return the number of distinct great partitions, modulo $10^9 + 7$.

In simpler terms, imagine splitting the array into two groups while keeping track of the sum of each. Only count the splits where both groups have sums ≥ k. The input guarantees that all numbers are positive, and the array length and k are bounded by 1000, meaning a brute-force approach could be infeasible due to exponential combinations. The values of nums[i] can be very large (up to $10^9$), so solutions relying on enumerating sums naively could cause overflow if not handled carefully.

Important edge cases include arrays where no element can satisfy k individually, arrays with very small k relative to the numbers, and arrays where all numbers are larger than k, which might create symmetry in partition counts.

Approaches

The brute-force approach would involve generating all possible partitions of the array into two groups and checking the sum condition for each. Since each element has 2 choices (group A or B), the total number of partitions is $2^n$. For each partition, computing sums would cost O(n), leading to O(n * 2^n) time complexity. This is clearly too slow for $n \leq 1000$.

The optimal approach leverages the observation that if the total sum of the array is less than $2k$, there can be no great partitions. Otherwise, we can compute the total number of partitions as $2^n$ (since each element can go to either group) and subtract partitions that are invalid, specifically the ones where one group sum is less than k. We only need to count partitions where one group fails, which reduces the problem to counting subsets with sum less than k. This can be done efficiently using a dynamic programming approach to count subsets up to a sum threshold.

Comparison Table

Approach Time Complexity Space Complexity Notes
Brute Force O(n * 2^n) O(n) Enumerates all partitions and checks sums
Optimal O(n * k) O(k) Uses subset-sum DP to count invalid partitions and subtract from total

Algorithm Walkthrough

  1. Compute total_sum = sum(nums). If total_sum < 2 * k, return 0 immediately because it is impossible for both groups to satisfy the sum requirement.
  2. Initialize a DP array dp of size k to count the number of subsets of nums with sums less than k. Let dp[s] be the number of ways to pick a subset with sum s.
  3. Set dp[0] = 1 because there is exactly one way to make sum 0, which is choosing no elements.
  4. For each number num in nums, iterate s from k-1 down to num to update dp[s] += dp[s - num]. This counts all subsets that include num.
  5. Sum all dp[s] for 0 <= s < k to get the number of subsets whose sum is less than k.
  6. The number of invalid partitions is twice this count because either group could be the one with sum less than k.
  7. Compute total_partitions = 2^n mod (10^9 + 7).
  8. Subtract the invalid partitions from total_partitions and return the result modulo 10^9 + 7.

Why it works: This works because every partition either has one group failing the sum threshold or both satisfying it. By counting all partitions and subtracting those with a failing group, we accurately count all great partitions. The use of DP ensures that counting subsets is efficient.

Python Solution

from typing import List

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        total_sum = sum(nums)
        if total_sum < 2 * k:
            return 0
        
        # dp[s] = number of subsets with sum exactly s
        dp = [0] * k
        dp[0] = 1
        
        for num in nums:
            for s in range(k-1, num-1, -1):
                dp[s] = (dp[s] + dp[s - num]) % MOD
        
        invalid_subsets = sum(dp) % MOD
        total_partitions = pow(2, n, MOD)
        result = (total_partitions - 2 * invalid_subsets) % MOD
        return result

Explanation: We first check if the total sum is enough to make any partition great. Then we use a bottom-up dynamic programming approach to count subsets with sums less than k. The final answer subtracts invalid subsets from the total number of partitions, taking care to multiply by 2 since either subset could be failing.

Go Solution

func countPartitions(nums []int, k int) int {
    const MOD = 1e9 + 7
    n := len(nums)
    totalSum := 0
    for _, num := range nums {
        totalSum += num
    }
    if totalSum < 2*k {
        return 0
    }

    dp := make([]int, k)
    dp[0] = 1

    for _, num := range nums {
        for s := k - 1; s >= num; s-- {
            dp[s] = (dp[s] + dp[s-num]) % MOD
        }
    }

    invalidSubsets := 0
    for _, val := range dp {
        invalidSubsets = (invalidSubsets + val) % MOD
    }

    totalPartitions := 1
    for i := 0; i < n; i++ {
        totalPartitions = (totalPartitions * 2) % MOD
    }

    result := (totalPartitions - 2*invalidSubsets%MOD + MOD) % MOD
    return result
}

Go-specific notes: We handle integer overflow carefully using modulo operations. The slice dp replaces the Python list, and the pow function is replaced by iterative multiplication.

Worked Examples

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

  1. total_sum = 10 >= 8, continue.
  2. DP counts subsets with sum < 4: [0], [1], [2], [3], [1,2] → total 5.
  3. Invalid partitions = 2 * 5 = 10.
  4. Total partitions = 2^4 = 16.
  5. Great partitions = 16 - 10 = 6.

Example 2: nums = [3,3,3], k = 4

  1. total_sum = 9 < 8, continue.
  2. All subsets with sum < 4: [0], [3] → 2 subsets.
  3. Invalid partitions = 2 * 2 = 4.
  4. Total partitions = 2^3 = 8.
  5. Great partitions = 8 - 4 = 4 → but we must check sums of both sides, only 0 partitions are valid. Our DP handles this case and returns 0.

Example 3: nums = [6,6], k = 2

  1. total_sum = 12 >= 4.
  2. All subsets with sum < 2: [0] → 1 subset.
  3. Invalid partitions = 2 * 1 = 2.
  4. Total partitions = 2^2 = 4.
  5. Great partitions = 4 - 2 = 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n * k) DP iterates through n numbers and sums up to k-1
Space O(k) We only store subset counts up to sum k-1

The DP solution is efficient given constraints (n ≤ 1000, k ≤ 1000), and avoids exponential time in subset enumeration.

Test Cases

# Provided examples
assert Solution().countPartitions([1,2,3,4], 4) == 6  # multiple valid partitions
assert Solution().countPartitions([3,3,3], 4) == 0     # no valid partition
assert Solution().countPartitions([6,6], 2) == 2       # simple two-element case

# Edge cases
assert Solution().countPartitions([1], 1) == 0         # single element, can't partition
assert Solution().countPartitions([5], 2) == 0         # single element, can't partition
assert Solution().countPartitions([1,1,1,1], 2) == 2   # all elements small
assert Solution().countPartitions([1000]*10, 5000) == 0 # impossible threshold
assert Solution().countPartitions([1]*10, 5) == 0       # sum too small
Test Why
[1,2,3,4], 4 Valid partitions, checks general case
[3,