Skip to main content
Talentd

Longest Subarray With at Most K Distinct Prime Factors - Solution & Explanation

MediumArrayHash TableMathSliding Window11 min read
Practice this problem

Problem Statement

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 <= 105
  • 2 <= nums[i] <= 105
  • 1 <= k <= 104

Approach Overview

Problem Overview: Given an array of positive integers, find the length of the longest contiguous subarray whose elements collectively have at most K distinct prime factors. A prime factor is counted once per subarray, not per element.

Approach 1: Brute Force - Check All Subarrays (O(n^2 * sqrt(m)))

Generate every possible subarray using two nested loops. For each subarray, factorize every element, insert all prime factors into a set, and check if the set size is at most K. Track the maximum length. This approach is straightforward but recomputes factorizations repeatedly, making it far too slow for large inputs. Space is O(n) in the worst case for the set of prime factors.

Approach 2: Preprocessing + Sliding Window (O(n * sqrt(m)) time, O(n) space)

Precompute the distinct prime factors for every element using trial division up to sqrt(m), where m is the maximum value in the array. Store these factor lists so each element is factorized only once. Then run a classic sliding window: expand the right pointer, add the current element's prime factors to a frequency map, and while the map size exceeds K, shrink the left pointer and remove factors that no longer appear in the window. The answer is the maximum window length seen. This is the optimal approach because it processes each element a constant number of times after preprocessing.

Approach 3: On-the-Fly Sliding Window with Cached Factorization (O(n * sqrt(m)) time, O(n) space)

Instead of precomputing all factor lists upfront, factorize each element lazily and cache the result in a hash map. This avoids factorizing elements that are never visited and can reduce constant factors when the array is large but the window is small. The sliding window logic remains identical. Prefer this when memory is tight or when many elements repeat.

Recommended for interviews: Interviewers expect the sliding window solution. Brute force shows you understand the problem, but the optimal solution demonstrates that you recognize the classic expand-and-shrink window pattern and can combine it with prime factorization. Mention that the frequency map tracks distinct prime factors, not element counts, and explain why a set alone cannot handle the shrinking step efficiently.

Related topics: Sliding Window, Hash Map, Math.

Solution

First, we preprocess the list of prime factors for every number in [2, 10^5] and store them in primes. Specifically, we enumerate i = 2, 3, cdots, M. If 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 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 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 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 nums and M = 10^5 is the maximum value of the array elements.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force - Check All SubarraysO(n^2 * sqrt(m))O(n)Only for tiny arrays or verifying correctness
Preprocessing + Sliding WindowO(n * sqrt(m))O(n)General case, best for interviews
On-the-Fly Sliding Window with Cached FactorizationO(n * sqrt(m))O(n)When memory is constrained or many repeated elements

Video Solutions (4)

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

CodeWithMeGuys21:41157 views
Video 1 of 4

Frequently Asked Questions

Is Longest Subarray With at Most K Distinct Prime Factors easy or hard?
This problem is rated Medium. The sliding window pattern is familiar, but the prime factorization step adds a mathematical twist. Candidates who recognize the window pattern and handle factor deduplication correctly will find it manageable.
Longest Subarray With at Most K Distinct Prime Factors Python/Java solution
In Python, use a dictionary for the frequency map and a helper function to extract distinct prime factors by trial division. In Java, use a HashMap<Integer, Integer> for factor counts and an ArrayList<List<Integer>> to cache factor lists. Both implementations run the same sliding window logic and achieve O(n * sqrt(m)) time.
How to solve Longest Subarray With at Most K Distinct Prime Factors in O(n)?
You can achieve O(n * sqrt(m)) time, which is effectively O(n) when the maximum value is bounded. Factorize each number by trial division up to sqrt(m), store the distinct prime factors, then run a sliding window with a frequency map. When the map has more than K distinct factors, shrink the left pointer until the window is valid again.
What is the best approach for Longest Subarray With at Most K Distinct Prime Factors?
The best approach is a sliding window combined with prime factorization. Precompute or lazily cache the distinct prime factors for each element, then use a frequency map to maintain the count of distinct prime factors in the current window. This runs in O(n * sqrt(m)) time and O(n) space, where n is the array length and m is the maximum value in the array.
Is Longest Subarray With at Most K Distinct Prime Factors asked at Google/Amazon/Meta?
This problem is a variation of the classic 'Longest Substring with At Most K Distinct Characters' combined with number theory. While the exact problem may not be widely reported, top companies like Google, Amazon, and Meta frequently ask sliding window problems and prime factorization problems, so this is strong interview practice.
What data structure is used in Longest Subarray With at Most K Distinct Prime Factors?
The solution uses a hash map (frequency map) to track how many times each distinct prime factor appears in the current window, and a sliding window defined by two pointers. A hash set is used to store the distinct prime factors of each individual element during preprocessing.
What is the time complexity of Longest Subarray With at Most K Distinct Prime Factors?
The optimal sliding window solution runs in O(n * sqrt(m)) time, where n is the number of elements and m is the maximum value in the array. Each element is factorized once and added/removed from the window at most once. The space complexity is O(n) for the factor cache and frequency map.

Ready to solve this problem?

Practice Longest Subarray With at Most K Distinct Prime Factors with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays