Maximize Count of Distinct Primes After Split - Solution & Explanation

Problem Overview: You are given an array and must choose a split index that divides it into a left and right subarray. The goal is to maximize the total number of distinct prime numbers appearing across the two parts. Each side counts its own distinct primes, so the same prime appearing on both sides contributes to both counts.

Approach 1: Brute Force Recompute Sets (O(n^2 log V) time, O(V) space)

Try every possible split position from 1 to n-1. For each split, iterate through the left portion and insert prime numbers into a set, then repeat for the right portion. Distinct primes are counted using set size. Checking whether a number is prime can be done with trial division or a precomputed sieve. This method is straightforward but extremely slow because the array is rescanned for every split.

Approach 2: Sieve + Prefix/Suffix Distinct Prime Tracking (O(n + M log log M) time, O(n + M) space)

First precompute primality for all values up to the maximum element using the Sieve of Eratosthenes from number theory. Then sweep from left to right and maintain a frequency map for primes to build a prefixDistinct[i] array representing how many distinct primes appear in nums[0..i]. Repeat from right to left to compute suffixDistinct[i]. For every split i, the score is prefixDistinct[i] + suffixDistinct[i+1]. This converts repeated work into two linear scans with constant-time updates using hash maps.

Approach 3: Segment Tree with Prime Frequency Tracking (O(n log n) time, O(n) space)

If the problem includes updates or multiple queries, maintain prime frequencies using a segment tree. Each node stores the set or compressed representation of primes in that range. A split query combines information from two ranges to compute distinct counts efficiently. While heavier than prefix/suffix preprocessing, it supports dynamic modifications and multiple evaluations without recomputing the entire array. The array structure itself comes from classic array processing patterns.

Recommended for interviews: The sieve + prefix/suffix approach is what interviewers usually expect. It demonstrates knowledge of prime preprocessing and linear scans. Mentioning the brute force solution first shows you understand the problem baseline, while the optimized prefix/suffix technique proves you can eliminate repeated work and achieve near-linear complexity.