LC-2963 Hard LeetCode

2963. Count the Number of Good Partitions

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 47% Topics: Array, Hash Table, Math, Combinatorics

Reading material

Arrays & Hashing 12 min Math & Geometry 12 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

# hash table, combinatorics
class Solution(object):
    def numberOfGoodPartitions(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        MOD = 10**9+7
        lookup = {x:i for i, x in enumerate(nums)}
        result = 1
        right = cnt = 0
        for left, x in enumerate(nums):
            if left == right+1:
                cnt += 1
            right = max(right, lookup[x])
        return pow(2, cnt, MOD)

Solution from kamyu104/LeetCode-Solutions · MIT