2963. Count the Number of Good Partitions

Problem Description

You have an array nums with positive integers and the challenge is to find out how many ways you can partition this array into contiguous subarrays so that no subarray contains the same number more than once. If you imagine a case with repeated numbers, you'd want to keep repeats in the same subarray to avoid violating the condition. The total number of ways of partitioning the array should be given modulo 10^9 + 7 to keep the number manageable size-wise, as it can get very large.

Intuition

The main idea is to group the same numbers together in a subarray because of the requirement that no subarray should contain duplicate numbers. So, we start by recording the last occurrence of each number using a hash table. With this information, we can determine the potential ends of each subarray.

We iterate through the nums array, updating where the current group could end (this is the furthest last occurrence of any number encountered so far in the array). If the current index aligns with the furthest last occurrence, it means we've reached the end of a potential subarray partition.

Each partition gives us two choices moving forward - either continue with another subarray or group the next number into the current subarray. Except for the first number, every other number has this choice, naturally leading to a calculation of 2^(number of subarrays - 1) to find all the different ways we can partition the array into subarrays that meet the requirements. Since the result can be very large, we use modular exponentiation to give the answer modulo 10^9 + 7. This technique is efficient and proficient for dealing with large powers in a modular space.

Learn more about Math and Combinatorics patterns.

Solution Approach

In the given solution, we utilize a hash map called last to keep track of the last index where each number appears in the array nums. This directly relates to the problem statement where we need to ensure that each subarray has unique elements. By knowing the last occurrence, we can determine the maximum bounds of where a unique element's subarray could end.

To implement this approach, we proceed as follows:

Initialize the last hash map by iterating over the array nums and setting last[x] to i (the current index) for each element x. This way, after the iteration, each key in last directly maps to the last position of that key in nums.
The variables j and k are used, where j keeps track of the end of the current subarray (initially -1) and k keeps count of the total number of subarrays that can be created (initially 0).
As we iterate through nums, for each number x at index i, we update the current subarray end j to the maximum of j and the last occurrence of x from the last hash map. If i equals j at any point during the iteration, it signifies that the current position can be the end of a subarray, at which point we increment k by 1.
After completing the iteration over the array, we calculate the total number of good partitions. Each subarray provides a choice to either split or not split at its end (except for the first element of 'nums' which provides no such choice). Hence, for k subarrays, there are k - 1 split choices, leading to a total of 2^(k - 1) ways to partition the array.
The answer is potentially very large, so we use the modulo operation with 10^9 + 7 to keep the numbers in a reasonable range. In Python, the power function pow is used with three arguments pow(2, k - 1, mod), which efficiently computes 2^(k - 1) modulo mod using fast exponentiation.

This algorithm uses constant space for variables and O(n) space for the hash table, where n is the length of nums. The time complexity is O(n) because we pass through the array only twice: once for creating the hash table and again for determining the partition points and counting subarrays.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's say our array nums is [4, 3, 2, 1, 4, 3].

Following the solution approach outlined in the content provided:

Initialize the last hash map:

We iterate over nums and update the last hash map:

last[4] = 4 (index of the last 4)
last[3] = 5 (index of the last 3)
last[2] = 2 (index of the last 2)
last[1] = 3 (index of the last 1)

Set up variables for tracking subarray ends and count:

We have variable j initialized to -1 and k initialized to 0.
Iterate through nums to determine subarray ends:

As we pass through nums, we will update j and k accordingly:
- i = 0 (value 4): Set j = max(j, last[4]) → j = 4. (No end of subarray reached)
- i = 1 (value 3): Set j = max(j, last[3]) → j = 5. (No end of subarray reached)
- i = 2 (value 2): Keep j = 5. (No end of subarray reached)
- i = 3 (value 1): Keep j = 5. (No end of subarray reached)
- i = 4 (value 4): We are at the last occurrence of '4', and i matches j. We've reached the end of a subarray therefore increment k (now k = 1).
- i = 5 (value 3): Again, i matches j, marking the end of another subarray so increment k to 2.
Count the number of ways to partition nums:

Since we have two subarrays, there are k - 1 = 1 decision point on whether or not to split them. There are (2^{k-1} = 2^1 = 2) ways to partition our nums array.
Apply modulo operation:

We calculate the total number of partition ways modulo (10^9 + 7): result = pow(2, k - 1, 10^9 + 7) → result = 2.

Thus, there are two ways to partition the array [4, 3, 2, 1, 4, 3] into contiguous subarrays where no subarray contains the same number more than once.

Solution Implementation

1from typing import List
2
3class Solution:
4    def numberOfGoodPartitions(self, nums: List[int]) -> int:
5        # Store the last occurrence index of each number in the list
6        last_occurrence_index = {value: index for index, value in enumerate(nums)}
7        mod = 10**9 + 7  # Define the modulo value
8
9        partition_end = -1  # Initialize the end position of the current partition
10        good_partitions_count = 0  # Counter for the number of good partitions
11
12        # Loop through the numbers in the list and their corresponding indices
13        for index, value in enumerate(nums):
14            # Update the end position of the current partition to be the maximum
15            # between the current end and the last occurrence index of the number
16            partition_end = max(partition_end, last_occurrence_index[value])
17          
18            # If the current index is equal to the partition end, it signifies the end
19            # of a partition and we found a "good partition"
20            # Increment the good partitions count accordingly
21            if index == partition_end:
22                good_partitions_count += 1
23
24        # The total number of combinations is 2^(good_partitions_count - 1),
25        # and we return this number modulo mod
26        return pow(2, good_partitions_count - 1, mod)
27

1class Solution {
2    public int numberOfGoodPartitions(int[] nums) {
3        // Use a map to store the last occurrence of each number
4        Map<Integer, Integer> lastOccurrence = new HashMap<>();
5        int length = nums.length;
6      
7        // Populate the map with the last occurrence of each number
8        for (int i = 0; i < length; ++i) {
9            lastOccurrence.put(nums[i], i);
10        }
11      
12        // Define the modulus for large prime numbers, as per the problem statement
13        final int modulus = (int) 1e9 + 7;
14      
15        // Initialization of pointers for the partitioning logic
16        int maxLastOccurrenceIndex = -1;
17        int partitionCount = 0;
18      
19        // Iterate through the array to find good partitions
20        for (int i = 0; i < length; ++i) {
21            // Update the maxLastOccurrenceIndex to the maximum of current and last occurrence of nums[i]
22            maxLastOccurrenceIndex = Math.max(maxLastOccurrenceIndex, lastOccurrence.get(nums[i]));
23          
24            // If the current index is equal to the maxLastOccurrenceIndex,
25            // the partition can end here, so increment the partition counter
26            partitionCount += (i == maxLastOccurrenceIndex) ? 1 : 0;
27        }
28      
29        // Calculate the power (2^(partitionCount - 1) mod modulus) using quick exponentiation
30        return quickPower(2, partitionCount - 1, modulus);
31    }
32
33    // Method to perform quick exponentiation (a^n % mod)
34    private int quickPower(long base, int exponent, int mod) {
35        long result = 1;
36        for (; exponent > 0; exponent >>= 1) {
37            // If the exponent's least significant bit is 1, multiply the result by base
38            if ((exponent & 1) == 1) {
39                result = result * base % mod;
40            }
41            // Square the base and take modulus
42            base = base * base % mod;
43        }
44        return (int) result;
45    }
46}
47

1#include <vector>
2#include <unordered_map>
3
4class Solution {
5public:
6    // Function to count the number of good partitions in the vector `nums`
7    int numberOfGoodPartitions(std::vector<int>& nums) {
8        std::unordered_map<int, int> lastIndex;  // Create a map to store the last index of each number.
9        int n = nums.size();                     // Get the size of the input vector.
10        // Fill the lastIndex map with the last index at which each number appears.
11        for (int i = 0; i < n; ++i) {
12            lastIndex[nums[i]] = i;
13        }
14        const int MOD = 1e9 + 7;                // Initialize the modulus for the result.
15        int j = -1;                             // Initialize the variable `j` to keep track of the last index of the current partition.
16        int partitionsCount = 0;                 // Initialize the counter for partitions.
17
18        // Iterate over the numbers and count the partitions.
19        for (int i = 0; i < n; ++i) {
20            j = std::max(j, lastIndex[nums[i]]);  // Update `j` to be the maximum of itself and the last index of current number.
21            // Increase partitions count if `i` and `j` match.
22            partitionsCount += i == j;
23        }
24
25        // Define a lambda function to calculate quick power modulo.
26        auto quickPower = [&](long long base, int exponent, int mod) -> int {
27            long long result = 1;
28            for (; exponent; exponent >>= 1) {
29                // If current exponent bit is 1, multiply result by base modulo MOD.
30                if (exponent & 1) {
31                    result = (result * base) % mod;
32                }
33                // Square the base modulo MOD for the next iteration.
34                base = (base * base) % mod;
35            }
36            return static_cast<int>(result);
37        };
38
39        // Return the number of ways to partition the array, which is 2^(partitionsCount-1) modulo MOD.
40        return quickPower(2, partitionsCount - 1, MOD);
41    }
42};
43

1function numberOfGoodPartitions(nums: number[]): number {
2    // Helper function to calculate (a^b) % mod efficiently using binary exponentiation.
3    const quickPower = (base: number, exponent: number, mod: number): number => {
4        let result = 1;
5        base %= mod;
6
7        // Iterate over bits of the exponent
8        while (exponent > 0) {
9            // If the current bit is set, multiply the result with the base
10            if (exponent & 1) {
11                result = Number((BigInt(result) * BigInt(base)) % BigInt(mod));
12            }
13
14            // Square the base
15            base = Number((BigInt(base) * BigInt(base)) % BigInt(mod));
16
17            // Shift exponent to the right by 1 bit to check the next bit
18            exponent >>= 1;
19        }
20
21        return result;
22    };
23
24    // Map to track the last position for each distinct number in the array
25    const lastPositionMap: Map<number, number> = new Map();
26
27    // Get the length of the input array
28    const arrayLength = nums.length;
29
30    // Populate last position map with the index of the last occurrence of each number
31    for (let i = 0; i < arrayLength; ++i) {
32        lastPositionMap.set(nums[i], i);
33    }
34
35    // Define the modulus value for the answer
36    const modValue = 1e9 + 7;
37
38    let maxLastPosition = -1; // Tracks the max last position of elements seen so far
39    let partitionCount = 0;   // Counts the number of good partitions
40
41    // Iterate through the array to determine the number of good partitions
42    for (let i = 0; i < arrayLength; ++i) {
43        // Update the maxLastPosition with the larger of current or last occurrence of nums[i]
44        maxLastPosition = Math.max(maxLastPosition, lastPositionMap.get(nums[i])!);
45
46        // If the current index i is the last occurrence of nums[i], increment partition count
47        if (i === maxLastPosition) {
48            partitionCount++;
49        }
50    }
51
52    // Since the first partition doesn't count as splitting, compute 2^(partitionCount-1) % mod
53    return quickPower(2, partitionCount - 1, modValue);
54}
55

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n) since it iterates through all n elements of the input list nums just once. The loop builds a dictionary last that records the last occurrence of each element, and then it iterates over nums once more, updating j and k. Since both operations within the loop are constant time operations, the total time complexity remains linear with respect to the length of nums.

Space Complexity

The space complexity is also O(n) due to the storage requirements of the dictionary last, which, in the worst-case scenario, stores an entry for each unique element in nums. Since nums has n elements and all could be unique, the space required for last can grow linearly with n. No other data structures in the algorithm scale with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know