# Maximum Subarray With Equal Products
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-subarray-with-equal-products)
Canonical: https://scaleengineer.com/dsa/problems/maximum-subarray-with-equal-products
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
---
## 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 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`

# Approaches
## Brute-Force Iteration over Subarrays
This approach systematically checks every possible contiguous subarray within the given `nums` array. For each subarray, it verifies if it satisfies the 'product equivalent' condition. A key insight is that the condition `prod(arr) == lcm(arr) * gcd(arr)` is equivalent to all numbers in the subarray `arr` being pairwise coprime. The check for this property is done by ensuring that no two numbers in the subarray share a common prime factor. We can ignore the number 1 as it is coprime with all integers.
**Time:** O(N^3) - There are three nested loops. The outer two loops iterate through all O(N^2) subarrays. The innermost loop iterates up to N elements to check the pairwise coprime property. Operations inside the innermost loop are constant time. · **Space:** O(1) - The space used by the `usedPrimes` set is constant because there are only 4 possible prime factors (2, 3, 5, 7) for numbers up to 10.
**Pros:** Simple and straightforward to understand and implement.; Correctly solves the problem for the given constraints.
**Cons:** High time complexity, which might be too slow for larger constraints.; Redundant computations, as the validity of overlapping subarrays is re-calculated from scratch.
### Explanation
The algorithm iterates through all possible start and end indices, `i` and `j`, to define a subarray. For each subarray, it then iterates through its elements from left to right, keeping track of the prime factors encountered so far in a hash set. If it finds a number that has a prime factor already present in the set, the subarray is not pairwise coprime, and the algorithm moves to the next subarray. If the entire subarray is traversed without such a conflict, its length is compared with the maximum length found so far.

Since the maximum value in `nums` is 10, the only primes we need to consider are 2, 3, 5, and 7. We can precompute the prime factors for numbers 1 through 10.

```java
import java.util.*;

class Solution {
    // Precompute prime factors for numbers 1 to 10 for efficiency
    private static final List<Integer>[] PRIME_FACTORS = new List[11];
    static {
        for (int i = 0; i <= 10; i++) {
            PRIME_FACTORS[i] = new ArrayList<>();
        }
        PRIME_FACTORS[2].add(2);
        PRIME_FACTORS[3].add(3);
        PRIME_FACTORS[4].add(2);
        PRIME_FACTORS[5].add(5);
        PRIME_FACTORS[6].add(2); PRIME_FACTORS[6].add(3);
        PRIME_FACTORS[7].add(7);
        PRIME_FACTORS[8].add(2);
        PRIME_FACTORS[9].add(3);
        PRIME_FACTORS[10].add(2); PRIME_FACTORS[10].add(5);
    }

    public int longestSubarray(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int maxLength = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Check subarray nums[i...j]
                Set<Integer> usedPrimes = new HashSet<>();
                boolean isPairwiseCoprime = true;
                for (int k = i; k <= j; k++) {
                    int currentNum = nums[k];
                    // 1 is coprime with every number
                    if (currentNum == 1) continue;

                    List<Integer> factors = PRIME_FACTORS[currentNum];
                    for (int p : factors) {
                        if (usedPrimes.contains(p)) {
                            isPairwiseCoprime = false;
                            break;
                        }
                    }

                    if (!isPairwiseCoprime) break;
                    
                    // Add the prime factors of the current number to the set
                    usedPrimes.addAll(factors);
                }

                if (isPairwiseCoprime) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        // Any single element subarray is valid, so the minimum answer is 1 if nums is not empty.
        return maxLength > 0 ? maxLength : (n > 0 ? 1 : 0);
    }
}
```
### Algorithm
- First, it's crucial to understand the condition `prod(arr) == lcm(arr) * gcd(arr)`. This mathematical property holds if and only if the elements of the subarray `arr` are pairwise coprime. This simplifies the problem to finding the longest subarray with pairwise coprime elements.
- The brute-force approach iterates through all possible subarrays.
- For each subarray, it checks for the pairwise coprime property.
- Initialize `maxLength = 0`.
- Use a nested loop to define the start `i` and end `j` of a subarray.
- For each subarray `nums[i...j]`, use a third loop from `k = i` to `j` to check its validity.
- Inside the third loop, maintain a set of prime factors (`usedPrimes`) seen so far in the current subarray `nums[i...k]`.
- For each number `nums[k]`, find its prime factors. If any of its prime factors are already in `usedPrimes`, the subarray `nums[i...j]` is invalid. Break and check the next subarray.
- If `nums[k]` doesn't introduce a conflict, add its prime factors to `usedPrimes`.
- If the loop for `k` completes without finding any conflicts, the subarray `nums[i...j]` is valid. Update `maxLength = max(maxLength, j - i + 1)`.
- After checking all subarrays, return `maxLength`.

## Optimal Sliding Window
A more efficient method is the sliding window technique. This approach avoids the redundant calculations of the brute-force method by maintaining a 'window' of elements and checking its validity in linear time. We expand the window by moving a `right` pointer and shrink it by moving a `left` pointer whenever the pairwise coprime property is violated. A hash map is used to keep track of the counts of prime factors within the current window, allowing for a quick check of the window's validity.
**Time:** O(N) - The `right` pointer iterates through the array once. The `left` pointer also traverses the array at most once. Therefore, each element is visited a constant number of times, resulting in a linear time complexity. · **Space:** O(1) - The space complexity is constant. The `primeCounts` map will store at most 4 keys (the primes 2, 3, 5, 7), as the input numbers are less than or equal to 10.
**Pros:** Optimal time complexity.; Highly efficient as each element is processed at most twice.
**Cons:** Slightly more complex to reason about and implement compared to the brute-force approach.
### Explanation
We iterate through the array with a `right` pointer, representing the end of our sliding window. For each element `nums[right]`, we add its prime factors to a frequency map. If adding `nums[right]` causes any prime factor's count to exceed 1, the pairwise coprime property is violated. We then enter a loop to shrink the window from the left by advancing the `left` pointer and removing `nums[left]`'s prime factors from the frequency map, until the property is restored. At each step after ensuring the window is valid, we calculate its size and update our maximum length.

This ensures that both `left` and `right` pointers only move forward through the array, leading to a linear time complexity overall.

```java
import java.util.*;

class Solution {
    // Precompute prime factors for numbers 1 to 10
    private static final List<Integer>[] PRIME_FACTORS = new List[11];
    static {
        for (int i = 0; i <= 10; i++) {
            PRIME_FACTORS[i] = new ArrayList<>();
        }
        PRIME_FACTORS[2].add(2);
        PRIME_FACTORS[3].add(3);
        PRIME_FACTORS[4].add(2);
        PRIME_FACTORS[5].add(5);
        PRIME_FACTORS[6].add(2); PRIME_FACTORS[6].add(3);
        PRIME_FACTORS[7].add(7);
        PRIME_FACTORS[8].add(2);
        PRIME_FACTORS[9].add(3);
        PRIME_FACTORS[10].add(2); PRIME_FACTORS[10].add(5);
    }

    public int longestSubarray(int[] nums) {
        int n = nums.length;
        int maxLength = 0;
        int left = 0;
        Map<Integer, Integer> primeCounts = new HashMap<>();

        for (int right = 0; right < n; right++) {
            int num = nums[right];
            List<Integer> factors = PRIME_FACTORS[num];
            for (int p : factors) {
                primeCounts.put(p, primeCounts.getOrDefault(p, 0) + 1);
            }

            // Shrink window from the left if it's invalid (a prime factor appears more than once)
            while (isInvalid(primeCounts)) {
                int leftNum = nums[left];
                List<Integer> leftFactors = PRIME_FACTORS[leftNum];
                for (int p : leftFactors) {
                    primeCounts.put(p, primeCounts.get(p) - 1);
                    // Optional: remove from map if count is 0 for minor optimization
                    if (primeCounts.get(p) == 0) {
                        primeCounts.remove(p);
                    }
                }
                left++;
            }

            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    private boolean isInvalid(Map<Integer, Integer> primeCounts) {
        for (int count : primeCounts.values()) {
            if (count > 1) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- As with the previous approach, we first simplify the problem to finding the longest subarray with pairwise coprime elements.
- This approach uses a sliding window, defined by a `left` and `right` pointer, to efficiently find the longest valid subarray.
- We use a hash map, `primeCounts`, to store the frequency of each prime factor within the current window.
- Initialize `maxLength = 0`, `left = 0`, and an empty `primeCounts` map.
- Iterate `right` from `0` to `N-1` to expand the window to the right:
  - Add `nums[right]` to the window. Update `primeCounts` by incrementing the counts of its prime factors.
  - After adding `nums[right]`, the window might become invalid (i.e., some prime factor has a count greater than 1).
  - Use a `while` loop to shrink the window from the left until it becomes valid again. In each step of the `while` loop:
    - Check if any prime factor count in `primeCounts` is greater than 1. If not, the window is valid, and we break the `while` loop.
    - If the window is invalid, remove `nums[left]` by decrementing the counts of its prime factors in `primeCounts`.
    - Increment the `left` pointer.
  - Once the window `nums[left...right]` is valid, update `maxLength = max(maxLength, right - left + 1)`.
- Return `maxLength` after the main loop finishes.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
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 ans
```