Count the Number of Good Partitions — LeetCode 2963 Python Solution

The problem

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.

Example

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]).

Python solution

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)

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 2963. Count the Number of Good Partitions is filed here because LeetCode tags it Math and Combinatorics, which is the vocabulary this hub collects.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems