{x}
blog image

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

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]2 == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
  • Type 2: Triplet (i, j, k) if nums2[i]2 == 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]2 = nums2[1] * nums2[2]. (42 = 2 * 8).

Example 2:

Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: 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
Explanation: 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 Explanation for LeetCode 1577: Number of Ways Where Square of Number Is Equal to Product of Two Numbers

This problem asks to count triplets satisfying two conditions:

  • Type 1: nums1[i]^2 == nums2[j] * nums2[k] where 0 <= i < len(nums1) and 0 <= j < k < len(nums2).
  • Type 2: nums2[i]^2 == nums1[j] * nums1[k] where 0 <= i < len(nums2) and 0 <= j < k < len(nums1).

The most straightforward approach uses hash tables to efficiently count the triplets. Here's a breakdown of the solution and complexity analysis:

Approach: Hash Tables for Efficient Counting

  1. Counting Product Pairs: For each input array (nums1 and nums2), we create a hash table (dictionary in Python, HashMap in Java, etc.) to store the frequency of each possible product of two distinct elements. For example, if nums = [2, 3, 4], the hash table will contain entries like: 6:1 (23), 8:1 (24), 12:1 (3*4). The key is the product, and the value is its count. This step takes O(n^2) time for an array of length n, as we need to iterate through all pairs.

  2. Counting Valid Triplets: Once we have the product-count hash tables for both arrays, we iterate through the elements of nums1. For each nums1[i], we check if nums1[i]^2 exists as a key in the product-count hash table for nums2. If it exists, the value associated with that key represents the number of valid triplets of Type 1 that involve nums1[i]. We repeat this process for nums2 to count Type 2 triplets.

  3. Summing the Counts: Finally, we sum up the total counts of Type 1 and Type 2 triplets to get the final answer.

Time and Space Complexity Analysis

  • Time Complexity: Dominated by the product pair counting step in Step 1. This step takes O(m^2 + n^2) time, where 'm' is the length of nums1 and 'n' is the length of nums2. The remaining steps have linear time complexity, O(m + n), which is insignificant compared to O(m^2 + n^2). Therefore, the overall time complexity is O(m^2 + n^2).

  • Space Complexity: The space complexity is determined by the size of the hash tables created in Step 1. In the worst case, each hash table can store up to O(n^2) entries (all distinct product pairs). Thus, the overall space complexity is O(m^2 + n^2).

Code Examples (Python, Java, C++, Go, TypeScript)

The code examples below reflect the described approach:

Python:

from collections import Counter
 
class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        def count_products(nums):
            count = Counter()
            for i in range(len(nums)):
                for j in range(i + 1, len(nums)):
                    count[nums[i] * nums[j]] += 1
            return count
 
        prod_count1 = count_products(nums1)
        prod_count2 = count_products(nums2)
 
        ans = 0
        for x in nums1:
            ans += prod_count2.get(x * x, 0)
        for x in nums2:
            ans += prod_count1.get(x * x, 0)
        return ans

Java:

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int numTriplets(int[] nums1, int[] nums2) {
        Map<Long, Integer> prodCount1 = countProducts(nums1);
        Map<Long, Integer> prodCount2 = countProducts(nums2);
 
        int ans = 0;
        for (int x : nums1) {
            ans += prodCount2.getOrDefault((long) x * x, 0);
        }
        for (int x : nums2) {
            ans += prodCount1.getOrDefault((long) x * x, 0);
        }
        return ans;
    }
 
    private Map<Long, Integer> countProducts(int[] nums) {
        Map<Long, Integer> count = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                count.put((long) nums[i] * nums[j], count.getOrDefault((long) nums[i] * nums[j], 0) + 1);
            }
        }
        return count;
    }
}

C++:

#include <vector>
#include <unordered_map>
 
using namespace std;
 
class Solution {
public:
    int numTriplets(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<long long, int> prodCount1 = countProducts(nums1);
        unordered_map<long long, int> prodCount2 = countProducts(nums2);
 
        int ans = 0;
        for (int x : nums1) {
            ans += prodCount2[(long long)x * x];
        }
        for (int x : nums2) {
            ans += prodCount1[(long long)x * x];
        }
        return ans;
    }
 
    unordered_map<long long, int> countProducts(vector<int>& nums) {
        unordered_map<long long, int> count;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                count[(long long)nums[i] * nums[j]]++;
            }
        }
        return count;
    }
};

Go:

func numTriplets(nums1 []int, nums2 []int) int {
	prodCount1 := countProducts(nums1)
	prodCount2 := countProducts(nums2)
 
	ans := 0
	for _, x := range nums1 {
		ans += prodCount2[int64(x*x)]
	}
	for _, x := range nums2 {
		ans += prodCount1[int64(x*x)]
	}
	return ans
}
 
func countProducts(nums []int) map[int64]int {
	count := make(map[int64]int)
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			count[int64(nums[i]*nums[j])]++;
		}
	}
	return count
}

TypeScript:

function numTriplets(nums1: number[], nums2: number[]): number {
    const prodCount1 = countProducts(nums1);
    const prodCount2 = countProducts(nums2);
 
    let ans = 0;
    for (const x of nums1) {
        ans += prodCount2.get(x * x) || 0;
    }
    for (const x of nums2) {
        ans += prodCount1.get(x * x) || 0;
    }
    return ans;
}
 
function countProducts(nums: number[]): Map<number, number> {
    const count = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            const product = nums[i] * nums[j];
            count.set(product, (count.get(product) || 0) + 1);
        }
    }
    return count;
}

Remember to handle potential integer overflow when calculating products, especially for larger input arrays. The use of long long in C++ and int64 in Go addresses this. In languages like Java and TypeScript, casting to long may be necessary. Python's integers handle arbitrary precision, so overflow is less of a direct concern in Python.