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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count the Number of Good Partitions

Number: 3212

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an array of positive integers, count the total number of ways to partition the array into one or more contiguous subarrays (segments) such that no number appears in two different subarrays. In other words, if a number occurs more than once in the array, all of its occurrences must lie in the same partition. Since the answer can get large, return it modulo 10^9+7.

Key Insights

  • A partition is “good” if for every segment, if a number appears, then all its occurrences (from the entire array) are contained in that same segment.
  • For each number, record its first and last occurrence.
  • A valid (or “safe”) cut between indices i and i+1 is possible if no number spans across that boundary (i.e. for every number seen on the left side, its last occurrence is at or before i).
  • This observation is equivalent to the well-known “partition labels” idea: as you iterate from the beginning, keep track of the maximum last occurrence seen so far. When the current index equals this maximum, you have reached a boundary where a partition may end.
  • Each safe boundary gives you a binary decision: either place a partition cut there or not. Hence, if the number of safe boundaries is m, the total number of good partitions is 2^m (if no safe boundary is used then the whole array is taken as one partition).

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input array, since we make one pass to compute the last occurrence and one pass to count safe boundaries. Space Complexity: O(n) in the worst-case due to the hash table storing last occurrences.

Solution

We first compute the last occurrence for each unique number in the array. Then, we iterate over the array (except for the final element) and maintain a running maximum of the last occurrence indices encountered. If at any index i the running maximum equals i, it means that, for all numbers in the subarray from the last cut up to i, their last occurrence is ≤ i. Hence, a partition cut between i and i+1 is safe. Counting all such safe boundaries (say m), the answer is 2^m modulo (10^9+7). This combinatorial observation drastically simplifies the problem compared to trying to compute all valid segmentation positions by dynamic programming.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with detailed line-by-line comments.

# Define the modulo constant.
MOD = 10**9 + 7

def count_good_partitions(nums):
    n = len(nums)
    # Compute the last occurrence of each number.
    last_occurrence = {}
    for i, num in enumerate(nums):
        last_occurrence[num] = i

    safe_boundaries = 0
    current_max = 0
    # Iterate over the array from index 0 to n-2.
    # A boundary is considered only if it is not the end of the array.
    for i in range(n - 1):
        # Update the current maximum last occurrence for the segment so far.
        current_max = max(current_max, last_occurrence[nums[i]])
        # If current index equals current_max, a safe boundary is found.
        if i == current_max:
            safe_boundaries += 1

    # The total number of good partitions is 2^(safe_boundaries) mod MOD.
    result = pow(2, safe_boundaries, MOD)
    return result

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