Maximum Subarray With Equal Products

Easy

#3031Time: 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.

Patterns

Math Sliding Window Enumeration Number Theory

Data structures

Array

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.*;2 3class Solution {4    // Precompute prime factors for numbers 1 to 10 for efficiency5    private static final List<Integer>[] PRIME_FACTORS = new List[11];6    static {7        for (int i = 0; i <= 10; i++) {8            PRIME_FACTORS[i] = new ArrayList<>();9        }10        PRIME_FACTORS[2].add(2);11        PRIME_FACTORS[3].add(3);12        PRIME_FACTORS[4].add(2);13        PRIME_FACTORS[5].add(5);14        PRIME_FACTORS[6].add(2); PRIME_FACTORS[6].add(3);15        PRIME_FACTORS[7].add(7);16        PRIME_FACTORS[8].add(2);17        PRIME_FACTORS[9].add(3);18        PRIME_FACTORS[10].add(2); PRIME_FACTORS[10].add(5);19    }20 21    public int longestSubarray(int[] nums) {22        int n = nums.length;23        if (n == 0) return 0;24        int maxLength = 0;25 26        for (int i = 0; i < n; i++) {27            for (int j = i; j < n; j++) {28                // Check subarray nums[i...j]29                Set<Integer> usedPrimes = new HashSet<>();30                boolean isPairwiseCoprime = true;31                for (int k = i; k <= j; k++) {32                    int currentNum = nums[k];33                    // 1 is coprime with every number34                    if (currentNum == 1) continue;35 36                    List<Integer> factors = PRIME_FACTORS[currentNum];37                    for (int p : factors) {38                        if (usedPrimes.contains(p)) {39                            isPairwiseCoprime = false;40                            break;41                        }42                    }43 44                    if (!isPairwiseCoprime) break;45                    46                    // Add the prime factors of the current number to the set47                    usedPrimes.addAll(factors);48                }49 50                if (isPairwiseCoprime) {51                    maxLength = Math.max(maxLength, j - i + 1);52                }53            }54        }55        // Any single element subarray is valid, so the minimum answer is 1 if nums is not empty.56        return maxLength > 0 ? maxLength : (n > 0 ? 1 : 0);57    }58}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.*;2 3class Solution {4    // Precompute prime factors for numbers 1 to 105    private static final List<Integer>[] PRIME_FACTORS = new List[11];6    static {7        for (int i = 0; i <= 10; i++) {8            PRIME_FACTORS[i] = new ArrayList<>();9        }10        PRIME_FACTORS[2].add(2);11        PRIME_FACTORS[3].add(3);12        PRIME_FACTORS[4].add(2);13        PRIME_FACTORS[5].add(5);14        PRIME_FACTORS[6].add(2); PRIME_FACTORS[6].add(3);15        PRIME_FACTORS[7].add(7);16        PRIME_FACTORS[8].add(2);17        PRIME_FACTORS[9].add(3);18        PRIME_FACTORS[10].add(2); PRIME_FACTORS[10].add(5);19    }20 21    public int longestSubarray(int[] nums) {22        int n = nums.length;23        int maxLength = 0;24        int left = 0;25        Map<Integer, Integer> primeCounts = new HashMap<>();26 27        for (int right = 0; right < n; right++) {28            int num = nums[right];29            List<Integer> factors = PRIME_FACTORS[num];30            for (int p : factors) {31                primeCounts.put(p, primeCounts.getOrDefault(p, 0) + 1);32            }33 34            // Shrink window from the left if it's invalid (a prime factor appears more than once)35            while (isInvalid(primeCounts)) {36                int leftNum = nums[left];37                List<Integer> leftFactors = PRIME_FACTORS[leftNum];38                for (int p : leftFactors) {39                    primeCounts.put(p, primeCounts.get(p) - 1);40                    // Optional: remove from map if count is 0 for minor optimization41                    if (primeCounts.get(p) == 0) {42                        primeCounts.remove(p);43                    }44                }45                left++;46            }47 48            maxLength = Math.max(maxLength, right - left + 1);49        }50        return maxLength;51    }52 53    private boolean isInvalid(Map<Integer, Integer> primeCounts) {54        for (int count : primeCounts.values()) {55            if (count > 1) {56                return true;57            }58        }59        return false;60    }61}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem