In this guide, you will get 2963. Count the Number of Good Partitions LeetCode Solution with the best time and space complexity. The solution to Count the Number of Good Partitions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count the Number of Good Partitions
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 <= 105
1 <= nums[i] <= 109
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2963. Count the Number of Good Partitions LeetCode Solution in C++
class Solution {
public:
int numberOfGoodPartitions(vector<int>& nums) {
constexpr int kMod = 1'000'000'007;
int ans = 1;
// lastSeen[num] := the index of the last time `num` appeared
unordered_map<int, int> lastSeen;
for (int i = 0; i < nums.size(); ++i)
lastSeen[nums[i]] = i;
// Track the maximum right index of each running partition by ensuring that
// the first and last occurrences of a number fall within the same
// partition.
int maxRight = 0;
for (int i = 0; i < nums.size(); ++i) {
if (i > maxRight)
// Start a new partition that starts from nums[i].
// Each partition doubles the total number of good partitions.
ans = (ans * 2L) % kMod;
maxRight = max(maxRight, lastSeen[nums[i]]);
}
return ans;
}
}; /* code provided by PROGIEZ */
2963. Count the Number of Good Partitions LeetCode Solution in Java
class Solution {
public int numberOfGoodPartitions(int[] nums) {
final int kMod = 1_000_000_007;
int ans = 1;
// lastSeen[num] := the index of the last time `num` appeared
HashMap<Integer, Integer> lastSeen = new HashMap<>();
for (int i = 0; i < nums.length; ++i)
lastSeen.put(nums[i], i);
// Track the maximum right index of each running partition by ensuring that
// the first and last occurrences of a number fall within the same
// partition.
int maxRight = 0;
for (int i = 0; i < nums.length; ++i) {
if (i > maxRight)
// Start a new partition that starts from nums[i].
// Each partition doubles the total number of good partitions.
ans = (int) ((ans * 2L) % kMod);
maxRight = Math.max(maxRight, lastSeen.get(nums[i]));
}
return ans;
}
} // code provided by PROGIEZ
2963. Count the Number of Good Partitions LeetCode Solution in Python
class Solution:
def numberOfGoodPartitions(self, nums: list[int]) -> int:
kMod = 1_000_000_007
ans = 1
# lastSeen[num] := the index of the last time `num` appeared
lastSeen = {}
for i, num in enumerate(nums):
lastSeen[num] = i
# Track the maximum right index of each running partition by ensuring that
# the first and last occurrences of a number fall within the same partition.
maxRight = 0
for i, num in enumerate(nums):
if i > maxRight:
# Start a new partition that starts from nums[i].
# Each partition doubles the total number of good partitions.
ans = ans * 2 % kMod
maxRight = max(maxRight, lastSeen[num])
return ans # code by PROGIEZ
