Count the Number of Good Partitions

Hard

#2643Time: 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.

Patterns

Math Combinatorics

Data structures

Array Hash Table

Prompt

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⁹ + 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 <= 10⁵
1 <= nums[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int countGoodPartitions(int[] nums) {6        long MOD = 1_000_000_007;7        int n = nums.length;8        if (n == 1) {9            return 1;10        }11 12        int splitPoints = 0;13        for (int i = 0; i < n - 1; i++) {14            Set<Integer> prefixNums = new HashSet<>();15            for (int j = 0; j <= i; j++) {16                prefixNums.add(nums[j]);17            }18 19            boolean isDisjoint = true;20            for (int j = i + 1; j < n; j++) {21                if (prefixNums.contains(nums[j])) {22                    isDisjoint = false;23                    break;24                }25            }26 27            if (isDisjoint) {28                splitPoints++;29            }30        }31 32        return (int) power(2, splitPoints, MOD);33    }34 35    private long power(long base, int exp, long mod) {36        long res = 1;37        base %= mod;38        while (exp > 0) {39            if (exp % 2 == 1) {40                res = (res * base) % mod;41            }42            base = (base * base) % mod;43            exp /= 2;44        }45        return res;46    }47}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int countGoodPartitions(int[] nums) {6        long MOD = 1_000_000_007;7        int n = nums.length;8        Map<Integer, Integer> last = new HashMap<>();9        for (int i = 0; i < n; i++) {10            last.put(nums[i], i);11        }12 13        int blocks = 0;14        int maxReach = 0;15        for (int i = 0; i < n; i++) {16            maxReach = Math.max(maxReach, last.get(nums[i]));17            if (maxReach == i) {18                blocks++;19            }20        }21 22        // If there are 'blocks' minimal segments, there are 'blocks - 1' places to cut.23        // Each place has 2 choices: cut or not cut. So 2^(blocks - 1) ways.24        return (int) power(2, blocks - 1, MOD);25    }26 27    private long power(long base, int exp, long mod) {28        if (exp < 0) return 0; // Should not happen as blocks >= 129        long res = 1;30        base %= mod;31        while (exp > 0) {32            if (exp % 2 == 1) {33                res = (res * base) % mod;34            }35            base = (base * base) % mod;36            exp /= 2;37        }38        return res;39    }40}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int numberOfGoodPartitions(int[] nums) {4    Map<Integer, Integer> last = new HashMap<>();5    int n = nums.length;6    for (int i = 0; i < n; ++i) {7      last.put(nums[i], i);8    }9    final int mod = (int)1 e9 + 7;10    int j = -1;11    int k = 0;12    for (int i = 0; i < n; ++i) {13      j = Math.max(j, last.get(nums[i]));14      k += i == j ? 1 : 0;15    }16    return qpow(2, k - 1, mod);17  }18private19  int qpow(long a, int n, int mod) {20    long ans = 1;21    for (; n > 0; n >>= 1) {22      if ((n & 1) == 1) {23        ans = ans * a % mod;24      }25      a = a * a % mod;26    }27    return (int)ans;28  }29}

1class Solution {2public:3  int numberOfGoodPartitions(vector<int> &nums) {4    unordered_map<int, int> last;5    int n = nums.size();6    for (int i = 0; i < n; ++i) {7      last[nums[i]] = i;8    }9    const int mod = 1e9 + 7;10    int j = -1, k = 0;11    for (int i = 0; i < n; ++i) {12      j = max(j, last[nums[i]]);13      k += i == j;14    }15    auto qpow = [&](long long a, int n, int mod) {16      long long ans = 1;17      for (; n; n >>= 1) {18        if (n & 1) {19          ans = ans * a % mod;20        }21        a = a * a % mod;22      }23      return (int)ans;24    };25    return qpow(2, k - 1, mod);26  }27};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem