Count the Number of Good Partitions - Practice Coding Problems

Count the Number of Good Partitions - 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 the total number of good partitions of nums. Since the answer may be large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,4]

› Output: 8

💡 Note: All elements are unique, so we can partition after any position. With 3 possible split points, we have 2³ = 8 ways: [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], [1][2][3][4]

Example 2 — Repeated Elements

$ Input: nums = [1,2,3,2]

› Output: 4

💡 Note: Element 2 appears at positions 1 and 3, so we cannot split between them. Valid partitions: [1,2,3,2], [1][2,3,2], [1,2,3][2], [1][2,3][2]

Example 3 — All Same Elements

$ Input: nums = [1,1,1,1]

› Output: 1

💡 Note: Since all elements are the same, we cannot split anywhere. Only one partition possible: [1,1,1,1]

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array [1,2,3,2] with element 2 appearing at positions 1 and 3

Span Calculation

Element 2 spans from index 1 to 3, preventing splits at positions 1 and 2

Count Partitions

2 valid split points result in 2² = 4 good partitions

Key Takeaway

🎯 Key Insight: An element's span (first to last occurrence) determines where we can legally partition the array

Asked in

G Google 45 M Microsoft 32 a Amazon 28

The key insight is that we can only split the array at positions where no element's span (first to last occurrence) would be broken. The optimal approach finds these valid split points and uses the formula 2^k where k is the number of valid splits. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimal - Combinatorial Analysis	O(n)	O(n)	Find valid partition points using element span analysis and combinatorics
Brute Force - Try All Partitions	O(2^n × n²)	O(n)	Generate all possible partitions and check if each is good

Optimal - Combinatorial Analysis — Algorithm Steps

Find first and last occurrence of each element
Determine minimum spans that cannot be split
Find positions where partitions are allowed
Use combinatorics to count valid partitions

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Element Spans

Calculate first and last occurrence of each unique element

Identify Valid Splits

Mark positions where we can split without breaking any element's span

Count Combinations

Use 2^k formula where k is number of valid split points

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int solution(int* nums, int numsSize) {
    const int MOD = 1000000007;
    
    if (numsSize == 1) return 1;
    
    // Find first and last occurrence of each element
    int first[10001], last[10001];
    memset(first, -1, sizeof(first));
    memset(last, -1, sizeof(last));
    
    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        if (first[num] == -1) {
            first[num] = i;
        }
        last[num] = i;
    }
    
    // Find the rightmost position we must include for each prefix
    int* maxLast = (int*)malloc(numsSize * sizeof(int));
    maxLast[0] = last[nums[0]];
    
    for (int i = 1; i < numsSize; i++) {
        int lastPos = last[nums[i]];
        maxLast[i] = (lastPos > maxLast[i-1]) ? lastPos : maxLast[i-1];
    }
    
    // Count valid partition points
    int validPartitions = 0;
    
    for (int i = 0; i < numsSize-1; i++) {
        if (maxLast[i] == i) {
            validPartitions++;
        }
    }
    
    free(maxLast);
    
    // Number of ways to choose subsets of valid partition points
    return (int)pow(2, validPartitions) % MOD;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int size = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to find spans plus one pass to find valid split points

✓ Linear Growth

Space Complexity

O(n)

Hash map to store first/last occurrences of each element

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimal - Combinatorial Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler