Watch 7 video solutions for Count the Number of Good Partitions, a hard level problem involving Array, Hash Table, Math. This walkthrough by codestorywithMIK has 10,272 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= nums[i] <= 109Problem Overview: You are given an array of integers and must split it into contiguous partitions such that each distinct value appears in exactly one partition. The task is to count how many valid ways the array can be partitioned while satisfying this constraint.
Approach 1: Sliding Window with Frequency Map (O(n) time, O(n) space)
This method tracks the active range of elements using a frequency map and the last occurrence of each value. First compute the last index where every number appears. Then iterate through the array while maintaining the farthest boundary required to keep all occurrences of the current values inside the same partition. When the current index reaches this boundary, a partition can safely end. Each valid boundary creates a binary choice (cut or extend), which leads to multiplying the number of possibilities. The approach relies heavily on hash table lookups and sequential traversal of the array.
Approach 2: Dynamic Programming with Combinatorics (O(n) time, O(n) space)
Another way to frame the problem is by identifying independent segments first and then counting combinations. Compute the last occurrence of every value. While scanning the array, track the maximum last index of all numbers seen so far. Whenever the current index equals this maximum, the segment closes and forms an independent block. If there are k such blocks, each boundary between blocks can either merge with the next block or remain separate, producing 2^(k-1) valid partitions. Modular exponentiation is used to avoid overflow. This approach highlights the dynamic programming perspective combined with combinatorics for counting possibilities efficiently.
Recommended for interviews: The greedy boundary detection using last occurrences is the expected solution. It runs in linear time and demonstrates that you recognize how overlapping value ranges restrict partition points. Explaining the combinatorial step (2^(segments-1)) clearly shows strong reasoning about independent substructures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Last Occurrence Map | O(n) | O(n) | Best general solution. Single pass after preprocessing last indices. |
| Dynamic Programming with Combinatorics | O(n) | O(n) | Useful when reasoning about independent segments and counting partition combinations. |