You are given an array of positive integers nums.
An array arr is called product equivalent if prod(arr) == lcm(arr) * gcd(arr), where:
prod(arr) is the product of all elements of arr.gcd(arr) is the GCD of all elements of arr.lcm(arr) is the LCM of all elements of arr.Return the length of the longest product equivalent subarray of nums.
Example 1:
Input: nums = [1,2,1,2,1,1,1]
Output: 5
Explanation:
The longest product equivalent subarray is [1, 2, 1, 1, 1], where prod([1, 2, 1, 1, 1]) = 2, gcd([1, 2, 1, 1, 1]) = 1, and lcm([1, 2, 1, 1, 1]) = 2.
Example 2:
Input: nums = [2,3,4,5,6]
Output: 3
Explanation:
The longest product equivalent subarray is [3, 4, 5].
Example 3:
Input: nums = [1,2,3,1,4,5,1]
Output: 5
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 10Problem Overview: You are given an integer array and must find the maximum length subarray where the product of all elements equals gcd(subarray) × lcm(subarray). The task is essentially identifying contiguous segments where this mathematical equality holds.
Approach 1: Brute Force Enumeration (O(n³) time, O(1) space)
Enumerate every possible subarray using two indices i and j. For each subarray, iterate again to compute its product, gcd, and lcm. After calculating these values, check whether product == gcd × lcm. Track the maximum length that satisfies the condition. This approach is straightforward and demonstrates the mathematical condition clearly, but recomputing values for every subarray makes it impractical for larger arrays.
Approach 2: Incremental Enumeration with Running GCD/LCM (O(n² log A) time, O(1) space)
Fix a starting index and extend the subarray to the right. Maintain the running gcd, lcm, and product as you expand. Updating gcd is cheap, and lcm can be updated using lcm(a,b) = (a × b) / gcd(a,b). After each extension, check if product == gcd × lcm. This avoids recomputing values from scratch and reduces the complexity significantly. The method relies on number theory operations such as number theory and math utilities.
Approach 3: Sliding Window with Prime Factor Tracking (O(n log A) time, O(A) space)
The key mathematical insight: the equality product == gcd × lcm holds only when the numbers in the subarray do not share repeated prime factors in conflicting ways. Using a sliding window, maintain a frequency map of prime factors present in the window. Expand the right pointer while the condition remains valid. If adding a number introduces conflicting factors that break the equality, move the left pointer and remove its contributions. Each element enters and leaves the window once, giving near linear time while relying on fast factorization or small constraints.
Recommended for interviews: Start with the O(n²) incremental enumeration approach. It clearly shows understanding of gcd/lcm relationships and avoids redundant computation. If constraints are large, discussing the sliding window optimization and the number‑theory insight behind the equality demonstrates deeper algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n³) | O(1) | Good for understanding the condition or very small arrays |
| Incremental GCD/LCM Enumeration | O(n² log A) | O(1) | General case with moderate constraints |
| Sliding Window with Factor Tracking | O(n log A) | O(A) | Large inputs where near linear performance is required |
3411. Maximum Subarray With Equal Products | Math | Log property | LeetCode | Easy • Leet's Code • 1,092 views views
Watch 3 more video solutions →Practice Maximum Subarray With Equal Products with our built-in code editor and test cases.
Practice on FleetCode