Maximize Count of Distinct Primes After Split - Video Solutions
3569. Maximize Count of Distinct Primes After Split | LeetCode weekly contest 452
Maximize Count of Distinct Primes After Split - Video Solution
Watch 3 video solutions for Maximize Count of Distinct Primes After Split, a hard level problem involving Array, Math, Segment Tree. This walkthrough by Amit Dhyani has 654 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
Complexity 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 |