Sliding Window Technique - Part 13

Solution here is a simple sliding window approach, the caveat is to cache the mapping number -> list of unique factors which you can use across test cases. Reasonably fast prime factorization is important too, mine isn't the most optimal but fast enough to pass all test cases. Code is down below, cheers, ACC.

Longest Subarray With at Most K Distinct Prime Factors - LeetCode

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

The prime factor set of a is the union of the distinct 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 <= 105
• 2 <= nums[i] <= 105
• 1 <= k <= 104

public class Solution
{
    static Hashtable uniquePrimeFactors = new Hashtable();

    public int LongestSubarray(int[] nums, int k)
    {
        Hashtable distinctPrimeFactors = new Hashtable();
        int retVal = 0;

        int leftPointer = 0;
        int rightPointer = 0;

        while (rightPointer < nums.Length)
        {
            if (distinctPrimeFactors.Count > k)
            {
                //Move left
                HashSet leftFactors = GetUniquePrimeFactors(nums[leftPointer]);
                foreach (int factor in leftFactors)
                {
                    if (distinctPrimeFactors.Contains(factor))
                    {
                        distinctPrimeFactors[factor] = (int)distinctPrimeFactors[factor] - 1;
                        if ((int)distinctPrimeFactors[factor] <= 0) distinctPrimeFactors.Remove(factor);
                    }
                }
                leftPointer++;
            }
            else
            {
                //Move right
                HashSet rightFactors = GetUniquePrimeFactors(nums[rightPointer]);
                foreach (int factor in rightFactors)
                {
                    if (!distinctPrimeFactors.Contains(factor)) distinctPrimeFactors.Add(factor, 0);
                    distinctPrimeFactors[factor] = (int)distinctPrimeFactors[factor] + 1;
                }
                if (distinctPrimeFactors.Count <= k) retVal = Math.Max(retVal, rightPointer - leftPointer + 1);
                rightPointer++;
            }
        }

        return retVal;
    }

    private HashSet GetUniquePrimeFactors(int n)
    {
        if (uniquePrimeFactors.ContainsKey(n)) return (HashSet)uniquePrimeFactors[n];

        HashSet uniqueFactors = new HashSet();

        int limit = (int)(n / 2 + 1);
        int candidate = 2;
        int temp = n;
        while (candidate <= limit && temp > 1)
        {
            if (temp % candidate == 0)
            {
                if (!uniqueFactors.Contains(candidate)) uniqueFactors.Add(candidate);
                temp /= candidate;
            }
            else
            {
                candidate++;
            }
        }
        if (temp == n) uniqueFactors.Add(n);
        uniquePrimeFactors.Add(n, uniqueFactors);       

        return uniqueFactors;
    }
}