<p>You are given a <strong>0-indexed</strong> array <code>nums</code> consisting of <strong>positive</strong> integers.</p>

<p>A partition of an array into one or more <strong>contiguous</strong> subarrays is called <strong>good</strong> if no two subarrays contain the same number.</p>

<p>Return <em>the <strong>total number</strong> of good partitions of </em><code>nums</code>.</p>

<p>Since the answer may be large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4]
<strong>Output:</strong> 8
<strong>Explanation:</strong> 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]).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1,1]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only possible good partition is: ([1,1,1,1]).
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,1,3]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The 2 possible good partitions are: ([1,2,1], [3]) and ([1,2,1,3]).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def numberOfGoodPartitions(self, nums: List[int]) -> int:
        # a good subarray is when no two subarrays contain the same number, two subarrays can't share a number
        # the total number of good partitions of nums, how many ways can we split nums into subarrays such that it's good

        # nums: 10^5
        # nums[i] -> 10^9

        # dynamic programming -> we go from left to right and kind of iterate over all the values
        # keep track of the number of ways to form a good partition at the subarray ending at i, nums[:i+1]

        # brute force:
            # for each index, iterate backwards and see for every index before it whether we can make a good partition

        # we need to find an efficient way to ensure our current partition is good
        # each time we look a new value, look at the most recent occurrence, that tells us from where we can start a partition
        # [1,.., 1, .., 1]
        # hashmap : {} track the occurrences
        # [1, 2, 3, 4]
        # ([1], [2], [3]), ([1, 2], [3]) dp[i-1]
        # ([1, [2,3]])
        # ([1,2,3])
        # dp = [1, 2, 4, 8]
        # if there aren't any prev occurrences, dp[i] = dp[i-1] * 2
        # [1]
        # time complexity: O(N), space complexity: O(N) 
        # find the number of discrete intervals needed
        first_occ = {}
        last_occ = {}
        for i in range(len(nums)):
            if nums[i] not in first_occ:
                first_occ[nums[i]] = i
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] not in last_occ:
                last_occ[nums[i]] = i
        intervals = []
        for i in range(len(nums)):
            if i == first_occ[nums[i]]:
                intervals.append((first_occ[nums[i]], last_occ[nums[i]]))
        i = 0
        new_int = []
        while i < len(intervals) - 1:
            if intervals[i][1] > intervals[i+1][0]:
                start, end = intervals[i]
                while i < len(intervals) and end >= intervals[i][0]:
                    end = max(end, intervals[i][1])
                    i += 1
                new_int.append((start, end))
            else:
                new_int.append(intervals[i])
                i += 1
        if i == len(intervals) - 1:
            new_int.append(intervals[i])
            
        return 2 ** (len(new_int) - 1) % (10 ** 9 + 7)
50100