2963. Good Partitions

Count the Number of Good Partitions

Straight to the point: this task is to split the input array into one or more contiguous subarrays,

with the constraint that no two subarrays share the same number. This is called a good partition.

The expected returned value is total number of good partitions.

Can't Join Two Groups? So...

Put it this way: for any number, find its first and last occurrence at indices $i$ and $j$.

Both $i$ and $j$ must belong to the same group.

Which means we need to track the last occurrence index of each number.

With that in hand, we launch two pointers: scanIdx and boundaryIdx.

boundaryIdx represents the right boundary index of the current unfinished group $G_k$.

scanIdx is used to incrementally scan indices within $G_k$ that haven't been checked yet.

What are we checking? Whether the last occurrence index $j$ of the number $x$ at scanIdx exceeds boundaryIdx.

If it does, we must update boundaryIdx = $j$,

so that $x$ stays loyal and remains within the current unfinished group $G_k$, ensuring $x$ doesn't join two groups 😏

Conversely, if during this incremental scan, scanIdx ever becomes $>$ boundaryIdx,

it naturally means group $G_k$ has fully formed and stopped growing, so we update the total count of completed groups accordingly.

What Does Group Count Represent?

Say there are $k$ groups in total, implying that there are $k - 1$ gaps between them.

Each gap faces two paths: keep it to separate two adjacent groups, or remove it to merge them into one group.

The answer follows: total good partitions = $2^{k - 1}$ ✌️

Since total number of partitions is on the order of $O(2^k)$, we use a modulo of $10^9 + 7$ to prevent overflow.

Even computing the exponent $2^{k - 1}$ should use modular exponentiation for safety.

Hash map stores each number's last occurrence index. Space complexity $O(n)$.

Modular exponentiation is implemented iteratively. Space complexity $O(1)$.

Each index is scanned once by scanIdx, and once when building the hash map. Time complexity $O(n)$.

Modular exponentiation runs in $O(\log(k - 1))$, where $k$ is the total number of groups.

Since $k$ is at most $n$, this is effectively $O(\log n)$.

Overall time and space complexity: both $O(n)$.

C++

#include <unordered_map>
#include <vector>
using namespace std;

int countGoodPartitions(vector<int>& nums) // LeetCode Q.2963.
{
    unordered_map<int, int> numsLastIndices; // Each num's last idx.

    for (int idx = 0; idx < nums.size(); idx++)
        numsLastIndices[nums[idx]] = idx;

    int windowsCount = 0; // Sliding window by two pointers.
    int scanIdx = 0, boundaryIdx = 0;

    while (boundaryIdx < nums.size()) {
        int num = nums[scanIdx];
        scanIdx++; // Already visited.

        if (boundaryIdx < numsLastIndices[num]) { // Num extends current window.
            boundaryIdx = numsLastIndices[num];
            continue;
        }

        if (scanIdx > boundaryIdx) {
            windowsCount++; // Current window is finalized.

            boundaryIdx++; // Search for another window, if possible.
        }
    }

    int goodPartitions = 1;

    int power = windowsCount - 1, modulo = pow(10, 9) + 7;

    while (power > 0) {
        goodPartitions *= 2;
        goodPartitions %= modulo; // Must prevent overflow.
        power--;
    }

    return goodPartitions;
}

Python

def count_good_partitions(nums: list[int]) -> int:  # LeetCode Q.2963.
    nums_last_indices: dict[int, int] = dict()  # Each num's last idx.

    for idx, num in enumerate(nums):
        nums_last_indices[num] = idx

    windows_count = 0  # Sliding window by two pointers.
    scan_idx, boundary_idx = 0, 0

    while boundary_idx < len(nums):
        num = nums[scan_idx]
        scan_idx += 1  # Already visited.

        if boundary_idx < nums_last_indices[num]:  # Num extends current window.
            boundary_idx = nums_last_indices[num]
            continue

        if scan_idx > boundary_idx:
            windows_count += 1  # Current window is finalized.

            boundary_idx += 1  # Search for another window, if possible.

    good_partitions = 1
    power = windows_count - 1
    base = 2  # Mod exp method speeds up quite some in Python.
    modulo = 10 ** 9 + 7

    while power > 0:
        if power % 2 == 1:  # Power is odd: product times current base.
            good_partitions *= base
            good_partitions %= modulo

        base = (base * base) % modulo  # Square base and reduce power.
        power //= 2

    return good_partitions