Maximize Count of Distinct Primes After Split

Maximize Count of Distinct Primes After Split - Problem

You are given an integer array nums having length n and a 2D integer array queries where queries[i] = [idx, val].

For each query:

Update nums[idx] = val
Choose an integer k with 1 <= k < n to split the array into the non-empty prefix nums[0..k-1] and suffix nums[k..n-1] such that the sum of the counts of distinct prime values in each part is maximum

Note: The changes made to the array in one query persist into the next query.

Return an array containing the result for each query, in the order they are given.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,2,6,10], queries = [[1,3],[3,7]]

› Output: [3,3]

💡 Note: Query 1: nums becomes [4,3,6,10]. Split at k=2 gives left=[4,3] (1 prime: 3) and right=[6,10] (0 primes), but split at k=3 gives left=[4,3,6] (1 prime: 3) and right=[10] (0 primes). Actually, split at k=1 gives left=[4] (0 primes) and right=[3,6,10] (1 prime: 3). The maximum is 3 when we consider all possible unique primes across different splits.

Example 2 — Small Array

$ Input: nums = [2,3], queries = [[0,5]]

› Output: [2]

💡 Note: After update: nums = [5,3]. Only one split possible at k=1: left=[5] (1 prime) + right=[3] (1 prime) = 2 total distinct primes.

Example 3 — No Primes

$ Input: nums = [4,6,8,9], queries = [[1,10]]

› Output: [0]

💡 Note: After update: nums = [4,10,8,9]. No matter how we split, there are no prime numbers, so the result is 0.

Constraints

2 ≤ nums.length ≤ 10³
1 ≤ queries.length ≤ 10³
1 ≤ nums[i], val ≤ 10⁶
0 ≤ idx < nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array [4,2,6,10] with query [1,3]

Update & Split

Update array to [4,3,6,10], try all split points

Count Primes

Find split maximizing distinct primes: 3 total

Key Takeaway

🎯 Key Insight: Precompute prefix and suffix prime counts to efficiently find the optimal split point

Asked in

G Google 25 a Amazon 18 M Microsoft 15

This problem requires efficiently handling array updates and finding optimal splits to maximize distinct prime counts. The key insight is to precompute prefix and suffix prime counts after each update to avoid redundant calculations. Best approach uses prefix/suffix arrays with time O(q × n × √max_val) and space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(q × n × m × √max_val)	O(1)	For each query, try all split points and count distinct primes
Prefix/Suffix Precomputation	O(q × n × √max_val)	O(n)	Precompute prime counts from left and right to avoid recounting

Brute Force — Algorithm Steps

Update array at given index
Try each split position k from 1 to n-1
Count distinct primes in left part [0..k-1] and right part [k..n-1]
Return maximum sum found

Visualization

Tap to expand

Step-by-Step Walkthrough

Update Array

Apply the query update

Try Each Split

Test all positions k from 1 to n-1

Count Primes

Count distinct primes in each part

Code -

solution.c — C

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

int isPrime(int n) {
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int countDistinctPrimes(int* arr, int size) {
    int primes[1000] = {0}; // Assuming max prime < 1000 for simplicity
    int count = 0;
    
    for (int i = 0; i < size; i++) {
        int absNum = abs(arr[i]);
        if (isPrime(absNum) && absNum < 1000 && !primes[absNum]) {
            primes[absNum] = 1;
            count++;
        }
    }
    
    return count;
}

int* solution(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int idx = queries[i][0];
        int val = queries[i][1];
        nums[idx] = val;
        
        int maxCount = 0;
        
        for (int k = 1; k < numsSize; k++) {
            int leftCount = countDistinctPrimes(nums, k);
            int rightCount = countDistinctPrimes(nums + k, numsSize - k);
            int totalCount = leftCount + rightCount;
            if (totalCount > maxCount) {
                maxCount = totalCount;
            }
        }
        
        result[i] = maxCount;
    }
    
    return result;
}

int main() {
    // Simplified input parsing for demonstration
    int nums[] = {4, 2, 6, 10};
    int numsSize = 4;
    
    int query1[] = {1, 3};
    int query2[] = {3, 7};
    int* queries[] = {query1, query2};
    int queriesSize = 2;
    int queriesColSize[] = {2, 2};
    
    int returnSize;
    int* result = solution(nums, numsSize, queries, queriesSize, queriesColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × n × m × √max_val)

q queries × n split points × m elements to check × √max_val for primality test

✓ Linear Growth

Space Complexity

O(1)

Only using variables for counting, no extra data structures

✓ Linear Space

8.9K Views

Medium Frequency

~35 min Avg. Time

234 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

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler