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.
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.
Python
JavaScript
Java
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.
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.
Python
JavaScript
Java
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.
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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. |
Count the Number of Good Partitions | Intuition | Leetcode-2963 | Weekly Contest 375 • codestorywithMIK • 10,272 views views
Watch 6 more video solutions →Practice Count the Number of Good Partitions with our built-in code editor and test cases.
Practice on FleetCode