MediumNo. 1577

Number of Ways Where Square of Number Is Equal to Product of Two Numbers — LeetCode 1577 Python Solution

Topics
Array, Hash Table, Math, Two Pointers
Reading time
3 min

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]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

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).

Python solution

PythonSolution
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)

Complexity

Time
O(m2 + n2 + m + n)
Space · auxiliary
O(m2 + n2)

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0149Max Points on a LineHard
0202Happy NumberEasy
0268Missing NumberEasy
0349Intersection of Two ArraysEasy
0350Intersection of Two Arrays IIEasy
0380Insert Delete GetRandom O(1)Medium

Frequently asked questions

How hard is LeetCode 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers?

LeetCode 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers is rated Medium on LeetCode.

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

The Python solution on this page runs in O(m2 + n2 + m + n).

What is the space complexity of LeetCode 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers?

The Python solution on this page uses O(m2 + n2) auxiliary space.

What topics does LeetCode 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers cover?

LeetCode 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers is tagged Array, Hash Table, Math and Two Pointers on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.