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.

Description Hints 3 Video 47:12

3569. Maximize Count of Distinct Primes After Split

Hard19.0% acceptance1 company

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.

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 1^st query, nums = [2, 2, 3, 1, 2]. Split nums into [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 is 1 + 2 = 3.
After 2^nd query, nums = [2, 2, 3, 3, 2]. Split nums into [2, 2, 3] and [3, 2] with an answer of 2 + 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 1^st query, nums = [1, 1, 4]. There are no prime numbers in nums, hence the answer for this query is 0.
The output is [0].

Constraints:

2 <= n == nums.length <= 5 * 10⁴
1 <= queries.length <= 5 * 10⁴
1 <= nums[i] <= 10⁵
0 <= queries[i][0] < nums.length
1 <= queries[i][1] <= 10⁵

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Preprocess all primes up to max(nums) with a sieve to enable O(1) primality checks.

Hint 2

For each prime p, record its occurrence indices; if it appears at least twice, treat [first, last] as a segment, and note that the split position k with the most overlapping segments equals the number of primes counted on both sides.

Hint 3

Use a segment tree with lazy propagation over all possible k to maintain, update, and query the sum of distinct-prime counts in the prefix and suffix, adjusting for overlaps.

LanguageLoading editor…

1class Solution:
2    def maximumCount(self, nums: List[int], queries: List[List[int]]) -> List[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[2,1,3,1,2]
[[1,2],[3,3]]

Input

[2,1,4]
[[0,1]]

Your code is saved on this device.