LeetCode Problem 1577

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Two Pointers

Solution

LeetCode 1577, Number of Ways Where Square of Number Is Equal to Product of Two Numbers

Problem Understanding

The problem gives us two integer arrays, nums1 and nums2. We must count the number of valid triplets that satisfy one of two mathematical relationships.

A Type 1 triplet exists when:

• We pick one element from nums1
• We pick two different elements from nums2
• The square of the selected element from nums1 equals the product of the two selected elements from nums2

Formally:

$$nums1[i]^2 = nums2[j] \times nums2[k]$$

where:

$$0 \le i < nums1.length$$

$$0 \le j < k < nums2.length$$

A Type 2 triplet is symmetric:

• We pick one element from nums2
• We pick two different elements from nums1
• The square of the selected element from nums2 equals the product of the two selected elements from nums1

Formally:

$$nums2[i]^2 = nums1[j] \times nums1[k]$$

The final answer is the total number of valid Type 1 and Type 2 triplets.

The constraints are important:

• Each array can contain up to 1000 elements
• Values can be as large as $10^5$

Since the arrays are relatively small, an $O(n^2)$ solution is acceptable. However, a naive cubic solution becomes too slow because checking every possible triplet would require roughly $10^9$ operations in the worst case.

Several edge cases are important:

• Arrays may contain many duplicate values
• Multiple pairs can produce the same product
• Squaring values can produce large numbers, so integer overflow must be considered in languages like Go
• Every value may be identical, which creates many valid combinations
• Some arrays may produce zero valid triplets

The key challenge is efficiently counting pairs whose product equals a target square value.

Approaches

Brute Force Approach

The most direct solution is to explicitly generate every possible triplet.

For every element in nums1, we compute its square. Then we iterate over every pair in nums2 and check whether their product equals the square. After that, we repeat the same process in the opposite direction for Type 2 triplets.

This approach is correct because it exhaustively checks every valid combination defined by the problem statement.

However, the complexity is too large.

If both arrays have length $n$, then:

• For each element in one array, we examine every pair in the other array
• There are $O(n^2)$ pairs
• Repeating this for all elements gives $O(n^3)$

With $n = 1000$, this becomes impractical.

Optimal Approach

The important observation is that we do not need to repeatedly recompute pair products for every target square.

Instead, for a fixed target value:

$$target = x^2$$

we can efficiently count how many pairs in the other array multiply to target.

We use a hash map to store frequencies of previously seen numbers while scanning the array.

For each current value num:

• If target % num == 0, then the complementary value must be:

$$complement = target / num$$

• If we have already seen complement, then every occurrence of it forms a valid pair with the current number

This transforms pair counting into an $O(n)$ process for each target value.

Since we repeat this for every element in both arrays, the total complexity becomes $O(n^2)$, which is efficient enough for the constraints.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Explicitly checks every triplet
Optimal	O(n²)	O(n)	Uses hash maps to count valid pair products efficiently

Algorithm Walkthrough

Step 1: Define a helper function

We create a helper function that:

• Takes one array as the source of squared values
• Takes the other array as the source of pair products
• Counts all valid triplets between them

This avoids duplicating logic.

Step 2: Iterate through each value in the first array

For each value value in the first array:

$$target = value \times value$$

This target is the product we need to find using pairs from the second array.

Step 3: Use a frequency hash map

We scan the second array from left to right.

The hash map stores how many times each number has already appeared.

Example:

frequency[num] += 1

This allows us to instantly determine how many valid complements exist.

Step 4: Check whether the current number can form a valid pair

For each number num in the second array:

• If target % num != 0, then no integer complement exists
• Otherwise:

$$complement = target // num$$

If complement has already appeared in the frequency map, then every occurrence forms a valid pair.

We add:

count += frequency[complement]

Step 5: Update the frequency map

After checking complements, we record the current number in the hash map.

This ordering ensures we only count pairs once and maintain:

$$j < k$$

Step 6: Count both triplet types

We compute:

• Type 1 triplets by squaring elements from nums1
• Type 2 triplets by squaring elements from nums2

The final answer is the sum of both counts.

Why it works

For every squared target value, the algorithm systematically counts all pairs whose product equals that target.

The frequency map guarantees that:

• Every valid pair is counted exactly once
• Duplicate values are handled correctly
• Pair ordering satisfies the required index constraints

Since every possible valid pair is examined through complement matching, the algorithm counts all valid triplets without omission or duplication.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        
        def count_triplets(source: List[int], target_array: List[int]) -> int:
            total = 0

            for value in source:
                target = value * value
                frequency = defaultdict(int)

                for num in target_array:
                    if target % num == 0:
                        complement = target // num
                        total += frequency[complement]

                    frequency[num] += 1

            return total

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

The implementation follows the algorithm directly.

The helper function count_triplets handles one direction of counting. It receives:

• source, whose elements are squared
• target_array, where we search for pair products

For every value in source, we compute the target square.

A defaultdict(int) stores frequencies of numbers already encountered while scanning target_array.

For each current number:

• We check whether it divides the target evenly
• If it does, we compute the complement
• Every previously seen complement contributes valid pairs

The frequency map is updated after the check so that pairs are counted only once.

Finally, we call the helper twice to count both Type 1 and Type 2 triplets.

Go Solution

package main

func numTriplets(nums1 []int, nums2 []int) int {

	countTriplets := func(source []int, targetArray []int) int {
		total := 0

		for _, value := range source {
			target := int64(value) * int64(value)

			frequency := make(map[int64]int)

			for _, num := range targetArray {
				current := int64(num)

				if target%current == 0 {
					complement := target / current

					if count, exists := frequency[complement]; exists {
						total += count
					}
				}

				frequency[current]++
			}
		}

		return total
	}

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

The Go implementation is structurally identical to the Python solution.

The most important Go-specific detail is integer overflow handling. Since values can be as large as $10^5$, squaring produces values up to $10^{10}$, which exceeds 32-bit integer range.

To avoid overflow:

target := int64(value) * int64(value)

All product-related calculations use int64.

The hash map uses:

map[int64]int

to ensure consistent numeric types during complement lookup.

Go slices naturally handle empty arrays, though the problem constraints guarantee arrays contain at least one element.

Worked Examples

Example 1

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

Counting Type 1 Triplets

We square elements from nums1.

Target = 7² = 49

Current Number	Complement Needed	Frequency Map Before	New Triplets
5	49/5 not integer	{}	0
2	49/2 not integer	{5:1}	0
8	49/8 not integer	{5:1,2:1}	0
9	49/9 not integer	{5:1,2:1,8:1}	0

No valid pairs.

Target = 4² = 16

Current Number	Complement Needed	Frequency Map Before	New Triplets
5	not integer	{}	0
2	8	{5:1}	0
8	2	{5:1,2:1}	1
9	not integer	{5:1,2:1,8:1}	0

One valid pair:

$$2 \times 8 = 16$$

Type 1 total = 1

Counting Type 2 Triplets

No valid products exist.

Final answer:

1

Example 2

nums1 = [1,1]
nums2 = [1,1,1]

Type 1

Each 1² = 1.

Every pair of ones in nums2 works.

Pairs in nums2:

$$(0,1), (0,2), (1,2)$$

Total pairs = 3

Since there are 2 elements in nums1:

$$2 \times 3 = 6$$

Type 2

Pairs in nums1:

$$(0,1)$$

Total pairs = 1

Since there are 3 elements in nums2:

$$3 \times 1 = 3$$

Final answer:

6 + 3 = 9

Example 3

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

Type 1

Only:

$$3^2 = 9$$

matches:

$$1 \times 9$$

One valid triplet.

Type 2

Only:

$$7^2 = 49$$

matches:

$$7 \times 7$$

from nums1.

One valid triplet.

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	For each element in one array, we scan the other array once
Space	O(n)	Frequency hash map may store all elements of one array

The helper function processes one array element at a time and scans the opposite array once per element. If both arrays have size $n$, this produces $O(n^2)$ total operations.

The hash map stores frequencies of previously seen values in the scanned array. In the worst case, every value is distinct, so the map requires $O(n)$ additional space.

Test Cases

from typing import List

class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        
        from collections import defaultdict

        def count_triplets(source, target_array):
            total = 0

            for value in source:
                target = value * value
                frequency = defaultdict(int)

                for num in target_array:
                    if target % num == 0:
                        complement = target // num
                        total += frequency[complement]

                    frequency[num] += 1

            return total

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

solution = Solution()

assert solution.numTriplets([7,4], [5,2,8,9]) == 1  # basic valid type 1 case

assert solution.numTriplets([1,1], [1,1,1]) == 9  # all combinations valid

assert solution.numTriplets([7,7,8,3], [1,2,9,7]) == 2  # mixed type 1 and type 2

assert solution.numTriplets([2], [3]) == 0  # arrays too small for pair formation

assert solution.numTriplets([4], [2,8]) == 1  # exactly one valid pair

assert solution.numTriplets([10,10], [100,1,1]) == 2  # duplicate squared values

assert solution.numTriplets([1,2,3], [4,5,6]) == 0  # no valid triplets

assert solution.numTriplets([100000], [100000,100000]) == 0  # large values

assert solution.numTriplets([6], [2,3,6]) == 1  # product uses distinct indices

assert solution.numTriplets([9], [3,3,3]) == 3  # multiple duplicate pairs

assert solution.numTriplets([16], [2,2,8,8]) == 4  # many repeated complement matches

Test Summary

Test	Why
[7,4], [5,2,8,9]	Basic valid Type 1 example
[1,1], [1,1,1]	Heavy duplicate counting
[7,7,8,3], [1,2,9,7]	Mixed triplet types
[2], [3]	No pair possible
[4], [2,8]	Single exact match
[10,10], [100,1,1]	Duplicate source values
[1,2,3], [4,5,6]	No valid products
[100000], [100000,100000]	Large integer handling
[6], [2,3,6]	Pair ordering correctness
[9], [3,3,3]	Multiple duplicate complements
[16], [2,2,8,8]	Repeated pair combinations

Edge Cases

Arrays With Many Duplicate Values

Duplicate values are the most common source of counting mistakes. For example:

nums1 = [1,1]
nums2 = [1,1,1]

A naive implementation might accidentally undercount or overcount repeated combinations.

The frequency map handles duplicates naturally because it stores how many times each complement has already appeared. Every occurrence contributes separately to the total count.

Very Large Numbers

Values can be as large as:

$$10^5$$

Squaring produces:

$$10^{10}$$

This exceeds 32-bit integer range.

The Go implementation explicitly uses int64 for all multiplication and division involving squared values. This guarantees correctness without overflow.

Python integers automatically expand to arbitrary precision, so no special handling is required there.

Arrays Too Small To Form Pairs

If one array has only one element, no pair can be formed from it.

Example:

nums1 = [2]
nums2 = [3]

Since valid triplets require two distinct indices for the product pair, the answer must be zero.

The algorithm naturally handles this because the frequency map never accumulates enough values to create a valid pair.