Skip to main content
Talentd

Maximum Subarray With Equal Products - Solution & Explanation

EasyArrayMathSliding WindowEnumeration4 min readAsked at: Google
Practice this problem

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 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 <= 100
  • 1 <= 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

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n³)O(1)Good for understanding the condition or very small arrays
Incremental GCD/LCM EnumerationO(n² log A)O(1)General case with moderate constraints
Sliding Window with Factor TrackingO(n log A)O(A)Large inputs where near linear performance is required

Video Solution

3411. Maximum Subarray With Equal Products | Math | Log property | LeetCode | Easy • Leet's Code • 1,161 views views

Watch 3 more video solutions →

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

Ready to solve this problem?

Practice Maximum Subarray With Equal Products with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Greatest Common Divisor of Array