Maximum Subarray With Equal Products solution and explanation
Google
3 more videos on this problem
3411. Maximum Subarray With Equal Products | Math | Log property | LeetCode | EasyLeet's Code · 13:46 · 1K views
3411. Maximum Subarray With Equal Products (Leetcode Easy)Programming Live with Larry · 3:40 · 835 views
3411. Maximum Subarray With Equal ProductsArkojyotiDeyOfficial · 27:22 · 129 views
Leetcode easy problem 3411. Maximum Subarray With Equal ProductsEasy | devops python practiceADevOpsEngineer · 11:15 · 21 views
The problem
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.
Solution
class Solution:
def maxLength(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
max_p = lcm(*nums) * max(nums)
for i in range(n):
p, g, l = 1, 0, 1
for j in range(i, n):
p *= nums[j]
g = gcd(g, nums[j])
l = lcm(l, nums[j])
if p == g * l:
ans = max(ans, j - i + 1)
if p > max_p:
break
return ansclass Solution {
public int maxLength(int[] nums) {
int mx = 0, ml = 1;
for (int x : nums) {
mx = Math.max(mx, x);
ml = lcm(ml, x);
}
int maxP = ml * mx;
int n = nums.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
int p = 1, g = 0, l = 1;
for (int j = i; j < n; ++j) {
p *= nums[j];
g = gcd(g, nums[j]);
l = lcm(l, nums[j]);
if (p == g * l) {
ans = Math.max(ans, j - i + 1);
}
if (p > maxP) {
break;
}
}
}
return ans;
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
private int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
}class Solution {
public:
int maxLength(vector<int>& nums) {
int mx = 0, ml = 1;
for (int x : nums) {
mx = max(mx, x);
ml = lcm(ml, x);
}
long long maxP = (long long) ml * mx;
int n = nums.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
long long p = 1, g = 0, l = 1;
for (int j = i; j < n; ++j) {
p *= nums[j];
g = gcd(g, nums[j]);
l = lcm(l, nums[j]);
if (p == g * l) {
ans = max(ans, j - i + 1);
}
if (p > maxP) {
break;
}
}
}
return ans;
}
};func maxLength(nums []int) int {
mx, ml := 0, 1
for _, x := range nums {
mx = max(mx, x)
ml = lcm(ml, x)
}
maxP := ml * mx
n := len(nums)
ans := 0
for i := 0; i < n; i++ {
p, g, l := 1, 0, 1
for j := i; j < n; j++ {
p *= nums[j]
g = gcd(g, nums[j])
l = lcm(l, nums[j])
if p == g*l {
ans = max(ans, j-i+1)
}
if p > maxP {
break
}
}
}
return ans
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func lcm(a, b int) int {
return a / gcd(a, b) * b
}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 |
Frequently asked questions
Is Maximum Subarray With Equal Products easy or hard?
The problem is classified as Easy because the core idea relies on checking a mathematical relationship while enumerating subarrays. The challenge mainly comes from recognizing how gcd and lcm interact with the product and implementing the checks efficiently.
Maximum Subarray With Equal Products Python/Java solution
Most solutions iterate over starting indices and expand the subarray while updating gcd, lcm, and product values. This approach is straightforward to implement in Python, Java, C++, or Go using built‑in gcd functions and careful lcm updates.
How to solve Maximum Subarray With Equal Products in O(n)?
Near‑linear performance can be achieved using a sliding window combined with number theory observations. Track prime factors of elements in the window and ensure they do not violate the equality condition product = gcd × lcm. Each element is processed when entering and leaving the window, giving roughly O(n log A) time.
What is the best approach for Maximum Subarray With Equal Products?
The most practical approach is incremental enumeration while maintaining running gcd, lcm, and product values. For each starting index, expand the subarray and update these values in O(log A) time. This produces an overall complexity of O(n^2 log A) and avoids recomputing values for every subarray.
Is Maximum Subarray With Equal Products asked at Google/Amazon/Meta?
Problems involving gcd, lcm, and subarray enumeration frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine number theory with sliding window or prefix techniques are common in coding interviews.
What data structure is used in Maximum Subarray With Equal Products?
Typical implementations use basic arrays along with mathematical utilities for gcd and lcm. Optimized solutions may also use hash maps or frequency maps to track prime factors while maintaining a sliding window.
What is the time complexity of Maximum Subarray With Equal Products?
The optimal commonly implemented solution runs in O(n^2 log A) time by extending each subarray while updating gcd and lcm incrementally. A more advanced sliding window with prime factor tracking can approach O(n log A). Brute force enumeration takes O(n^3).