Skip to content

2963. Count the Number of Good Partitions 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int numberOfGoodPartitions(vector<int>& nums) {
    constexpr int kMod = 1'000'000'007;
    int ans = 1;
    // lastSeen[num] := the index of the last time `num` appeared
    unordered_map<int, int> lastSeen;

    for (int i = 0; i < nums.size(); ++i)
      lastSeen[nums[i]] = i;

    // Track the maximum right index of each running partition by ensuring that
    // the first and last occurrences of a number fall within the same
    // partition.
    int maxRight = 0;
    for (int i = 0; i < nums.size(); ++i) {
      if (i > maxRight)
        // Start a new partition that starts from nums[i].
        // Each partition doubles the total number of good partitions.
        ans = (ans * 2L) % kMod;
      maxRight = max(maxRight, lastSeen[nums[i]]);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int numberOfGoodPartitions(int[] nums) {
    final int MOD = 1_000_000_007;
    int ans = 1;

    // lastSeen[num] := the index of the last time `num` appeared
    HashMap<Integer, Integer> lastSeen = new HashMap<>();

    for (int i = 0; i < nums.length; ++i)
      lastSeen.put(nums[i], i);

    // Track the maximum right index of each running partition by ensuring that
    // the first and last occurrences of a number fall within the same
    // partition.
    int maxRight = 0;
    for (int i = 0; i < nums.length; ++i) {
      if (i > maxRight)
        // Start a new partition that starts from nums[i].
        // Each partition doubles the total number of good partitions.
        ans = (int) ((ans * 2L) % MOD);
      maxRight = Math.max(maxRight, lastSeen.get(nums[i]));
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def numberOfGoodPartitions(self, nums: list[int]) -> int:
    MOD = 1_000_000_007
    ans = 1
    # lastSeen[num] := the index of the last time `num` appeared
    lastSeen = {}

    for i, num in enumerate(nums):
      lastSeen[num] = i

    # Track the maximum right index of each running partition by ensuring that
    # the first and last occurrences of a number fall within the same partition.
    maxRight = 0
    for i, num in enumerate(nums):
      if i > maxRight:
        # Start a new partition that starts from nums[i].
        # Each partition doubles the total number of good partitions.
        ans = ans * 2 % MOD
      maxRight = max(maxRight, lastSeen[num])

    return ans