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.

Description Hints 3 Solution Video 27:21

2963. Count the Number of Good Partitions

Hard49.3% acceptance1 company

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 10⁹ + 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 <= 10⁵
1 <= nums[i] <= 10⁹

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

If a segment contains a value, it must contain all occurrences of the same value.

Hint 2

Partition the array into segments making each one as short as possible. This can be achieved by two-pointers or using a Set.

Hint 3

If we have m segments, we can arbitrarily group the neighboring segments. How many ways are there to group these m segments?

27:21

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution