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.

Return _thetotal number of good partitions of _nums.

Since the answer may be large, return it modulo 10^9 + 7.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

Input: nums = [1,1,1,1]
Output: 1
Explanation: The only possible good partition is: ([1,1,1,1]).

Example 3

1
2
3

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

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Greedy + Combinatorics (Counting Partition Points)

Intuition

A partition is good if no two subarrays contain the same number. This means that for every number, all its occurrences must be in the same subarray. We can find the last occurrence of each number, and a partition point is valid if all numbers to the left have their last occurrence before or at that point. The answer is the number of ways to choose partition points, which is 2^k where k is the number of valid partition points.

Approach

  1. For each number, record its last occurrence in the array.
  2. Iterate through the array, keeping track of the farthest last occurrence seen so far.
  3. If the current index equals the farthest last occurrence, it is a valid partition point.
  4. The number of good partitions is 2^k, where k is the number of valid partition points (excluding the end of the array).
  5. Return the answer modulo 10^9 + 7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int countGoodPartitions(vector<int>& nums) {
        const int MOD = 1e9+7;
        int n = nums.size();
        unordered_map<int, int> last;
        for (int i = 0; i < n; ++i) last[nums[i]] = i;
        int ans = 1, maxLast = 0;
        for (int i = 0; i < n-1; ++i) {
            maxLast = max(maxLast, last[nums[i]]);
            if (i == maxLast) ans = (ans * 2) % MOD;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

type Solution struct{}
func (Solution) CountGoodPartitions(nums []int) int {
    const MOD = 1_000_000_007
    n := len(nums)
    last := map[int]int{}
    for i, v := range nums {
        last[v] = i
    }
    ans, maxLast := 1, 0
    for i := 0; i < n-1; i++ {
        if last[nums[i]] > maxLast {
            maxLast = last[nums[i]]
        }
        if i == maxLast {
            ans = ans * 2 % MOD
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int countGoodPartitions(int[] nums) {
        int MOD = 1_000_000_007, n = nums.length;
        Map<Integer, Integer> last = new HashMap<>();
        for (int i = 0; i < n; ++i) last.put(nums[i], i);
        int ans = 1, maxLast = 0;
        for (int i = 0; i < n-1; ++i) {
            maxLast = Math.max(maxLast, last.get(nums[i]));
            if (i == maxLast) ans = (int)((long)ans * 2 % MOD);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun countGoodPartitions(nums: IntArray): Int {
        val MOD = 1_000_000_007
        val n = nums.size
        val last = mutableMapOf<Int, Int>()
        for (i in 0 until n) last[nums[i]] = i
        var ans = 1
        var maxLast = 0
        for (i in 0 until n-1) {
            maxLast = maxOf(maxLast, last[nums[i]]!!)
            if (i == maxLast) ans = (ans * 2) % MOD
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def countGoodPartitions(self, nums: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        last = {v: i for i, v in enumerate(nums)}
        ans = 1
        max_last = 0
        for i in range(n-1):
            max_last = max(max_last, last[nums[i]])
            if i == max_last:
                ans = ans * 2 % MOD
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn count_good_partitions(nums: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let n = nums.len();
        let mut last = std::collections::HashMap::new();
        for (i, &v) in nums.iter().enumerate() {
            last.insert(v, i);
        }
        let mut ans = 1i64;
        let mut max_last = 0;
        for i in 0..n-1 {
            max_last = max_last.max(*last.get(&nums[i]).unwrap());
            if i == max_last {
                ans = ans * 2 % MOD;
            }
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    countGoodPartitions(nums: number[]): number {
        const MOD = 1_000_000_007;
        const n = nums.length;
        const last = new Map<number, number>();
        for (let i = 0; i < n; ++i) last.set(nums[i], i);
        let ans = 1, maxLast = 0;
        for (let i = 0; i < n-1; ++i) {
            maxLast = Math.max(maxLast, last.get(nums[i])!);
            if (i === maxLast) ans = ans * 2 % MOD;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums, since we scan the array twice.
  • 🧺 Space complexity: O(n), for the hash map of last occurrences.