Count the Number of Good Partitions - Solution & Explanation
Problem Statement
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] <= 109
Approach Overview
Problem 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 1: Sliding Window with Frequency Map
This approach employs a sliding window along with a frequency map to maintain the count of each number as we progress through the array. We'll extend the window until we find a conflicting partition, at which point we move the start of the window to maintain the condition required for a partition to be classified as 'good'.
The algorithm initializes a frequency map to count the occurrence of each integer as the right pointer of the sliding window moves forward. If a number repeats in the current window, the left pointer is incremented until the repeating element is excluded, adjusting the frequency accordingly. Each valid window represents a 'good' partition.
Code
Python
JavaScript
Java
Complexity
Time Complexity: O(n), where n is the length of the array, because each element is processed at most twice.
Space Complexity: O(n), due to the space required to store the frequency of each element in the hashmap.
Approach 2: Dynamic Programming
This dynamic programming solution capitalizes on the idea that the number of good partitions can be recursively built from smaller sequences. Treating each element in the array as a potential new starting point, we calculate partitions based on previously evaluated subarrays up to that index.
This DP solution defines dp[i] as the number of good partitions possible for the first i elements. If a number reoccurs, the current DP value contributes its count from the last seen index's DP value. This cumulative process builds the number of good partitions dynamically, using past results to upscale current calculations.
Code
Python
JavaScript
Java
Complexity
Time Complexity: O(n). The loop over the array contributes.
Space Complexity: O(n), used to store the DP table alongside a hashmap tracking the last index of each number.
Approach 3: Hash Table + Grouping + Fast Power
According to the problem description, we know that the same number must be in the same subarray. Therefore, we use a hash table last to record the index of the last occurrence of each number.
Next, we use an index j to mark the index of the last element that has appeared among the elements, and use a variable k to record the number of subarrays that can currently be divided.
Then, we traverse the array nums from left to right. For the current number nums[i] we are traversing, we get its last occurrence index and update j = max(j, last[nums[i]]). If i = j, it means that the current position can be the end of a subarray, and we increase k by 1. Continue to traverse until the entire array is traversed.
Finally, we consider the number of division schemes for k subarrays. The number of subarrays is k, and there are k-1 positions that can be divided (concatenated), so the number of schemes is 2^{k-1}. Since the answer may be very large, we need to take the modulo of 10^9 + 7. Here we can use fast power to speed up the calculation.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Frequency Map | Time Complexity: O(n), where n is the length of the array, because each element is processed at most twice. |
| Dynamic Programming | Time Complexity: O(n). The loop over the array contributes. |
| Hash Table + Grouping + Fast Power | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Count the Number of Good Partitions | Intuition | Leetcode-2963 | Weekly Contest 375 • codestorywithMIK • 11,751 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Count the Number of Good Partitions easy or hard?
Count the Number of Good Partitions Python/Java solution
How to solve Count the Number of Good Partitions in O(n)?
What is the best approach for Count the Number of Good Partitions?
Is Count the Number of Good Partitions asked at Google/Amazon/Meta?
What data structure is used in Count the Number of Good Partitions?
What is the time complexity of Count the Number of Good Partitions?
Ready to solve this problem?
Practice Count the Number of Good Partitions with our built-in code editor and test cases.
Practice on FleetCode