#1577

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Ways Where Square of Number Is Equal to Product of Two Numbers

Find the number of triplets where the square of a number equals the product of two others, utilizing array scanning and hash lookup.

array hash table math two pointers

Problem Statement

Given two arrays of integers, nums1 and nums2, your task is to return the number of triplets formed where the square of one number is equal to the product of two others, with the condition that the square comes from nums1 and the product comes from nums2. Specifically, find all triplets (i, j, k) where either nums1[i]^2 = nums2[j] * nums2[k] or nums2[i]^2 = nums1[j] * nums1[k].

The arrays nums1 and nums2 can have lengths up to 1000, and the values in these arrays can be as large as 100,000. Your solution must efficiently calculate the number of such triplets using array scanning and hash lookups to minimize time complexity.

Examples

Example 1

Input: nums1 = [7,4], nums2 = [5,2,8,9]

Output: 1

Type 1: (1, 1, 2), nums1[1]2 = nums2[1] * nums2[2]. (42 = 2 * 8).

Example 2

Input: nums1 = [1,1], nums2 = [1,1,1]

Output: 9

All Triplets are valid, because 12 = 1 * 1. Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2). nums1[i]2 = nums2[j] * nums2[k]. Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]2 = nums1[j] * nums1[k].

Example 3

Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]

Output: 2

There are 2 valid triplets. Type 1: (3,0,2). nums1[3]2 = nums2[0] * nums2[2]. Type 2: (3,0,1). nums2[3]2 = nums1[0] * nums1[1].

Constraints

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

Solution Approach

Precompute Frequencies of Squared Values

Start by calculating the square of each element in nums1 and nums2. Use hash tables to store the frequencies of these squared values. This allows for quick lookups during the scanning phase.

Array Scanning and Hash Lookup

Scan through nums1 and nums2 while checking for the conditions: nums1[i]^2 = nums2[j] * nums2[k] or nums2[i]^2 = nums1[j] * nums1[k]. Use the precalculated frequencies of squared values to quickly check if the product of any two numbers in nums2 (or nums1) equals the square of a number from nums1 (or nums2).

Optimize Time Complexity

By using hash tables to store the squared values and their frequencies, you reduce the time complexity of checking conditions from O(n^2) to O(n) in most cases, where n is the length of the arrays. This optimization allows handling the largest inputs within the time limits.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used for the final solution. The precomputing step involves iterating through both arrays, which is O(n) for each array. The scanning step requires checking combinations of elements, which can be reduced to O(n^2) by leveraging hash lookups for fast product checks. Thus, the overall time complexity is typically O(n^2) in most implementations, with some optimizations possible through efficient hashing.

What Interviewers Usually Probe

Can the candidate efficiently use hash tables to store squared values and check combinations?
Does the candidate understand how to optimize time complexity with precomputation and hashing?
Is the candidate able to adapt array scanning with hash lookups to optimize large input handling?

Common Pitfalls or Variants

Common pitfalls

Not leveraging the hash table for fast lookup, leading to a time complexity of O(n^3).
Failing to handle edge cases where no valid triplets exist, which could result in incorrect outputs.
Misunderstanding the problem constraints, especially regarding the relationship between squared values and product combinations.

Follow-up variants

Adjust the problem to use a fixed number of triplets (e.g., 3 numbers) instead of considering all combinations.
Increase the input size, requiring optimization for larger datasets.
Extend the problem to handle negative numbers, which would require careful handling of square values and product calculations.

FAQ

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

The optimal approach uses hash tables to store squared values of nums1 and nums2, and then scans both arrays to check for valid triplet conditions, reducing the time complexity significantly.

How do hash tables help in solving this problem?

Hash tables store the frequencies of squared values, allowing for fast lookups during the scanning process to check if the product of two numbers equals the square of another number.

What are the main challenges in this problem?

The primary challenges include efficiently calculating squared values, handling large input sizes, and ensuring optimal time complexity using hash lookups during array scanning.

What is the time complexity of the best solution for this problem?

The best solution typically has a time complexity of O(n^2), where n is the length of the arrays, due to the combination checks. However, hashing and precomputation optimize it in practice.

Are there any variations of this problem?

Yes, variations include handling larger datasets, considering a fixed number of triplets, or introducing negative numbers, which adds complexity to the product and square checks.

terminal

Solution

Solution 1: Hash Table + Enumeration

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

class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        def count(nums: List[int]) -> Counter:
            cnt = Counter()
            for j in range(len(nums)):
                for k in range(j + 1, len(nums)):
                    cnt[nums[j] * nums[k]] += 1
            return cnt

        def cal(nums: List[int], cnt: Counter) -> int:
            return sum(cnt[x * x] for x in nums)

        cnt1 = count(nums1)
        cnt2 = count(nums2)
        return cal(nums1, cnt2) + cal(nums2, cnt1)

Solution 2: Hash Table + Enumeration Optimization

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

class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        def count(nums: List[int]) -> Counter:
            cnt = Counter()
            for j in range(len(nums)):
                for k in range(j + 1, len(nums)):
                    cnt[nums[j] * nums[k]] += 1
            return cnt

        def cal(nums: List[int], cnt: Counter) -> int:
            return sum(cnt[x * x] for x in nums)

        cnt1 = count(nums1)
        cnt2 = count(nums2)
        return cal(nums1, cnt2) + cal(nums2, cnt1)

Continue Practicing

#1512 number of good pairs #1679 max number of k sum pairs #1442 count triplets that can form two arrays of equal xor