Maximize Count of Distinct Primes After Split solution and explanation
Google
2 more videos on this problem
3569. Maximize Count of Distinct Primes After Split | LeetCode weekly contest 452Amit Dhyani · 47:12 · 654 views
3569. Maximize Count of Distinct Primes After Split (Leetcode Hard)Programming Live with Larry · 54:28 · 362 views
Maximize Count of Distinct Primes After Split (Leetcode Weekly 452)Soumya Bhattacharjee · 19:08 · 195 views
The 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
kwith1 <= k < nto split the array into the non-empty prefixnums[0..k-1]and suffixnums[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.
Example 1:
Input: nums = [2,1,3,1,2], queries = [[1,2],[3,3]]
Output: [3,4]
Explanation:
- Initially
nums = [2, 1, 3, 1, 2]. - After 1st query,
nums = [2, 2, 3, 1, 2]. Splitnumsinto[2]and[2, 3, 1, 2].[2]consists of 1 distinct prime and[2, 3, 1, 2]consists of 2 distinct primes. Hence, the answer for this query is1 + 2 = 3. - After 2nd query,
nums = [2, 2, 3, 3, 2]. Splitnumsinto[2, 2, 3]and[3, 2]with an answer of2 + 2 = 4. - The output is
[3, 4].
Example 2:
Input: nums = [2,1,4], queries = [[0,1]]
Output: [0]
Explanation:
- Initially
nums = [2, 1, 4]. - After 1st query,
nums = [1, 1, 4]. There are no prime numbers innums, hence the answer for this query is 0. - The output is
[0].
Constraints:
2 <= n == nums.length <= 5 * 1041 <= queries.length <= 5 * 1041 <= nums[i] <= 1050 <= queries[i][0] < nums.length1 <= queries[i][1] <= 105
Approach overview
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.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Set Recalculation | O(n^2 log V) | O(V) | Small arrays or when demonstrating baseline logic during interviews |
| Sieve + Prefix/Suffix Distinct Prime Count | O(n + M log log M) | O(n + M) | Best general solution when the array is static and only one optimal split is required |
| Segment Tree with Prime Tracking | O(n log n) | O(n) | Useful when the array changes or multiple split queries must be processed efficiently |
Frequently asked questions
Is Maximize Count of Distinct Primes After Split easy or hard?
This problem is considered Hard due to the combination of number theory preprocessing and efficient array partition analysis. Many candidates initially attempt O(n^2) recomputation before recognizing the need for prefix/suffix optimization.
Maximize Count of Distinct Primes After Split Python/Java solution
The standard implementation precomputes primes using the Sieve of Eratosthenes, then scans the array to build prefix and suffix distinct-prime counts. The same logic translates directly across Python, Java, C++, and Go using sets or hash maps for frequency tracking.
How to solve Maximize Count of Distinct Primes After Split in O(n)?
Achieving near-linear time requires preprocessing primes with a sieve and then performing two linear passes over the array. The first pass records distinct primes seen so far, and the second pass records distinct primes from the right side. Evaluating each split becomes an O(1) lookup using these arrays.
What is the best approach for Maximize Count of Distinct Primes After Split?
The most efficient approach uses the Sieve of Eratosthenes to precompute prime numbers and then builds prefix and suffix arrays that track the number of distinct primes seen so far. For each possible split, combine prefixDistinct[i] and suffixDistinct[i+1]. This runs in O(n + M log log M) time where M is the maximum value in the array.
Is Maximize Count of Distinct Primes After Split asked at Google/Amazon/Meta?
Problems involving prime preprocessing, prefix arrays, and distinct counting appear frequently in interviews at companies like Google and Amazon. Variants combining number theory with array partitioning are common in high-difficulty coding rounds.
What data structure is used in Maximize Count of Distinct Primes After Split?
The core solution uses hash sets or frequency maps to track distinct primes, along with prefix and suffix arrays for fast lookup. Some advanced variants use a segment tree to support dynamic updates or repeated split queries efficiently.
What is the time complexity of Maximize Count of Distinct Primes After Split?
The optimal solution runs in O(n + M log log M) time. The sieve preprocessing costs O(M log log M) and the prefix/suffix scans over the array take O(n). Space complexity is O(n + M) for the sieve and distinct tracking arrays.