#2963

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count the Number of Good Partitions

Calculate how many ways to partition an array into contiguous subarrays where no number repeats across segments using hash tracking.

array hash table math combinatorics

Problem Statement

Given a 0-indexed array nums of positive integers, a partition of nums into contiguous subarrays is considered good if each number appears in exactly one subarray. Your task is to return the total number of good partitions possible for nums.

Each subarray in a good partition must contain all occurrences of any number it includes, preventing any value from appearing in multiple subarrays. The array length can be up to 105 and values up to 109.

Examples

Example 1

Input: nums = [1,2,3,4]

Output: 8

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

The only possible good partition is: ([1,1,1,1]).

Example 3

Input: nums = [1,2,1,3]

Output: 2

The 2 possible good partitions are: ([1,2,1], [3]) and ([1,2,1,3]).

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109

Solution Approach

Track last occurrences with a hash map

Scan nums while storing the last index of each value in a hash map. This lets you determine the minimum segment end for each partition to ensure no number appears in multiple subarrays.

Dynamic segment counting

Use a dynamic programming array to store the number of good partitions ending at each index. For each new index, extend previous valid partitions while respecting last occurrence boundaries from the hash map.

Combine counts efficiently

Iterate through nums and combine segment counts using cumulative sums or modular arithmetic if needed. Avoid recomputation by updating counts only when a new segment boundary is reached.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on scanning the array and updating hash maps, approximately O(n). Space complexity is O(n) for storing last occurrences and dynamic counts, scalable to 105 elements.

What Interviewers Usually Probe

Candidate checks last positions of numbers to avoid overlaps in subarrays.
Candidate uses dynamic programming or combinatorics to count partitions.
Candidate explains why extending a segment beyond a repeated number would invalidate the partition.

Common Pitfalls or Variants

Common pitfalls

Failing to include all occurrences of a number in the same subarray, causing invalid partitions.
Overcounting partitions by ignoring previous segment boundaries.
Inefficient hash map lookups or unnecessary nested loops leading to timeouts.

Follow-up variants

Count good partitions with at most k subarrays.
Return the number of partitions where each subarray has unique sums.
Partition arrays into subarrays avoiding duplicate numbers within any segment.

FAQ

What is a good partition in Count the Number of Good Partitions?

A good partition divides the array into contiguous subarrays such that no number appears in more than one subarray, with each subarray containing all occurrences of its numbers.

Why use hash maps for this problem?

Hash maps store the last index of each number, ensuring segments include all occurrences without repetition, which is the core pattern for this array scanning problem.

Can duplicates appear within a single subarray?

Yes, duplicates can appear inside one subarray, but they cannot be split across multiple subarrays in a good partition.

What is the expected time complexity?

Scanning the array with hash lookups and dynamic programming yields roughly O(n) time complexity, efficient even for the maximum length of 105.

How do I handle very large values in nums?

Values themselves are only used as hash keys, so large numbers up to 109 do not impact the algorithm's correctness or efficiency.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

class Solution:
    def numberOfGoodPartitions(self, nums: List[int]) -> int:
        last = {x: i for i, x in enumerate(nums)}
        mod = 10**9 + 7
        j, k = -1, 0
        for i, x in enumerate(nums):
            j = max(j, last[x])
            k += i == j
        return pow(2, k - 1, mod)

Continue Practicing

#3128 right triangles #3312 sorted gcd pair queries #2597 the number of beautiful subsets