Maximize Count of Distinct Primes After Split - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

HardArray Math Segment Tree Number Theory4 min readAsked at: Google

Practice this problem

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 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⁵

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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed 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

Video Solution

3569. Maximize Count of Distinct Primes After Split | LeetCode weekly contest 452 • Amit Dhyani • 654 views views

Watch 2 more video solutions →

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.

Ready to solve this problem?

Practice Maximize Count of Distinct Primes After Split with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyHard

Acceptance19.0%

Approaches0

Reading time4 min

Asked at

Google