We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count the Number of Good Partitions

Difficulty: Hard

Problem Description

You are given a 0-indexed array nums consisting of positive integers. A partition of an array into one or more contiguous subarrays is called good if no two subarrays contain the same number. Return the total number of good partitions of nums. Since the answer may be large, return it modulo 10^9 + 7.

Key Insights

  • A partition is good if it contains unique elements in each subarray.
  • The problem can be approached using dynamic programming to count the number of valid partitions.
  • The last occurrence of each number can be tracked to ensure no duplicates in partitions.
  • The solution involves combinatorics to calculate the total number of ways to partition the array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we will utilize dynamic programming. We maintain a dp array where dp[i] represents the number of good partitions for the subarray nums[0:i]. We will also use a hash map to track the last occurrence of each number in the array. For each position i, we will determine the valid partitions by considering the last position where the current number occurred, ensuring that we do not double count partitions that would lead to duplicates.

Code Solutions

def count_good_partitions(nums):
    MOD = 10**9 + 7
    n = len(nums)
    dp = [0] * (n + 1)
    dp[0] = 1  # Base case: one way to partition an empty array
    last_occurrence = {}

    for i in range(1, n + 1):
        num = nums[i - 1]
        dp[i] = dp[i - 1]  # We can always extend the previous partitions
        if num in last_occurrence:
            j = last_occurrence[num]
            dp[i] = (dp[i] - dp[j - 1] + MOD) % MOD  # Subtract partitions ending before last occurrence
        last_occurrence[num] = i  # Update last occurrence
        dp[i] = (dp[i] + MOD) % MOD  # Ensure dp[i] is non-negative

    return dp[n]

# Example usage:
# print(count_good_partitions([1, 2, 3, 4]))  # Output: 8
← Back to All Questions