4032. Longest Subarray With at Most K Distinct Prime Factors

Description

You are given an integer array nums consisting of positive integers and an integer k.

The prime factor set of a subarray is the union of the distinct prime factors of all its elements.

Return the length of the longest subarray whose prime factor set contains at most k distinct prime factors. If no such subarray exists, return 0.

Example 1:

Input: nums = [7,6,10,12,11], k = 3

Output: 3

Explanation:

Consider the subarray [6, 10, 12]:

The distinct prime factors of 6 are {2, 3}.
The distinct prime factors of 10 are {2, 5}.
The distinct prime factors of 12 are {2, 3}.
The union of these sets is {2, 3, 5}, which contains 3 distinct prime factors.

No longer subarray satisfies the condition. Therefore, the answer is 3.

Example 2:

Input: nums = [4,6,9,18], k = 4

Output: 4

Explanation:

Consider the entire array [4, 6, 9, 18]:

The distinct prime factors of 4 are {2}.
The distinct prime factors of 6 are {2, 3}.
The distinct prime factors of 9 are {3}.
The distinct prime factors of 18 are {2, 3}.
The union of these sets is {2, 3}, which contains 2 distinct prime factors.

Since 2 <= 4, the entire array is valid. Therefore, the answer is 4.

Example 3:

Input: nums = [6,10,15], k = 2

Output: 1

Explanation:

Every subarray of length at least 2 has prime factor set {2, 3, 5}, which contains 3 distinct prime factors.

Since 3 > 2, only subarrays of length 1 are valid. Therefore, the answer is 1.

Constraints:

1 <= nums.length <= 10⁵
2 <= nums[i] <= 10⁵
1 <= k <= 10⁴

Solutions

Solution 1: Preprocessing + Sliding Window

Thinking

A subarray is legal if and only if it has at most \(k\) distinct prime factors. That constraint is monotone in the window, so a sliding window applies.

Factoring every value online would multiply \(n\) by \(M=10^5\). A sieve stores the prime-factor lists on \([2,M]\); the window updates a hash table from those lists as it expands or shrinks.

Whenever the number of distinct primes is again at most \(k\), the window length updates the answer.

First, we preprocess the list of prime factors for every number in \([2, 10^5]\) and store them in \(\textit{primes}\). Specifically, we enumerate \(i = 2, 3, \cdots, M\). If \(\textit{primes}[i]\) is empty, then \(i\) is a prime, and we add \(i\) to the prime-factor list of every multiple of \(i\).

Then we use a sliding window to find the longest valid subarray. A hash table \(\textit{cnt}\) records the occurrence count of each prime factor in the current window. When the right pointer \(r\) expands, we add all prime factors of \(\textit{nums}[r]\) to the window. When the number of distinct prime factors in the window exceeds \(k\), the left pointer \(l\) shrinks and we remove the prime factors of \(\textit{nums}[l]\). Whenever the window is valid, we update the answer with the window length.

The time complexity is \(O(M \log \log M + n \log M)\), and the space complexity is \(O(M \log \log M)\), where \(n\) is the length of \(\textit{nums}\) and \(M = 10^5\) is the maximum value of the array elements.

Python3JavaC++GoTypeScriptRust

mx = 100001
primes = [[] for _ in range(mx)]
for i in range(2, mx):
    if not primes[i]:
        for j in range(i, mx, i):
            primes[j].append(i)


class Solution:
    def longestSubarray(self, nums: list[int], k: int) -> int:
        cnt = defaultdict(int)
        ans = l = 0
        for r, x in enumerate(nums):
            for y in primes[x]:
                cnt[y] += 1
            while len(cnt) > k:
                for y in primes[nums[l]]:
                    cnt[y] -= 1
                    if cnt[y] == 0:
                        cnt.pop(y)
                l += 1
            ans = max(ans, r - l + 1)
        return ans

class Solution {
    static final int MX = 100001;
    static List<Integer>[] primes = new ArrayList[MX];

    static {
        for (int i = 0; i < MX; i++) {
            primes[i] = new ArrayList<>();
        }

        for (int i = 2; i < MX; i++) {
            if (primes[i].isEmpty()) {
                for (int j = i; j < MX; j += i) {
                    primes[j].add(i);
                }
            }
        }
    }

    public int longestSubarray(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();

        int ans = 0;
        int l = 0;

        for (int r = 0; r < nums.length; r++) {
            for (int p : primes[nums[r]]) {
                cnt.merge(p, 1, Integer::sum);
            }

            while (cnt.size() > k) {
                for (int p : primes[nums[l]]) {
                    if (cnt.merge(p, -1, Integer::sum) == 0) {
                        cnt.remove(p);
                    }
                }
                l++;
            }

            ans = Math.max(ans, r - l + 1);
        }

        return ans;
    }
}

class Solution {
public:
    int longestSubarray(vector<int>& nums, int k) {
        const int MX = 100001;

        static vector<vector<int>> primes(MX);

        static bool initialized = false;
        if (!initialized) {
            initialized = true;

            for (int i = 2; i < MX; i++) {
                if (primes[i].empty()) {
                    for (int j = i; j < MX; j += i) {
                        primes[j].push_back(i);
                    }
                }
            }
        }

        unordered_map<int, int> cnt;

        int ans = 0;
        int l = 0;

        for (int r = 0; r < nums.size(); r++) {
            for (int p : primes[nums[r]]) {
                cnt[p]++;
            }

            while (cnt.size() > k) {
                for (int p : primes[nums[l]]) {
                    if (--cnt[p] == 0) {
                        cnt.erase(p);
                    }
                }
                l++;
            }

            ans = max(ans, r - l + 1);
        }

        return ans;
    }
};

var primes [100001][]int

func init() {
    for i := 2; i < 100001; i++ {
        if len(primes[i]) == 0 {
            for j := i; j < 100001; j += i {
                primes[j] = append(primes[j], i)
            }
        }
    }
}

func longestSubarray(nums []int, k int) int {
    cnt := map[int]int{}

    ans := 0
    l := 0

    for r, x := range nums {

        for _, p := range primes[x] {
            cnt[p]++
        }

        for len(cnt) > k {
            for _, p := range primes[nums[l]] {
                cnt[p]--
                if cnt[p] == 0 {
                    delete(cnt, p)
                }
            }
            l++
        }

        ans = max(ans, r-l+1)
    }

    return ans
}

const MX = 100001;

const primes: number[][] = Array.from({ length: MX }, () => []);

for (let i = 2; i < MX; i++) {
    if (primes[i].length === 0) {
        for (let j = i; j < MX; j += i) {
            primes[j].push(i);
        }
    }
}

function longestSubarray(nums: number[], k: number): number {
    const cnt = new Map<number, number>();

    let ans = 0;
    let l = 0;

    for (let r = 0; r < nums.length; r++) {
        for (const p of primes[nums[r]]) {
            cnt.set(p, (cnt.get(p) ?? 0) + 1);
        }

        while (cnt.size > k) {
            for (const p of primes[nums[l]]) {
                cnt.set(p, cnt.get(p)! - 1);

                if (cnt.get(p) === 0) {
                    cnt.delete(p);
                }
            }
            l++;
        }

        ans = Math.max(ans, r - l + 1);
    }

    return ans;
}

use std::collections::HashMap;
use std::sync::OnceLock;

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>, k: i32) -> i32 {
        static PRIMES: OnceLock<Vec<Vec<i32>>> = OnceLock::new();

        let primes = PRIMES.get_or_init(|| {
            let mut primes = vec![Vec::<i32>::new(); 100001];

            for i in 2..100001 {
                if primes[i].is_empty() {
                    let mut j = i;
                    while j < 100001 {
                        primes[j].push(i as i32);
                        j += i;
                    }
                }
            }

            primes
        });

        let mut cnt: HashMap<i32, i32> = HashMap::new();

        let mut ans = 0;
        let mut l = 0usize;

        for r in 0..nums.len() {
            for &p in &primes[nums[r] as usize] {
                *cnt.entry(p).or_insert(0) += 1;
            }

            while cnt.len() > k as usize {
                for &p in &primes[nums[l] as usize] {
                    let v = cnt.get_mut(&p).unwrap();
                    *v -= 1;

                    if *v == 0 {
                        cnt.remove(&p);
                    }
                }

                l += 1;
            }

            ans = ans.max((r - l + 1) as i32);
        }

        ans
    }
}

4032. Longest Subarray With at Most K Distinct Prime Factors

Description

Solutions

Solution 1: Preprocessing + Sliding Window

Comments