LeetCode 2963 - Count the Number of Good Partitions

LeetCode Problem 2963

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Math, Combinatorics

Solution

Problem Understanding

The problem asks us to count the number of ways we can partition a given array nums of positive integers into contiguous subarrays such that no number appears in more than one subarray. Each partition must maintain the original order of elements, and two partitions are considered different if the subarrays are split at different positions, even if the numbers themselves are the same. The result must be returned modulo $10^9 + 7$.

The input array nums can be up to $10^5$ elements long, and the values in nums can be up to $10^9$. The constraints imply that a brute-force approach enumerating all partitions would be far too slow due to exponential growth with array length.

Important edge cases include arrays where all elements are identical (only one partition is possible), arrays with all unique elements (maximal number of partitions), and arrays where duplicates appear sporadically, forcing careful splitting.

Approaches

The brute-force approach would involve generating all possible contiguous partitions of the array, checking for each partition whether any number is repeated across subarrays. This is guaranteed to be correct but infeasible, because the number of possible partitions of an array of length $n$ is $2^{n-1}$, which is astronomical for $n \approx 10^5$.

The optimal approach relies on the observation that a good partition is determined by the frequency of each number. If a number appears more than once, it must appear entirely within a single subarray in any valid partition. Therefore, any number that appears more than half the length of the array immediately limits the number of partitions to one: the entire array itself. Otherwise, we can use combinatorics: given the frequency distribution of each number, we can count partitions using powers of 2 representing choices of splitting between positions that do not violate the "unique per subarray" constraint. Dynamic programming or a simplified combinatorial formula can be applied to efficiently compute the result modulo $10^9 + 7$.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Enumerate all partitions and check validity; infeasible for n=10^5
Optimal	O(n)	O(n)	Count frequency of numbers and compute partitions based on combinatorial constraints

Algorithm Walkthrough

1. Compute the frequency count of each number in the array using a hash map. This helps identify numbers that constrain partitions.
2. Check if any number appears more than half the length of the array. If yes, only the whole array itself can be a valid partition. Return 1 modulo $10^9 + 7$.
3. Otherwise, compute the total number of valid partitions using powers of 2. Each position between elements can either be a split or not, subject to the constraint that a split cannot separate two occurrences of the same number.
4. Iterate through the array while maintaining the latest index of each number. This ensures that we only consider splits that respect uniqueness in subarrays.
5. Use modular arithmetic to compute the final count modulo $10^9 + 7$.

Why it works: By ensuring that splits occur only between elements that do not share duplicates in different subarrays, and by tracking the last occurrence of each number, we guarantee that each partition satisfies the "good partition" definition. The modulo ensures we handle large counts safely.

Python Solution

from typing import List

class Solution:
    def numberOfGoodPartitions(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        from collections import Counter
        
        n = len(nums)
        freq = Counter(nums)
        
        # If any number occurs more than half of n, only one partition is valid
        if any(count > n // 2 for count in freq.values()):
            return 1
        
        # We can use dynamic programming to count partitions
        dp = [0] * (n + 1)
        dp[0] = 1
        last_seen = {}
        sum_dp = 1
        
        for i in range(1, n + 1):
            num = nums[i - 1]
            if num in last_seen:
                # remove dp value before last occurrence to avoid duplicates in subarrays
                sum_dp -= dp[last_seen[num]]
            dp[i] = sum_dp % MOD
            sum_dp = (sum_dp + dp[i]) % MOD
            last_seen[num] = i - 1
        
        return dp[n]

Explanation: We first handle the trivial case where a number occurs more than half of the array. Otherwise, we use dynamic programming, where dp[i] counts the number of good partitions ending at position i. last_seen helps enforce uniqueness by preventing splits that would repeat a number in multiple subarrays. We maintain sum_dp to quickly compute cumulative sums for DP transitions.

Go Solution

package main

func numberOfGoodPartitions(nums []int) int {
    const MOD = 1_000_000_007
    n := len(nums)
    
    freq := make(map[int]int)
    for _, num := range nums {
        freq[num]++
    }
    
    for _, count := range freq {
        if count > n/2 {
            return 1
        }
    }
    
    dp := make([]int, n+1)
    dp[0] = 1
    lastSeen := make(map[int]int)
    sumDP := 1
    
    for i := 1; i <= n; i++ {
        num := nums[i-1]
        if idx, ok := lastSeen[num]; ok {
            sumDP -= dp[idx]
            if sumDP < 0 {
                sumDP += MOD
            }
        }
        dp[i] = sumDP % MOD
        sumDP = (sumDP + dp[i]) % MOD
        lastSeen[num] = i - 1
    }
    
    return dp[n]
}

Explanation: The Go version mirrors the Python solution. We use map[int]int for counting and tracking last occurrences. We handle negative values during modulo subtraction carefully. Slices in Go naturally replace Python lists, and we maintain DP and cumulative sums similarly.

Worked Examples

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

All elements are unique. dp values propagate by including or not including splits, resulting in dp[4] = 8.

i	num	dp[i]	sumDP	lastSeen
1	1	1	2	{1:0}
2	2	2	4	{1:0,2:1}
3	3	4	8	{1:0,2:1,3:2}
4	4	8	16	{1:0,2:1,3:2,4:3}

Example 2: nums = [1,1,1,1]

1 occurs more than half the time, so result is 1.

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

Tracking lastSeen prevents splitting between duplicates, resulting in 2 valid partitions.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate once through the array, updating DP and lastSeen maps.
Space	O(n)	DP array of size n+1 and hash map storing last occurrences, at most n keys.

The DP-based approach ensures linear time processing despite the combinatorial nature of partitions.

Test Cases

# Provided examples
assert Solution().numberOfGoodPartitions([1,2,3,4]) == 8  # all unique elements
assert Solution().numberOfGoodPartitions([1,1,1,1]) == 1  # all identical elements
assert Solution().numberOfGoodPartitions([1,2,1,3]) == 2  # mix of duplicates and unique

# Edge and stress cases
assert Solution().numberOfGoodPartitions([1]) == 1  # single element
assert Solution().numberOfGoodPartitions([1,2]) == 2  # two unique elements
assert Solution().numberOfGoodPartitions([1,1,2,2]) == 2  # two duplicates, each can be grouped
assert Solution().numberOfGoodPartitions([i for i in range(1, 20)]) == 524288  # many unique elements

Test	Why
[1,2,3,4]	All elements unique, maximal partitions
[1,1,1,1]	All elements identical, only one partition possible
[1,2,1,3]	Duplicates enforce careful splitting
[1]	Minimum input size
[1,2]	Small array with all unique elements
[1,1,2,2]	Each duplicate constrains splitting
range(1,20)	Stress test for multiple unique elements

Edge Cases

1. All identical numbers: If nums = [x, x, ..., x], no internal split is allowed because it would duplicate x. The implementation returns 1 correctly.
2. All unique numbers: Any split is allowed. The DP accumulates all combinations of splits, yielding $2^{n-1}$ partitions.
3. **Numbers repeating sparsely