Maximum Subarray With Equal Products - Video Solutions
3411. Maximum Subarray With Equal Products | Math | Log property | LeetCode | Easy
Maximum Subarray With Equal Products - Video Solution
Watch 4 video solutions for Maximum Subarray With Equal Products, a easy level problem involving Array, Math, Sliding Window. This walkthrough by Leet's Code has 1,161 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 ofarr.gcd(arr)is the GCD of all elements ofarr.lcm(arr)is the LCM of all elements ofarr.
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] <= 10
Approach Overview
Problem 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.
Complexity Analysis
| 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 |