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