Count the Number of Good Partitions

Count the Number of Good Partitions

What is this problem about?

The Count the Number of Good Partitions interview question involves an array where you must divide it into one or more non-empty contiguous subarrays. A partition is "good" if no two subarrays contain the same value. In other words, if a number $x$ appears in the array, all occurrences of $x$ must be contained within the same subarray.

Your goal is to find the total number of ways to create such partitions.

Why is this asked in interviews?

Google uses this "Hard" problem to test a candidate's ability to model dependencies as intervals. It requires identifying the interval merge interview pattern. By finding the first and last occurrence of each number, you define "must-include" ranges. If these ranges overlap, they must be merged. Once merged, the gaps between the final disjoint intervals represent possible "cut points."

Algorithmic pattern used

This problem is solved using Interval Merging and Combinatorics.

1. Determine Ranges: Use a Hash Table to record the first and last index of every unique number.
2. Merge Intervals: Sort the ranges by start index and merge overlapping ones.
3. Count Components: Let $M$ be the number of disjoint merged intervals.
4. Calculate Ways: Each gap between $M$ intervals can either be a cut or not. There are $M-1$ such gaps.
5. Total ways = $2^{M-1}$ (modulo $10^9 + 7$).

Example explanation

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

1. Ranges:
   • 1: [0, 2]
   • 2: [1, 1]
   • 3: [3, 5]
   • 4: [4, 4]
2. Merging:
   • [0, 2] and [1, 1] overlap $o$ [0, 2].
   • [3, 5] and [4, 4] overlap $o$ [3, 5].
3. Disjoint Intervals: [0, 2] and [3, 5].
4. $M = 2$.
5. Ways = $2^{2-1} = 2^1 = 2$. The partitions are [[1, 2, 1], [3, 4, 3]] and [[1, 2, 1, 3, 4, 3]].

Common mistakes candidates make

• Inefficient merging: Not sorting the intervals before merging, leading to $O(N^2)$ checks.
• Missing dependencies: Not realizing that if 1 is in a block and 2 is in that same block, all instances of 2 must also be in that block, even if they extend beyond the last 1.
• Power calculation: Forgetting to handle the modulo during the $2^{M-1}$ calculation.

Interview preparation tip

Think of this as a "connected components" problem on intervals. If two elements "interact" because their ranges overlap, they belong to the same logical group. Grouping items by their first/last occurrence is a common technique for subarray problems.