Maximum Subarray With Equal Products

Difficulty: Easy | Acceptance: 46.80% | Paid: No Topics: Array, Math, Sliding Window, Enumeration, Number Theory

You are given an array nums of positive integers. A subarray nums[i..j] is valid if the length of the subarray is even, say 2k, and the product of the first k elements equals the product of the last k elements. Formally, nums[i] * nums[i+1] * ... * nums[i+k-1] == nums[i+k] * ... * nums[j].

Return the maximum length of a valid subarray. If no such subarray exists, return 0.

• Examples
• Constraints
• Prime Factorization with Prefix Sums
• Logarithmic Sum Comparison

Examples

Example 1

Input: nums = [1,2,3,4,5,6]
Output: 0
Explanation: There is no subarray with equal product halves.

Example 2

Input: nums = [2,3,6,1]
Output: 4
Explanation: The subarray [2,3,6,1] has length 4.
First half product: 2 * 3 = 6
Second half product: 6 * 1 = 6

Example 3

Input: nums = [1,1,1,1]
Output: 4
Explanation: The subarray [1,1,1,1] has length 4.
First half product: 1 * 1 = 1
Second half product: 1 * 1 = 1

Constraints

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

Prime Factorization with Prefix Sums

Intuition Since the numbers in the array are small (1 to 10), their prime factors are limited to 2, 3, 5, and 7. Instead of calculating the potentially huge product directly, we can decompose each number into its prime factors. Two products are equal if and only if the counts of their corresponding prime factors are equal. We use prefix sums to store the cumulative count of these primes up to each index.

Steps

• Create a mapping for numbers 1-10 to their respective counts of prime factors (2, 3, 5, 7).
• Build a prefix sum array prefix where prefix[i] stores the total count of the 4 primes in nums[0...i-1].
• Iterate through all possible subarrays with even length. For a subarray starting at i and ending at j (where length is even), calculate the midpoint index mid.
• Check if the sum of factors in the first half equals the sum in the second half. This translates to checking if 2 * prefix[mid+1] == prefix[i] + prefix[j+1] for all 4 prime factors.
• Track the maximum length found.

class Solution:
    def maxEqualLength(self, nums: list[int]) -> int:
        n = len(nums)
        # Prime factors: 2, 3, 5, 7
        # Map numbers 1-10 to their factor counts
        factors = [
            [0, 0, 0, 0], # 1
            [1, 0, 0, 0], # 2
            [0, 1, 0, 0], # 3
            [2, 0, 0, 0], # 4
            [0, 0, 1, 0], # 5
            [1, 1, 0, 0], # 6
            [0, 0, 0, 1], # 7
            [3, 0, 0, 0], # 8
            [0, 2, 0, 0], # 9
            [1, 0, 1, 0]  # 10
        ]
        
        # Prefix sum array for factors
        prefix = [[0] * 4 for _ in range(n + 1)]
        for i in range(n):
            val = nums[i]
            f = factors[val]
            for k in range(4):
                prefix[i + 1][k] = prefix[i][k] + f[k]
        
        max_len = 0
        # Iterate over all subarrays with even length
        for i in range(n):
            for j in range(i + 1, n, 2):
                # mid is the last index of the first half
                # length = j - i + 1. half_len = length / 2
                # mid = i + half_len - 1
                mid = (i + j + 1) // 2
                
                valid = True
                for k in range(4):
                    # Check if sum(first_half) == sum(second_half)
                    # prefix[mid+1] - prefix[i] == prefix[j+1] - prefix[mid+1]
                    # 2 * prefix[mid+1] == prefix[i] + prefix[j+1]
                    if 2 * prefix[mid + 1][k] != prefix[i][k] + prefix[j + 1][k]:
                        valid = False
                        break
                
                if valid:
                    max_len = max(max_len, j - i + 1)
                    
        return max_len

Complexity

• Time: O(n²) - We iterate through all possible subarrays.
• Space: O(n) - For the prefix sum array.
• Notes: This approach avoids overflow and precision issues associated with large products.

Logarithmic Sum Comparison

Intuition Using the property of logarithms that log(a * b) = log(a) + log(b), we can transform the problem of comparing products into comparing sums of logarithms. This avoids the need for big integers or prime factorization arrays, though it introduces potential floating-point precision errors.

Steps

• Compute a prefix sum array logPrefix where logPrefix[i] is the sum of log(nums[k]) for k < i.
• Iterate through all subarrays with even length.
• For a subarray [i, j], calculate the sum of logs for the first half and the second half using the prefix array.
• Check if the absolute difference between the two sums is less than a small epsilon (e.g., 1e-9).
• Track the maximum length.

import math

class Solution:
    def maxEqualLength(self, nums: list[int]) -> int:
        n = len(nums)
        log_prefix = [0.0] * (n + 1)
        
        for i in range(n):
            log_prefix[i + 1] = log_prefix[i] + math.log(nums[i])
        
        max_len = 0
        for i in range(n):
            for j in range(i + 1, n, 2):
                mid = (i + j + 1) // 2
                
                # Sum of logs for first half: log_prefix[mid+1] - log_prefix[i]
                # Sum of logs for second half: log_prefix[j+1] - log_prefix[mid+1]
                sum_left = log_prefix[mid + 1] - log_prefix[i]
                sum_right = log_prefix[j + 1] - log_prefix[mid + 1]
                
                if abs(sum_left - sum_right) < 1e-9:
                    max_len = max(max_len, j - i + 1)
                    
        return max_len

Complexity

• Time: O(n²) - Iterating through all subarrays.
• Space: O(n) - For the prefix sum array.
• Notes: While concise, this method relies on floating-point arithmetic, which can theoretically lead to incorrect results due to precision loss, though it is generally acceptable for the given constraints.