Longest Subarray With at Most K Distinct Prime Factors | Leetcode 4032

class Solution {
    void primeFactorize(unordered_map<int,vector<int>>& prime_factors,int num){
        int val = num;
        vector<int> fact;
        for(int i=2;i*i<=num;++i){
            if(num%i==0)
                fact.push_back(i);
            while(num%i==0)
                num/=i;
        }
        if(num>1)
            fact.push_back(num);
        prime_factors[val] = fact;
    }
public:
    int longestSubarray(vector<int>& nums, int k) {
        // Step-1: Prime Factorize all numbers
        unordered_map<int,vector<int>> prime_factors;
        for(int num: nums){
            if(!prime_factors.count(num))
                primeFactorize(prime_factors,num);
        }

        // Step-2: Apply 2-pointer Sliding Window to find the max window size
        unordered_map<int,int> prime_freq;
        int n = nums.size();

        int l=0,r=0;
        int max_size = 0;
        while(r<n){
            for(int factor: prime_factors[nums[r]]) //Insert the prime factors
                prime_freq[factor]++;
            
            // Use 2-Pointer sliding window to maintain a sliding valid window
            if(prime_freq.size()<=k){    //Check if the count of prime factors is valid
                max_size = max(max_size,r-l+1);
            }else{ // If not valid then remove elements from the left until it becomes valid
                while(l<=r and prime_freq.size()>k){
                    for(int factor: prime_factors[nums[l]]){
                        prime_freq[factor]--;
                        if(prime_freq[factor]==0)
                            prime_freq.erase(factor);
                    }
                    l++;
                }
                max_size = max(max_size,r-l+1);
            }
            r++;
        }
        return max_size;
    }
};
/*
//JAVA
import java.util.*;

class Solution {

    private void primeFactorize(
        HashMap<Integer, ArrayList<Integer>> primeFactors,
        int num
    ) {
        int val = num;
        ArrayList<Integer> factors = new ArrayList<>();

        for (int i = 2; i * i <= num; ++i) {

            if (num % i == 0) {
                factors.add(i);
            }

            while (num % i == 0) {
                num /= i;
            }
        }

        if (num > 1) {
            factors.add(num);
        }

        primeFactors.put(val, factors);
    }

    public int longestSubarray(int[] nums, int k) {

        // Step-1: Prime Factorize all numbers
        HashMap<Integer, ArrayList<Integer>> primeFactors = new HashMap<>();

        for (int num : nums) {
            if (!primeFactors.containsKey(num)) {
                primeFactorize(primeFactors, num);
            }
        }

        // Step-2: Apply 2-pointer Sliding Window
        HashMap<Integer, Integer> primeFreq = new HashMap<>();

        int n = nums.length;

        int l = 0, r = 0;
        int maxSize = 0;

        while (r < n) {

            // Add prime factors of nums[r]
            for (int factor : primeFactors.get(nums[r])) {
                primeFreq.put(
                    factor,
                    primeFreq.getOrDefault(factor, 0) + 1
                );
            }

            // Maintain a valid sliding window
            if (primeFreq.size() <= k) {

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

            } else {

                // Remove elements from the left
                while (l <= r && primeFreq.size() > k) {

                    for (int factor : primeFactors.get(nums[l])) {

                        primeFreq.put(
                            factor,
                            primeFreq.get(factor) - 1
                        );

                        if (primeFreq.get(factor) == 0) {
                            primeFreq.remove(factor);
                        }
                    }

                    l++;
                }

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

            r++;
        }

        return maxSize;
    }
}

#Python
class Solution:

    def primeFactorize(self, prime_factors, num):
        val = num
        factors = []

        i = 2

        while i * i <= num:

            if num % i == 0:
                factors.append(i)

            while num % i == 0:
                num //= i

            i += 1

        if num > 1:
            factors.append(num)

        prime_factors[val] = factors

    def longestSubarray(self, nums, k):

        # Step-1: Prime Factorize all numbers
        prime_factors = {}

        for num in nums:
            if num not in prime_factors:
                self.primeFactorize(prime_factors, num)

        # Step-2: Apply 2-pointer Sliding Window
        prime_freq = {}

        n = len(nums)

        l = 0
        r = 0
        max_size = 0

        while r < n:

            # Add prime factors of nums[r]
            for factor in prime_factors[nums[r]]:
                prime_freq[factor] = prime_freq.get(factor, 0) + 1

            # Maintain a valid sliding window
            if len(prime_freq) <= k:

                max_size = max(max_size, r - l + 1)

            else:

                # Remove elements from the left
                while l <= r and len(prime_freq) > k:

                    for factor in prime_factors[nums[l]]:

                        prime_freq[factor] -= 1

                        if prime_freq[factor] == 0:
                            del prime_freq[factor]

                    l += 1

                max_size = max(max_size, r - l + 1)

            r += 1

        return max_size
*/