# Count the Number of Good Partitions
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-the-number-of-good-partitions)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-good-partitions
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Data structures:** Array, Hash Table
---
## Problem
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** `109 + 7`.

**Example 1:**

**Input:** nums = [1,2,3,4]
**Output:** 8
**Explanation:** The 8 possible good partitions are: ([1], [2], [3], [4]), ([1], [2], [3,4]), ([1], [2,3], [4]), ([1], [2,3,4]), ([1,2], [3], [4]), ([1,2], [3,4]), ([1,2,3], [4]), and ([1,2,3,4]).

**Example 2:**

**Input:** nums = [1,1,1,1]
**Output:** 1
**Explanation:** The only possible good partition is: ([1,1,1,1]).

**Example 3:**

**Input:** nums = [1,2,1,3]
**Output:** 2
**Explanation:** The 2 possible good partitions are: ([1,2,1], [3]) and ([1,2,1,3]).

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute-Force with Split Point Checking
A brute-force approach can be devised by considering every possible split point in the array. A partition is defined by a set of split points. A partition is 'good' if for any two of its subarrays, the sets of numbers they contain are disjoint. This property implies that any valid split point `i` must separate the array into two parts, `nums[0...i]` and `nums[i+1...n-1]`, that have no numbers in common.

This approach iterates through all `n-1` potential split points. For each point `i`, it explicitly constructs the set of numbers in the prefix and checks for any overlap with the numbers in the suffix. If `c` such valid split points are found, they define `c+1` minimal blocks that cannot be internally divided. The problem then becomes counting the ways to partition these blocks. With `c` locations between blocks where a split can occur, and two choices at each (split or not split), the total number of good partitions is `2^c`.
**Time:** O(N^2), where N is the length of the array. The outer loop runs N-1 times, and for each iteration, the inner loops for building the set and checking for disjointness take O(N) time in total. · **Space:** O(N) in the worst case, as the hash set can store up to N unique elements within the loop.
**Pros:** Simple to understand and implement based on the problem definition.
**Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will result in a Time Limit Exceeded error.
### Explanation
This approach directly implements the definition of a valid split point. We iterate through every index `i` from `0` to `n-2` and test if we can make a cut after `nums[i]`. To test this, we need to verify that no number appearing in `nums[0...i]` also appears in `nums[i+1...n-1]`. A straightforward way to do this is to use hash sets. For each `i`, we build a hash set of numbers in the prefix `nums[0...i]`. Then, we iterate through the suffix `nums[i+1...n-1]` and check if any of its elements exist in our hash set. If we find no common elements, we've identified a valid split point and we increment a counter. After checking all `n-1` potential points, if we have found `c` valid split points, the total number of good partitions will be `2^c`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countGoodPartitions(int[] nums) {
        long MOD = 1_000_000_007;
        int n = nums.length;
        if (n == 1) {
            return 1;
        }

        int splitPoints = 0;
        for (int i = 0; i < n - 1; i++) {
            Set<Integer> prefixNums = new HashSet<>();
            for (int j = 0; j <= i; j++) {
                prefixNums.add(nums[j]);
            }

            boolean isDisjoint = true;
            for (int j = i + 1; j < n; j++) {
                if (prefixNums.contains(nums[j])) {
                    isDisjoint = false;
                    break;
                }
            }

            if (isDisjoint) {
                splitPoints++;
            }
        }

        return (int) power(2, splitPoints, MOD);
    }

    private long power(long base, int exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
- Initialize a variable `split_points` to 0.
- Iterate through each possible split index `i` from `0` to `n-2`, where `n` is the length of `nums`.
- For each `i`, check if a split is valid. A split is valid if the set of numbers in `nums[0...i]` is disjoint from the set of numbers in `nums[i+1...n-1]`.
- To perform the check:
  - Create a hash set for the prefix `nums[0...i]`.
  - Iterate through the suffix `nums[i+1...n-1]` and check if any of its elements are present in the prefix's hash set.
- If the sets are disjoint, increment `split_points`.
- After checking all possible split indices, the total number of good partitions is `2^split_points`.
- Calculate this value modulo `10^9 + 7` using modular exponentiation.

## Greedy Approach with Last Occurrence Map
A more efficient approach uses a greedy strategy. The core insight is that for a partition to be 'good', all occurrences of any given number must belong to the same subarray. This allows us to group elements into minimal contiguous blocks that cannot be split internally.

A split is possible after an index `i` if and only if every number that has appeared in `nums[0...i]` does not appear again in `nums[i+1...n-1]`. This condition is met if the last occurrence of every number in `nums[0...i]` is at an index less than or equal to `i`.

We can find these minimal blocks in a single pass. We iterate through the array while keeping track of the maximum last occurrence index (`max_reach`) of all numbers encountered so far. When our current index `i` equals `max_reach`, it means we have found the end of a valid block. The segment from the start of the current block to `i` contains all occurrences of its numbers.

If we decompose the array into `k` such blocks, there are `k-1` boundaries between them. At each boundary, we can either place a split or not. This gives `2^(k-1)` possible good partitions.
**Time:** O(N), where N is the length of `nums`. Populating the hash map takes O(N), the main loop takes O(N), and modular exponentiation takes O(log N). The total complexity is dominated by the linear scans. · **Space:** O(U), where U is the number of unique elements in `nums`. This is for the hash map storing the last occurrences. In the worst case, U can be N.
**Pros:** Highly efficient with a linear time complexity, which passes the given constraints.; Solves the problem with a single pass after pre-computation, making it very fast.
**Cons:** Requires extra space for the hash map, which can be up to O(N) if all elements are unique.
### Explanation
This optimal approach is based on a greedy algorithm. First, we iterate through the input array `nums` to populate a hash map, `last`, which maps each number to its last seen index. This takes O(N) time.

Next, we iterate through `nums` again from left to right. We maintain a variable `max_reach` that tracks the farthest last-occurrence index of any number we have seen in the current potential block. For each index `i`, we update `max_reach = max(max_reach, last.get(nums[i]))`. If at any point `i == max_reach`, it means we have found the boundary of a minimal block. All numbers within this block (from the end of the previous block to `i`) have their last occurrences within this range, so this block is guaranteed to be disjoint from the rest of the array. We count how many such blocks, `k`, we can form.

The total number of good partitions is then `2^(k-1)`, as we have `k-1` potential places to make a cut (between the `k` blocks). We calculate this using modular exponentiation to handle large results.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int countGoodPartitions(int[] nums) {
        long MOD = 1_000_000_007;
        int n = nums.length;
        Map<Integer, Integer> last = new HashMap<>();
        for (int i = 0; i < n; i++) {
            last.put(nums[i], i);
        }

        int blocks = 0;
        int maxReach = 0;
        for (int i = 0; i < n; i++) {
            maxReach = Math.max(maxReach, last.get(nums[i]));
            if (maxReach == i) {
                blocks++;
            }
        }

        // If there are 'blocks' minimal segments, there are 'blocks - 1' places to cut.
        // Each place has 2 choices: cut or not cut. So 2^(blocks - 1) ways.
        return (int) power(2, blocks - 1, MOD);
    }

    private long power(long base, int exp, long mod) {
        if (exp < 0) return 0; // Should not happen as blocks >= 1
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
- First, pre-compute the last occurrence index for each number in `nums`. This can be done by iterating through `nums` once and storing the results in a hash map `last_occurrence`.
- Initialize a counter for minimal blocks, `blocks = 0`, and a variable `max_reach = 0`.
- Iterate through the array `nums` from `i = 0` to `n-1`:
  - For each element `nums[i]`, update `max_reach` to be the maximum of its current value and `last_occurrence.get(nums[i])`.
  - If `max_reach` is equal to the current index `i`, it signifies the end of a minimal, self-contained block. All numbers seen so far have their last occurrences within the current segment. Increment `blocks`.
- After the loop, `blocks` will hold the total number of such minimal blocks.
- The number of good partitions is the number of ways to partition these `blocks` items, which is `2^(blocks - 1)`.
- Compute this value modulo `10^9 + 7` using modular exponentiation.

# Solutions
### Java

```java
class Solution {
public
  int numberOfGoodPartitions(int[] nums) {
    Map<Integer, Integer> last = new HashMap<>();
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      last.put(nums[i], i);
    }
    final int mod = (int)1 e9 + 7;
    int j = -1;
    int k = 0;
    for (int i = 0; i < n; ++i) {
      j = Math.max(j, last.get(nums[i]));
      k += i == j ? 1 : 0;
    }
    return qpow(2, k - 1, mod);
  }
private
  int qpow(long a, int n, int mod) {
    long ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % mod;
      }
      a = a * a % mod;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfGoodPartitions(vector<int> &nums) {
    unordered_map<int, int> last;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      last[nums[i]] = i;
    }
    const int mod = 1e9 + 7;
    int j = -1, k = 0;
    for (int i = 0; i < n; ++i) {
      j = max(j, last[nums[i]]);
      k += i == j;
    }
    auto qpow = [&](long long a, int n, int mod) {
      long long ans = 1;
      for (; n; n >>= 1) {
        if (n & 1) {
          ans = ans * a % mod;
        }
        a = a * a % mod;
      }
      return (int)ans;
    };
    return qpow(2, k - 1, mod);
  }
};

```

### Python

```python
class Solution:
    def numberOfGoodPartitions(self, nums: List[int]) -> int: last = {x: i for i, x in enumerate(nums)} mod = 10 ** 9 + 7 j, k = - 1, 0 for i, x in enumerate(nums): j = max(j, last[x]) k += i == j return pow(2, k - 1, mod)

```