Number of Ways Where Square of Number Is Equal to Product of Two Numbers - Solution & Explanation

Q: Is Number of Ways Where Square of Number Is Equal to Product of Two Numbers easy or hard?

The problem is typically rated Medium difficulty. The brute force idea is straightforward, but recognizing that pair products can be converted into factor lookups with a hash map requires algorithmic insight.

Q: Number of Ways Where Square of Number Is Equal to Product of Two Numbers Python/Java solution

Python and Java implementations follow the same pattern: compute the square target, iterate through the second array, and use a hash map to count complements. Each iteration checks if target % num == 0 and adds the frequency of target / num from the map, resulting in O(n^2) time complexity.

Q: How to solve Number of Ways Where Square of Number Is Equal to Product of Two Numbers in O(n^2)?

Iterate through one array and compute the square of each element. While scanning the other array, maintain a frequency map of numbers already seen. If target % current == 0, look up target / current in the map to count matching factors. Repeat the same process with arrays swapped to include both valid triplet types.

Q: What is the best approach for Number of Ways Where Square of Number Is Equal to Product of Two Numbers?

The most efficient approach uses a hash map to count complements while scanning the second array. For each value x, compute target = x^2 and check whether previously seen numbers form a product equal to that target. Hash lookups allow counting valid pairs in constant time, giving an overall time complexity of O(n^2) with O(n) extra space.

Q: Is Number of Ways Where Square of Number Is Equal to Product of Two Numbers asked at Google/Amazon/Meta?

This problem represents a common interview pattern involving pair products and hash-based counting. Variations of the problem appear in interviews at large tech companies where candidates must convert a triple condition into pair lookups using hash maps or frequency tables.

Q: What data structure is used in Number of Ways Where Square of Number Is Equal to Product of Two Numbers?

The optimal solution relies on a hash table (hash map) to store frequencies of numbers while iterating through the array. This allows constant-time lookups for complementary factors that multiply to the target square value.

Q: What is the time complexity of Number of Ways Where Square of Number Is Equal to Product of Two Numbers?

The brute force approach runs in O(n * m^2) time because every squared value is compared with all pairs from the other array. The optimized solution reduces this to O(n^2) by using a hash map to track previously seen numbers and count factor complements in constant time.

MediumArray Hash Table Math Two Pointers25 min read

Practice this problem

Problem Statement

Given two arrays of integers nums1 and nums2, return the number of triplets formed (type 1 and type 2) under the following rules:

Type 1: Triplet (i, j, k) if nums1[i]² == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
Type 2: Triplet (i, j, k) if nums2[i]² == nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= j < k < nums1.length.

Example 1:

Input: nums1 = [7,4], nums2 = [5,2,8,9]
Output: 1
Explanation: Type 1: (1, 1, 2), nums1[1]² = nums2[1] * nums2[2]. (4² = 2 * 8).

Example 2:

Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 1² = 1 * 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1[i]² = nums2[j] * nums2[k].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]² = nums1[j] * nums1[k].

Example 3:

Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]
Output: 2
Explanation: There are 2 valid triplets.
Type 1: (3,0,2).  nums1[3]² = nums2[0] * nums2[2].
Type 2: (3,0,1).  nums2[3]² = nums1[0] * nums1[1].

Constraints:

1 <= nums1.length, nums2.length <= 1000
1 <= nums1[i], nums2[i] <= 10⁵

Approach Overview

Problem Overview: You are given two arrays nums1 and nums2. Count triplets where the square of a number from one array equals the product of two numbers from the other array. Both directions count: nums1[i]^2 = nums2[j] * nums2[k] and nums2[i]^2 = nums1[j] * nums1[k] with j < k.

Approach 1: Brute Force Enumeration (O(n * m^2) time, O(1) space)

For every element in one array, compute its square and check all pairs in the other array. Use two nested loops to generate every pair (j, k) and compare their product with the square. Repeat the same process with arrays swapped to capture the second condition. This approach directly follows the problem definition and is useful for validating correctness on small inputs. However, triple nested iteration quickly becomes expensive when array sizes grow.

Approach 2: Optimized Hash Map Pair Counting (O(n^2) time, O(n) space)

The key observation: instead of recomputing all pair products repeatedly, track factors using a frequency map. For each element x in one array, compute target = x * x. Then iterate through the other array and check whether a previously seen number forms a valid pair: if target % num == 0, look up target / num in a hash map. This counts how many earlier numbers complete the product. After processing each number, store it in the map for future matches. Repeat the process with the arrays swapped to capture both triplet types. Hash lookups make pair detection constant time.

This technique is a common pattern in hash table problems where you convert pair comparisons into complement lookups. The arrays themselves are processed sequentially using standard array iteration, while arithmetic checks come from basic math reasoning about factors.

Recommended for interviews: The optimized hash map approach. The brute force method shows you understand the triplet condition, but the O(n^2) hash-based counting demonstrates awareness of factor matching and frequency tracking. Interviewers usually expect the optimized version once constraints suggest that cubic enumeration is too slow.

Approach 1: Brute Force Approach

This approach involves iterating through each element in one array, computing its square, and then iterating through all possible product pairs in the other array to check for matches. Although simple to understand, this approach is not optimal due to its O(n^3) complexity.

The function count_triplets computes the number of valid triplets for one type, given two lists. It computes the square of each element in arr1 and then iterates through all pairs in arr2 to find matching products. The final count is the sum of Type 1 and Type 2 triplets.

Code

Python JavaScript C C++Java C#

Python

JavaScript

C++

Java

Complexity

The time complexity is O(n^3), due to the triple loop. The space complexity is O(1), aside from input storage.

Try this approach in the editor →

Approach 2: Optimized Hash Map Approach

This approach improves efficiency by using hash maps (or dictionaries) to precompute the frequency of products. For each square in the first array, it checks the hash map for potential matching products in the second array, offering a much faster solution with O(n^2) complexity.

The count_triplets_via_map function first precomputes the frequency of all unique products in the second array. It then iterates through the first array and checks how many of its squares are present in the product hashmap, summing the counts of valid products.

Code

Python JavaScript C C++Java C#

Python

JavaScript

C++

Java

Complexity

The time complexity is O(n^2) because of the double nested loop for generating products and using a hash map lookup. The space complexity is O(n^2) due to storing products in a hash map.

Try this approach in the editor →

Approach 3: Hash Table + Enumeration

We use a hash table cnt1 to count the occurrences of each pair (nums[j], nums[k]) in nums1, where 0 leq j < k < m, and m is the length of the array nums1. Similarly, we use a hash table cnt2 to count the occurrences of each pair (nums[j], nums[k]) in nums2, where 0 leq j < k < n, and n is the length of the array nums2.

Next, we enumerate each number x in the array nums1 and calculate the value of cnt2[x^2], which is the number of pairs (nums[j], nums[k]) in nums2 that satisfy nums[j] times nums[k] = x^2. Similarly, we enumerate each number x in the array nums2 and calculate the value of cnt1[x^2], which is the number of pairs (nums[j], nums[k]) in nums1 that satisfy nums[j] times nums[k] = x^2. Finally, we return the sum of the two results.

The time complexity is O(m^2 + n^2 + m + n), and the space complexity is O(m^2 + n^2). Here, m and n are the lengths of the arrays nums1 and nums2, respectively.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Approach 4: Hash Table + Enumeration Optimization

We use a hash table cnt1 to count the occurrences of each number in nums1, and a hash table cnt2 to count the occurrences of each number in nums2.

Next, we enumerate each number x in the array nums1, and then enumerate each pair (y, v1) in cnt2, where y is the key of cnt2 and v1 is the value of cnt2. We calculate z = x^2 / y. If y times z = x^2, and if y = z, it means y and z are the same number, then the number of ways to choose two numbers from v1 is v1 times (v1 - 1) = v1 times (v2 - 1). If y neq z, then the number of ways to choose two numbers from v1 is v1 times v2. Finally, we sum all the ways and divide by 2. The division by 2 is because we count the number of ways for the pair (j, k), but (j, k) and (k, j) are the same way.

The time complexity is O(m times n), and the space complexity is O(m + n). Here, m and n are the lengths of the arrays nums1 and nums2, respectively.

Code

Python Java Go TypeScript

Python

Java

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Brute Force Approach	The time complexity is O(n^3), due to the triple loop. The space complexity is O(1), aside from input storage.
Optimized Hash Map Approach	The time complexity is O(n^2) because of the double nested loop for generating products and using a hash map lookup. The space complexity is O(n^2) due to storing products in a hash map.
Hash Table + Enumeration	—
Hash Table + Enumeration Optimization	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Enumeration	O(n * m^2)	O(1)	Useful for understanding the condition or when input sizes are very small
Hash Map Pair Counting	O(n^2)	O(n)	General case; reduces repeated pair checks using constant-time hash lookups

Video Solution

Leetcode 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers • Fraz • 1,513 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Number of Ways Where Square of Number Is Equal to Product of Two Numbers easy or hard?

The problem is typically rated Medium difficulty. The brute force idea is straightforward, but recognizing that pair products can be converted into factor lookups with a hash map requires algorithmic insight.

Number of Ways Where Square of Number Is Equal to Product of Two Numbers Python/Java solution

Python and Java implementations follow the same pattern: compute the square target, iterate through the second array, and use a hash map to count complements. Each iteration checks if target % num == 0 and adds the frequency of target / num from the map, resulting in O(n^2) time complexity.

How to solve Number of Ways Where Square of Number Is Equal to Product of Two Numbers in O(n^2)?

Iterate through one array and compute the square of each element. While scanning the other array, maintain a frequency map of numbers already seen. If target % current == 0, look up target / current in the map to count matching factors. Repeat the same process with arrays swapped to include both valid triplet types.

What is the best approach for Number of Ways Where Square of Number Is Equal to Product of Two Numbers?

The most efficient approach uses a hash map to count complements while scanning the second array. For each value x, compute target = x^2 and check whether previously seen numbers form a product equal to that target. Hash lookups allow counting valid pairs in constant time, giving an overall time complexity of O(n^2) with O(n) extra space.

Is Number of Ways Where Square of Number Is Equal to Product of Two Numbers asked at Google/Amazon/Meta?

This problem represents a common interview pattern involving pair products and hash-based counting. Variations of the problem appear in interviews at large tech companies where candidates must convert a triple condition into pair lookups using hash maps or frequency tables.

What data structure is used in Number of Ways Where Square of Number Is Equal to Product of Two Numbers?

The optimal solution relies on a hash table (hash map) to store frequencies of numbers while iterating through the array. This allows constant-time lookups for complementary factors that multiply to the target square value.

What is the time complexity of Number of Ways Where Square of Number Is Equal to Product of Two Numbers?

The brute force approach runs in O(n * m^2) time because every squared value is compared with all pairs from the other array. The optimized solution reduces this to O(n^2) by using a hash map to track previously seen numbers and count factor complements in constant time.

Ready to solve this problem?

Practice Number of Ways Where Square of Number Is Equal to Product of Two Numbers with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance43.9%

Approaches4

Reading time25 min

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Brute Force Approach

Code

Complexity

Approach 2: Optimized Hash Map Approach

Code

Complexity

Approach 3: Hash Table + Enumeration

Code

Approach 4: Hash Table + Enumeration Optimization

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents