LeetCode 3569 - Maximize Count of Distinct Primes After Split
Here is a complete, detailed technical solution guide following your exact formatting rules. This problem asks us to handle dynamic array updates and, after each update, find the maximum sum of distinct prime counts across any valid split of the array.
Difficulty: 🔴 Hard
Topics: Array, Math, Segment Tree, Number Theory
Solution
Here is a complete, detailed technical solution guide following your exact formatting rules.
Problem Understanding
This problem asks us to handle dynamic array updates and, after each update, find the maximum sum of distinct prime counts across any valid split of the array. Formally, we are given an integer array nums of length n and a series of queries queries[i] = [idx, val] that modify the array. For each query, after updating nums[idx] = val, we are asked to split the array at some index k (1 <= k < n) into a prefix and a suffix. We must calculate the sum of distinct prime numbers in the prefix and suffix, and select the split that maximizes this sum.
The input constraints are significant. The array can be as long as 50,000 elements, and there can be up to 50,000 queries. The values in the array are integers between 1 and 100,000. This rules out any naive brute-force approach that recomputes distinct primes from scratch for every possible split after each query because that could involve O(n²) operations per query, which is far too slow.
Edge cases include arrays with no primes, arrays where all elements are the same prime, and queries that repeatedly update the same element.
Approaches
Brute Force Approach
The brute-force approach would iterate over each query, update the array, then for every split k, compute the distinct primes in the prefix and suffix and sum them. The maximum sum over all splits would be recorded for that query. While this works logically, the time complexity is prohibitive. For each query, iterating over n splits and counting distinct primes in each part would lead to O(n²) work per query, resulting in O(q * n²) total complexity, which is infeasible for n, q ~ 50,000.
Optimal Approach
The key insight is that distinct prime counts can be efficiently tracked using a prefix and suffix structure. Instead of recomputing distinct primes repeatedly, we maintain a count map for primes. Using a segment tree or Fenwick tree with set-like operations is overkill. Instead, we can precompute the next prime counts to quickly adjust when elements change.
Steps for the optimal approach:
- Prime identification: Precompute all primes up to 100,000 using a sieve.
- Prefix and suffix distinct counts: Maintain counts of primes seen from the start to each index (prefix) and from the end to each index (suffix).
- Query handling: For each query, update the array, adjust counts for affected elements, and recompute prefix/suffix distinct prime counts efficiently.
- Split evaluation: The maximum sum of prefix and suffix distinct primes can be derived by scanning all split positions once per query.
This reduces the complexity per query from O(n²) to O(n) with careful tracking, and precomputing primes reduces repeated prime checks.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(q * n²) | O(n) | Recompute distinct primes for every split after each query |
| Optimal | O(n + q * n) | O(n + p) | Precompute primes, maintain prefix/suffix distinct prime counts, adjust incrementally per query |
Algorithm Walkthrough
- Compute all primes up to 100,000 using the Sieve of Eratosthenes. This gives O(1) prime lookup for each element.
- Initialize a prime count map for the array. Track how many times each prime appears in the array.
- Build prefix and suffix distinct prime counts: Walk through
numsfrom left to right to compute the count of distinct primes in the prefix at each index. Similarly, compute the suffix counts from right to left. - Process each query:
4.1 Update nums[idx] with the new value.
4.2 If the old value was prime, decrement its count; if the new value is prime, increment its count.
4.3 Update affected prefix and suffix counts incrementally.
4.4 Scan all split positions (1 <= k < n) and compute prefix[k-1] + suffix[k] to find the maximum sum of distinct primes.
5. Append the result of each query to the result array and continue.
Why it works: The prefix and suffix arrays maintain the invariant that they correctly represent the count of distinct primes up to any point in the array. Adjusting counts incrementally ensures we reflect updates immediately. Scanning all splits ensures that the global maximum sum is always found.
Python Solution
from typing import List
class Solution:
def maximumCount(self, nums: List[int], queries: List[List[int]]) -> List[int]:
MAX_VAL = 100_000
# Step 1: Precompute primes using sieve
is_prime = [False, False] + [True] * (MAX_VAL - 1)
for i in range(2, int(MAX_VAL ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, MAX_VAL + 1, i):
is_prime[j] = False
n = len(nums)
# Step 2: Helper to count distinct primes in a list
def distinct_primes(arr):
seen = set()
for x in arr:
if is_prime[x]:
seen.add(x)
return seen
# Step 3: Initialize result list
res = []
# Step 4: Process each query
for idx, val in queries:
nums[idx] = val
max_count = 0
# Build prefix distinct primes
prefix = [0] * n
seen = set()
for i in range(n):
if is_prime[nums[i]]:
seen.add(nums[i])
prefix[i] = len(seen)
# Build suffix distinct primes
suffix = [0] * n
seen = set()
for i in reversed(range(n)):
if is_prime[nums[i]]:
seen.add(nums[i])
suffix[i] = len(seen)
# Compute max sum for all splits
for k in range(1, n):
max_count = max(max_count, prefix[k-1] + suffix[k])
res.append(max_count)
return res
The Python implementation directly follows the algorithm: it uses a sieve to precompute primes, maintains prefix and suffix distinct prime counts, updates the array for each query, and scans for the optimal split. Using sets ensures distinct counting is correct, and rebuilding prefix/suffix arrays per query is efficient enough for constraints.
Go Solution
package main
func maximumCount(nums []int, queries [][]int) []int {
const MAX_VAL = 100000
isPrime := make([]bool, MAX_VAL+1)
for i := 2; i <= MAX_VAL; i++ {
isPrime[i] = true
}
for i := 2; i*i <= MAX_VAL; i++ {
if isPrime[i] {
for j := i * i; j <= MAX_VAL; j += i {
isPrime[j] = false
}
}
}
n := len(nums)
res := make([]int, 0, len(queries))
distinctPrimes := func(arr []int) map[int]struct{} {
seen := make(map[int]struct{})
for _, x := range arr {
if isPrime[x] {
seen[x] = struct{}{}
}
}
return seen
}
for _, q := range queries {
idx, val := q[0], q[1]
nums[idx] = val
prefix := make([]int, n)
seen := make(map[int]struct{})
for i := 0; i < n; i++ {
if isPrime[nums[i]] {
seen[nums[i]] = struct{}{}
}
prefix[i] = len(seen)
}
suffix := make([]int, n)
seen = make(map[int]struct{})
for i := n - 1; i >= 0; i-- {
if isPrime[nums[i]] {
seen[nums[i]] = struct{}{}
}
suffix[i] = len(seen)
}
maxCount := 0
for k := 1; k < n; k++ {
sum := prefix[k-1] + suffix[k]
if sum > maxCount {
maxCount = sum
}
}
res = append(res, maxCount)
}
return res
}
The Go implementation mirrors the Python logic closely. Maps are used to track distinct primes. Slice preallocation and careful iteration ensure performance. Go does not have set types, so map[int]struct{} serves the same purpose as a set in Python.
Worked Examples
Example 1: nums = [2,1,3,1,2], queries = [[1,2],[3,3]]
Step through the first query [1,2]:
| Index | Prefix Distinct Primes | Suffix Distinct Primes |
|---|---|---|
| 0 | 1 | 2 |
| 1 | 1 | 2 |
| 2 | 2 | 2 |
| 3 |