Count the Number of Good Partitions solution and explanation
Google
5 more videos on this problem
Count the Number of Good Partitions | Intuition | Leetcode-2963 | Weekly Contest 375codestorywithMIK · 27:21 · 11K views
2963 Count the Number of Good Partitions || Last index match + Sliding window 🔥Ayush Rao · 9:19 · 932 views
2963. Count the Number of Good Partitions (Leetcode Hard)Programming Live with Larry · 11:31 · 410 views
【每日一题】LeetCode 2963. Count the Number of Good PartitionsHuifeng Guan · 14:35 · 235 views
Count the Number of Good Partitions - LeetCode 2963 - PythonAlpha-Code · 17:09 · 109 views
2963 || Count the Number of Good Partitions || Leetcode Hard || Weekly Contest 375Harsit Sinha · 18:22 · 53 views
The 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 <= 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'.
from collections import defaultdict
def count_good_partitions(nums):
MOD = 10**9 + 7
left = 0
frequency = defaultdict(int)
partition_count = 0
n = len(nums)
for right in range(n):
frequency[nums[right]] += 1
while frequency[nums[right]] > 1:
frequency[nums[left]] -= 1
left += 1
# Each time we find a valid subarray ending at 'right'
partition_count = (partition_count + right - left + 1) % MOD
return partition_countimport java.util.HashMap;
public class GoodPartitions {
public int countGoodPartitions(int[] nums) {
final int MOD = 1000000007;
int left = 0, partitionCount = 0;
HashMap<Integer, Integer> frequency = new HashMap<>();
for (int right = 0; right < nums.length; right++) {
frequency.put(nums[right], frequency.getOrDefault(nums[right], 0) + 1);
while (frequency.get(nums[right]) > 1) {
frequency.put(nums[left], frequency.get(nums[left]) - 1);
left++;
}
partitionCount = (partitionCount + right - left + 1) % MOD;
}
return partitionCount;
}
}function countGoodPartitions(nums) {
const MOD = 1e9 + 7;
let left = 0, partitionCount = 0;
const frequency = new Map();
for (let right = 0; right < nums.length; right++) {
frequency.set(nums[right], (frequency.get(nums[right]) || 0) + 1);
while (frequency.get(nums[right]) > 1) {
frequency.set(nums[left], frequency.get(nums[left]) - 1);
left++;
}
partitionCount = (partitionCount + right - left + 1) % MOD;
}
return partitionCount;
}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.
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.
def count_good_partitions(nums):
MOD = 10**9 + 7
n = len(nums)
dp = [0] * (n + 1)
dp[0] = 1
last_seen = {}
for i in range(1, n + 1):
dp[i] = dp[i - 1]
if nums[i - 1] in last_seen:
dp[i] = (dp[i] + dp[last_seen[nums[i - 1]]]) % MOD
last_seen[nums[i - 1]] = i - 1
return dp[n]import java.util.HashMap;
public class GoodPartitionsDP {
public int countGoodPartitions(int[] nums) {
final int MOD = 1000000007;
int n = nums.length;
int[] dp = new int[n + 1];
dp[0] = 1;
HashMap<Integer, Integer> lastSeen = new HashMap<>();
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
if (lastSeen.containsKey(nums[i - 1])) {
dp[i] = (dp[i] + dp[lastSeen.get(nums[i - 1])]) % MOD;
}
lastSeen.put(nums[i - 1], i - 1);
}
return dp[n];
}
}function countGoodPartitions(nums) {
const MOD = 1e9 + 7;
const n = nums.length;
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
const lastSeen = new Map();
for (let i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
if (lastSeen.has(nums[i - 1])) {
dp[i] = (dp[i] + dp[lastSeen.get(nums[i - 1])]) % MOD;
}
lastSeen.set(nums[i - 1], i - 1);
}
return dp[n];
}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.
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.
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);
}
};function numberOfGoodPartitions(nums: number[]): number {
const qpow = (a: number, n: number, mod: number) => {
let ans = 1;
for (; n; n >>= 1) {
if (n & 1) {
ans = Number((BigInt(ans) * BigInt(a)) % BigInt(mod));
}
a = Number((BigInt(a) * BigInt(a)) % BigInt(mod));
}
return ans;
};
const last: Map<number, number> = new Map();
const n = nums.length;
for (let i = 0; i < n; ++i) {
last.set(nums[i], i);
}
const mod = 1e9 + 7;
let [j, k] = [-1, 0];
for (let i = 0; i < n; ++i) {
j = Math.max(j, last.get(nums[i])!);
if (i === j) {
++k;
}
}
return qpow(2, k - 1, mod);
}func numberOfGoodPartitions(nums []int) int {
qpow := func(a, n, mod int) int {
ans := 1
for ; n > 0; n >>= 1 {
if n&1 == 1 {
ans = ans * a % mod
}
a = a * a % mod
}
return ans
}
last := map[int]int{}
for i, x := range nums {
last[x] = i
}
const mod int = 1e9 + 7
j, k := -1, 0
for i, x := range nums {
j = max(j, last[x])
if i == j {
k++
}
}
return qpow(2, k-1, mod)
}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 | – |
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. |
Frequently asked questions
Is Count the Number of Good Partitions easy or hard?
LeetCode classifies this problem as Hard because it combines multiple ideas: tracking last occurrences, identifying valid partition boundaries, and applying combinatorics to count possibilities. Once the interval insight is recognized, the implementation becomes a straightforward O(n) scan.
Count the Number of Good Partitions Python/Java solution
Implement the solution by storing last indices in a dictionary or HashMap, scanning the array to detect segment boundaries, and computing 2^(segments-1) with modular exponentiation. The same logic works in Python, Java, and JavaScript because the algorithm only relies on hash lookups and a single linear pass.
How to solve Count the Number of Good Partitions in O(n)?
First compute the last index of every number using a hash map. Then iterate through the array while tracking the maximum last index among all elements seen so far. Whenever the current index equals that maximum, a segment closes. Count how many such segments exist and return 2^(segments-1) modulo 1e9+7.
What is the best approach for Count the Number of Good Partitions?
The optimal approach scans the array while tracking the last occurrence of every value. Maintain the farthest index required to include all occurrences of numbers seen so far. Whenever the current index reaches this boundary, a valid segment ends. If there are k segments, the number of good partitions is 2^(k-1). This runs in O(n) time and O(n) space.
Is Count the Number of Good Partitions asked at Google/Amazon/Meta?
Problems involving partition boundaries, last occurrence tracking, and combinatorial counting are common in interviews at companies like Amazon, Google, and Meta. Variants appear under array segmentation or greedy interval merging questions where candidates must reason about overlapping ranges.
What data structure is used in Count the Number of Good Partitions?
A hash table is used to store the last occurrence index of each value in the array. The main algorithm then performs a linear scan while maintaining the maximum boundary index. This combination of a hash map and greedy interval tracking enables an O(n) solution.
What is the time complexity of Count the Number of Good Partitions?
The optimal solution runs in O(n) time because the array is scanned once after computing last occurrences of each value. Hash map lookups for last indices are constant time on average. Space complexity is O(n) for storing the last occurrence map and intermediate variables.