LeetCode 3411 - Maximum Subarray With Equal Products

We are given an array nums consisting of positive integers. For any array arr, define: - prod(arr) as the product of all elements. - gcd(arr) as the greatest common divisor of all elements. - lcm(arr) as the least common multiple of all elements.

leetcodeeasyarraymathsliding-windowenumerationnumber-theory

LeetCode Problem 3411

Difficulty: 🟢 Easy
Topics: Array, Math, Sliding Window, Enumeration, Number Theory

Solution

LeetCode 3411 - Maximum Subarray With Equal Products

Problem Understanding

We are given an array nums consisting of positive integers.

For any array arr, define:

  • prod(arr) as the product of all elements.
  • gcd(arr) as the greatest common divisor of all elements.
  • lcm(arr) as the least common multiple of all elements.

A subarray is called product equivalent if:

$$prod(arr) = gcd(arr) \times lcm(arr)$$

The task is to find the length of the longest contiguous subarray that satisfies this property.

The input is a small array:

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 10

The constraints are extremely important. Since the array length is at most 100 and each value is at most 10, we can afford to enumerate many subarrays and compute their mathematical properties directly.

The output is a single integer representing the maximum length among all product equivalent subarrays.

A few observations immediately stand out:

  • Every element is positive, so products, GCDs, and LCMs are always well-defined.
  • The array is small enough that checking all subarrays is feasible.
  • Products can grow quickly, but with length at most 100 and values at most 10, Python integers can handle the computation safely.
  • Single-element subarrays satisfy the condition only when x = gcd(x) * lcm(x) = x², which happens only for x = 1. Therefore, not every single-element subarray is valid.
  • Arrays containing many 1s are interesting because multiplying by 1 does not change either the product or the LCM.

Approaches

Brute Force

The most direct approach is to enumerate every possible subarray.

For each subarray [i..j], we compute:

  • The product of all elements.
  • The GCD of all elements.
  • The LCM of all elements.

We then check whether:

$$product = gcd \times lcm$$

If the condition holds, we update the answer.

Since there are O(n²) subarrays and each subarray computation may require scanning up to O(n) elements, the total complexity becomes O(n³).

This approach is correct because every possible subarray is examined, but it performs unnecessary repeated work.

Key Insight

Because the array length is only 100, we can still enumerate every starting position.

Instead of recomputing product, GCD, and LCM from scratch for every subarray, we extend the right endpoint one step at a time and update these values incrementally.

Suppose we already know the values for subarray [i..j-1].

When we add nums[j]:

  • New product = old product × nums[j]
  • New GCD = gcd(old_gcd, nums[j])
  • New LCM = lcm(old_lcm, nums[j])

Each update takes constant time.

Therefore, for every starting index we can grow the subarray while maintaining all required values.

Since there are O(n²) subarrays and each extension performs only constant-time work, the total complexity becomes O(n²).

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Recomputes product, GCD, and LCM for every subarray
Optimal O(n²) O(1) Maintains product, GCD, and LCM incrementally

Algorithm Walkthrough

  1. Initialize answer = 0.
  2. Iterate through every possible starting index left.
  3. For each left, initialize:
  • product = 1
  • current_gcd = 0
  • current_lcm = 1
  1. Extend the subarray one element at a time by moving right from left to n - 1.
  2. Update the running product:

$$product \leftarrow product \times nums[right]$$ 6. Update the running GCD:

$$current_gcd \leftarrow gcd(current_gcd,\ nums[right])$$

Using 0 as the initial value works because:

$$gcd(0, x) = x$$ 7. Update the running LCM:

$$lcm(a,b)=\frac{a}{gcd(a,b)}\times b$$

Therefore:

$$current_lcm \leftarrow lcm(current_lcm,\ nums[right])$$ 8. Check whether:

$$product = current_gcd \times current_lcm$$

If true, update the answer with the current subarray length. 9. After all subarrays have been examined, return the answer.

Why it works

For every starting index, the algorithm considers every possible ending index. Therefore every contiguous subarray appears exactly once.

The maintained values product, current_gcd, and current_lcm always correspond to the current subarray because they are updated according to the mathematical definitions when a new element is appended. Whenever the equality

$$product = gcd \times lcm$$

holds, the subarray is product equivalent. Since every subarray is checked and the maximum valid length is recorded, the returned answer is correct.

Python Solution

from typing import List
from math import gcd

class Solution:
    def maxLength(self, nums: List[int]) -> int:
        n = len(nums)
        answer = 0

        for left in range(n):
            product = 1
            current_gcd = 0
            current_lcm = 1

            for right in range(left, n):
                value = nums[right]

                product *= value
                current_gcd = gcd(current_gcd, value)
                current_lcm = current_lcm // gcd(current_lcm, value) * value

                if product == current_gcd * current_lcm:
                    answer = max(answer, right - left + 1)

        return answer

The outer loop selects a starting position for the subarray.

For each starting position, the inner loop progressively extends the right endpoint. Rather than recomputing everything from scratch, the algorithm updates the running product, GCD, and LCM using the newly added value.

The GCD update uses Python's math.gcd. The LCM update uses the standard identity:

$$lcm(a,b)=\frac{a}{gcd(a,b)}\times b$$

After each extension, the condition product == current_gcd * current_lcm is checked. Whenever it is satisfied, the current subarray length is a candidate answer.

Because every subarray is examined exactly once, the maximum valid length is found.

Go Solution

package main

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
}

func maxLength(nums []int) int {
	n := len(nums)
	answer := 0

	for left := 0; left < n; left++ {
		product := 1
		currentGCD := 0
		currentLCM := 1

		for right := left; right < n; right++ {
			value := nums[right]

			product *= value
			currentGCD = gcd(currentGCD, value)
			currentLCM = lcm(currentLCM, value)

			if product == currentGCD*currentLCM {
				length := right - left + 1
				if length > answer {
					answer = length
				}
			}
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version.

The helper functions gcd and lcm are implemented explicitly because Go does not provide them in the standard library. Integer overflow is not a concern for the problem constraints because values are very small and the maximum array length is only 100.

Worked Examples

Example 1

Input:

nums = [1,2,1,2,1,1,1]

Consider the longest valid subarray:

[1,2,1,1,1]
Element Added Product GCD LCM
1 1 1 1
2 2 1 2
1 2 1 2
1 2 1 2
1 2 1 2

Final check:

product = 2
gcd × lcm = 1 × 2 = 2

The condition holds, so length 5 is valid.

No longer valid subarray exists.

Answer:

5

Example 2

Input:

nums = [2,3,4,5,6]

Consider subarray:

[3,4,5]
Element Added Product GCD LCM
3 3 3 3
4 12 1 12
5 60 1 60

Final check:

product = 60
gcd × lcm = 1 × 60 = 60

Length is 3.

Any longer subarray fails the equality.

Answer:

3

Example 3

Input:

nums = [1,2,3,1,4,5,1]

One longest valid subarray is:

[2,3,1,4,5]

Running values:

Element Added Product GCD LCM
2 2 2 2
3 6 1 6
1 6 1 6
4 24 1 12
5 120 1 60

Final check:

product = 120
gcd × lcm = 1 × 60 = 60

That particular subarray is not valid, so the algorithm continues checking all possibilities.

The longest valid subarray discovered during enumeration has length:

5

Answer:

5

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Every subarray is generated once using nested loops
Space O(1) Only a few running variables are maintained

The outer loop chooses a starting position and the inner loop extends the ending position. Together they examine all n(n+1)/2 subarrays, giving O(n²) time. No auxiliary data structures proportional to input size are used, so the extra space remains constant.

Test Cases

from typing import List

s = Solution()

assert s.maxLength([1, 2, 1, 2, 1, 1, 1]) == 5      # example 1
assert s.maxLength([2, 3, 4, 5, 6]) == 3            # example 2
assert s.maxLength([1, 2, 3, 1, 4, 5, 1]) == 5      # example 3

assert s.maxLength([1, 1]) == 2                     # all ones
assert s.maxLength([2, 2]) == 0                     # no valid subarray
assert s.maxLength([2, 3]) == 2                     # gcd=1, lcm=6, product=6

assert s.maxLength([1, 1, 1, 1]) == 4              # entire array valid
assert s.maxLength([2, 3, 5, 7]) == 4              # pairwise coprime

assert s.maxLength([10, 10, 10]) == 0              # repeated non-one values
assert s.maxLength([1, 2]) == 2                    # simple valid length two

assert s.maxLength([2, 6, 3]) == 2                 # best subarray length two
assert s.maxLength([3, 4, 5]) == 3                 # whole array valid

assert s.maxLength([1, 2, 2, 1]) == 2              # duplicate factors
assert s.maxLength([1, 1, 2, 1, 1]) == 5           # valid whole array

Test Summary

Test Why
[1,2,1,2,1,1,1] Official example 1
[2,3,4,5,6] Official example 2
[1,2,3,1,4,5,1] Official example 3
[1,1] Smallest all-ones array
[2,2] No valid subarray exists
[2,3] Small pairwise-coprime case
[1,1,1,1] Entire array valid
[2,3,5,7] Pairwise-coprime sequence
[10,10,10] Repeated composite values
[1,2] Minimal valid length-two case
[2,6,3] Best answer occurs in a shorter segment
[3,4,5] Entire array satisfies condition
[1,2,2,1] Duplicate prime factors
[1,1,2,1,1] Long valid segment with many ones

Edge Cases

Arrays Containing Only Ones

An array such as [1,1,1,1] is entirely product equivalent. The product is 1, the GCD is 1, and the LCM is 1, so the equality always holds. A careless implementation might incorrectly assume only longer arrays can satisfy the condition. The algorithm handles this naturally by checking every subarray.

No Valid Subarray Exists

Arrays like [2,2] contain no product equivalent subarray. For a single element 2, we have:

$$2 \ne 2^2$$

For the full array:

$$4 \ne 2 \times 2$$

The algorithm initializes the answer to 0 and updates it only when a valid subarray is found, so it correctly returns 0.

Repeated Factors

Arrays such as [2,2,2] are easy places to make mistakes because the LCM stops growing while the product continues growing. The algorithm computes both values according to their definitions and therefore correctly distinguishes between product growth and LCM growth.

Pairwise Coprime Numbers

For arrays such as [2,3,5,7], the GCD is 1 and the LCM equals the product. Therefore:

$$product = 1 \times product$$

The entire array is valid. The implementation correctly discovers this because it maintains exact running GCD and LCM values throughout the enumeration process.