1577. Square Equals Product of Two Numbers - Solution

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.

The problem

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.

Python

def numTriplets(nums1, nums2):
    def count_triplets(arr1, arr2):
        count = 0
        for i in range(len(arr1)):
            target = arr1[i] ** 2
            for j in range(len(arr2)):
                for k in range(j + 1, len(arr2)):
                    if arr2[j] * arr2[k] == target:
                        count += 1
        return count

    return count_triplets(nums1, nums2) + count_triplets(nums2, nums1)

Java

public class Solution {
    public int numTriplets(int[] nums1, int[] nums2) {
        return countTriplets(nums1, nums2) + countTriplets(nums2, nums1);
    }

    private int countTriplets(int[] arr1, int[] arr2) {
        int count = 0;
        for (int value : arr1) {
            long target = (long) value * value;
            for (int j = 0; j < arr2.length; j++) {
                for (int k = j + 1; k < arr2.length; k++) {
                    if ((long) arr2[j] * arr2[k] == target) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

C++

#include <vector>
#define long long long
using namespace std;

int numTriplets(vector<int>& nums1, vector<int>& nums2) {
    auto countTriplets = [](const vector<int>& arr1, const vector<int>& arr2) -> int {
        int count = 0;
        for (int num : arr1) {
            long target = (long)num * num;
            for (size_t j = 0; j < arr2.size(); ++j) {
                for (size_t k = j + 1; k < arr2.size(); ++k) {
                    if ((long)arr2[j] * arr2[k] == target) {
                        count++;
                    }
                }
            }
        }
        return count;
    };

    return countTriplets(nums1, nums2) + countTriplets(nums2, nums1);
}

JavaScript

function numTriplets(nums1, nums2) {
    function countTriplets(arr1, arr2) {
        let count = 0;
        for (let i = 0; i < arr1.length; i++) {
            const target = arr1[i] * arr1[i];
            for (let j = 0; j < arr2.length; j++) {
                for (let k = j + 1; k < arr2.length; k++) {
                    if (arr2[j] * arr2[k] === target) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    return countTriplets(nums1, nums2) + countTriplets(nums2, nums1);
}

#include <stdio.h>

int numTriplets(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int countTriplets(int* arr1, int size1, int* arr2, int size2) {
        int count = 0;
        for (int i = 0; i < size1; i++) {
            long target = (long)arr1[i] * arr1[i];
            for (int j = 0; j < size2; j++) {
                for (int k = j + 1; k < size2; k++) {
                    if ((long)arr2[j] * arr2[k] == target) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    return countTriplets(nums1, nums1Size, nums2, nums2Size) + countTriplets(nums2, nums2Size, nums1, nums1Size);
}

public class Solution {
    public int NumTriplets(int[] nums1, int[] nums2) {
        return CountTriplets(nums1, nums2) + CountTriplets(nums2, nums1);
    }

    private int CountTriplets(int[] arr1, int[] arr2) {
        int count = 0;
        foreach (var num in arr1) {
            long target = (long)num * num;
            for (int j = 0; j < arr2.Length; j++) {
                for (int k = j + 1; k < arr2.Length; k++) {
                    if ((long)arr2[j] * arr2[k] == target) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

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.

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.

Python

from collections import defaultdict

def numTriplets(nums1, nums2):
    def count_triplets_via_map(arr1, arr2):
        count = 0
        freq_map = defaultdict(int)
        for i in range(len(arr2)):
            for j in range(i + 1, len(arr2)):
                product = arr2[i] * arr2[j]
                freq_map[product] += 1

        for num in arr1:
            target = num ** 2
            count += freq_map[target]

        return count

    return count_triplets_via_map(nums1, nums2) + count_triplets_via_map(nums2, nums1)

Java

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int numTriplets(int[] nums1, int[] nums2) {
        return countTripletsViaMap(nums1, nums2) + countTripletsViaMap(nums2, nums1);
    }

    private int countTripletsViaMap(int[] arr1, int[] arr2) {
        Map<Long, Integer> freqMap = new HashMap<>();
        int count = 0;

        for (int i = 0; i < arr2.length; i++) {
            for (int j = i + 1; j < arr2.length; j++) {
                long product = (long) arr2[i] * arr2[j];
                freqMap.put(product, freqMap.getOrDefault(product, 0) + 1);
            }
        }

        for (int num : arr1) {
            long target = (long) num * num;
            count += freqMap.getOrDefault(target, 0);
        }

        return count;
    }
}

C++

#include <unordered_map>
#include <vector>
using namespace std;

int numTriplets(vector<int>& nums1, vector<int>& nums2) {
    auto countTripletsViaMap = [](const vector<int>& arr1, const vector<int>& arr2) {
        int count = 0;
        unordered_map<long, int> freqMap;

        for (size_t i = 0; i < arr2.size(); ++i) {
            for (size_t j = i + 1; j < arr2.size(); ++j) {
                long product = (long)arr2[i] * arr2[j];
                freqMap[product]++;
            }
        }

        for (int num : arr1) {
            long target = (long)num * num;
            if (freqMap.count(target)) {
                count += freqMap[target];
            }
        }

        return count;
    };

    return countTripletsViaMap(nums1, nums2) + countTripletsViaMap(nums2, nums1);
}

JavaScript

function numTriplets(nums1, nums2) {
    function countTripletsViaMap(arr1, arr2) {
        let count = 0;
        const freqMap = new Map();

        for (let i = 0; i < arr2.length; i++) {
            for (let j = i + 1; j < arr2.length; j++) {
                const product = arr2[i] * arr2[j];
                freqMap.set(product, (freqMap.get(product) || 0) + 1);
            }
        }

        for (let num of arr1) {
            const target = num * num;
            if (freqMap.has(target)) {
                count += freqMap.get(target);
            }
        }

        return count;
    }

    return countTripletsViaMap(nums1, nums2) + countTripletsViaMap(nums2, nums1);
}

#include <stdio.h>
#include <stdlib.h>

int numTriplets(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int countTripletsViaMap(int* arr1, int size1, int* arr2, int size2) {
        int count = 0;
        int* freqMap = calloc(1000000000, sizeof(int));

        for (int i = 0; i < size2; i++) {
            for (int j = i + 1; j < size2; j++) {
                long product = (long)arr2[i] * arr2[j];
                if (product < 1000000000) freqMap[product]++;
            }
        }

        for (int i = 0; i < size1; i++) {
            long target = (long)arr1[i] * arr1[i];
            if (target < 1000000000) count += freqMap[target];
        }

        free(freqMap);
        return count;
    }

    return countTripletsViaMap(nums1, nums1Size, nums2, nums2Size) + countTripletsViaMap(nums2, nums2Size, nums1, nums1Size);
}

using System;
using System.Collections.Generic;

public class Solution {
    public int NumTriplets(int[] nums1, int[] nums2) {
        return CountTripletsViaMap(nums1, nums2) + CountTripletsViaMap(nums2, nums1);
    }

    private int CountTripletsViaMap(int[] arr1, int[] arr2) {
        Dictionary<long, int> freqMap = new Dictionary<long, int>();
        int count = 0;

        for (int i = 0; i < arr2.Length; i++) {
            for (int j = i + 1; j < arr2.Length; j++) {
                long product = (long)arr2[i] * arr2[j];
                if (!freqMap.ContainsKey(product)) {
                    freqMap[product] = 0;
                }
                freqMap[product]++;
            }
        }

        foreach (var num in arr1) {
            long target = (long)num * num;
            if (freqMap.ContainsKey(target)) {
                count += freqMap[target];
            }
        }

        return count;
    }
}

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.

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.

TypeScript

function numTriplets(nums1: number[], nums2: number[]): number {
    const cnt1 = count(nums1);
    const cnt2 = count(nums2);
    return cal(cnt1, nums2) + cal(cnt2, nums1);
}

function count(nums: number[]): Map<number, number> {
    const cnt: Map<number, number> = new Map();
    for (let j = 0; j < nums.length; ++j) {
        for (let k = j + 1; k < nums.length; ++k) {
            const x = nums[j] * nums[k];
            cnt.set(x, (cnt.get(x) || 0) + 1);
        }
    }
    return cnt;
}

function cal(cnt: Map<number, number>, nums: number[]): number {
    return nums.reduce((acc, x) => acc + (cnt.get(x * x) || 0), 0);
}

func numTriplets(nums1 []int, nums2 []int) int {
	cnt1 := count(nums1)
	cnt2 := count(nums2)
	return cal(cnt1, nums2) + cal(cnt2, nums1)
}

func count(nums []int) map[int]int {
	cnt := map[int]int{}
	for j, x := range nums {
		for _, y := range nums[j+1:] {
			cnt[x*y]++
		}
	}
	return cnt
}

func cal(cnt map[int]int, nums []int) (ans int) {
	for _, x := range nums {
		ans += cnt[x*x]
	}
	return
}

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.

TypeScript

function numTriplets(nums1: number[], nums2: number[]): number {
    const cnt1 = count(nums1);
    const cnt2 = count(nums2);
    return cal(cnt1, nums2) + cal(cnt2, nums1);
}

function count(nums: number[]): Map<number, number> {
    const cnt: Map<number, number> = new Map();
    for (const x of nums) {
        cnt.set(x, (cnt.get(x) || 0) + 1);
    }
    return cnt;
}

function cal(cnt: Map<number, number>, nums: number[]): number {
    let ans: number = 0;
    for (const x of nums) {
        for (const [y, v1] of cnt) {
            const z = Math.floor((x * x) / y);
            if (y * z == x * x) {
                const v2 = cnt.get(z) || 0;
                ans += v1 * (y === z ? v2 - 1 : v2);
            }
        }
    }
    return ans / 2;
}

func numTriplets(nums1 []int, nums2 []int) int {
	cnt1 := count(nums1)
	cnt2 := count(nums2)
	return cal(cnt1, nums2) + cal(cnt2, nums1)
}

func count(nums []int) map[int]int {
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	return cnt
}

func cal(cnt map[int]int, nums []int) (ans int) {
	for _, x := range nums {
		for y, v1 := range cnt {
			z := x * x / y
			if y*z == x*x {
				if v2, ok := cnt[z]; ok {
					if y == z {
						v2--
					}
					ans += v1 * v2
				}
			}
		}
	}
	ans /= 2
	return
}

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	–

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

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.

Number of Ways Where Square of Number Is Equal to Product of Two Numbers solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Hash Map Approach

Approach 3: Hash Table + Enumeration

Approach 4: Hash Table + Enumeration Optimization

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Number of Ways Where Square of Number Is Equal to Product of Two Numbers solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Hash Map Approach

Approach 3: Hash Table + Enumeration

Approach 4: Hash Table + Enumeration Optimization

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems