Problem 1577

Abstract / Summary

Count the number of ways to choose two numbers from an array whose product equals the square of a third number.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1577.py

class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        def count(n1, n2):
            result  = 0
            squares = defaultdict(int)
            for n in n1:
                squares[n * n] += 1
            for i in range(len(n2)):
                for j in range(i + 1, len(n2)):
                    result += squares[n2[i] * n2[j]]
            return result

        return count(nums1, nums2) + count(nums2, nums1)
13 lines | 472 bytes | submitted December 8, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 44% (60k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Hash Table
  • Math
  • Two Pointers
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a Solution class with a single public method numTriplets. The method receives two integer arrays, nums1 and nums2, and returns the total number of triplets that satisfy a specific multiplicative relationship: the square of an element from one array must equal the product of two distinct elements from the other array. The algorithm treats the two arrays symmetrically by invoking a helper routine twice-once with the original ordering and once with the arguments swapped-and aggregates the results.

Core Logic

Helper Function count

The inner function count encapsulates the work of finding valid triplets where the square originates from the first argument list (n1) and the product comes from two distinct elements of the second argument list (n2).

def count(n1, n2):
    result  = 0
    squares = defaultdict(int)
    for n in n1:
        squares[n * n] += 1
    for i in range(len(n2)):
        for j in range(i + 1, len(n2)):
            result += squares[n2[i] * n2[j]]
    return result

The routine proceeds in two phases.

The first phase builds a frequency map called squares. For each element n in n1, the square n * n is computed and its occurrence count is incremented. This map enables constant-time lookup of how many times a particular square appears in n1.

The second phase iterates over all unordered pairs of distinct indices (i, j) in n2. For each pair, the product n2[i] * n2[j] is calculated, and the map is consulted to determine how many elements in n1 have a square equal to that product. The count is accumulated in result.

Combining Results

The public method calls count twice, swapping the role of the two input arrays, and returns the sum of both calls.

return count(nums1, nums2) + count(nums2, nums1)

This double invocation ensures that triplets where the square comes from nums1 and the product from nums2 are counted, as well as the converse scenario.

Edge Cases Handled

When either input array is empty, the first loop that populates squares simply produces an empty map, and the nested loops over the second array have no iterations because the length is zero. Consequently, result remains zero, and the method correctly returns zero for the overall count.

If an array contains a single element, the inner double loop over pairs in that array never executes because the range i + 1 to len(n2) yields no valid j. The function therefore contributes zero for that direction, which aligns with the requirement that two distinct elements are needed to form a product.

Duplicate values are naturally accommodated by the frequency map. For example, if n1 contains the same number multiple times, its square entry in squares will have a count greater than one, and each matching product from n2 will add that count to the total, reflecting all possible selections of the squared element.

Similarly, duplicate values in n2 are handled correctly because the pair iteration uses index positions rather than value uniqueness, allowing distinct index pairs that involve equal values to be considered.

Performance Optimizations

The algorithm reduces the problem of matching squares to products to a lookup problem by precomputing all squares of the first list and storing them in a hash map (defaultdict). This transforms what could be a cubic search into a quadratic one, as the expensive product-matching step only needs to query the map rather than scan the first list for each pair.

Using a hash map provides average-case constant-time access for each product lookup, eliminating the need for sorting or binary search. The choice of defaultdict(int) avoids explicit existence checks before incrementing counts, streamlining the construction of the frequency map.

The nested loops over n2 generate each unordered pair exactly once by starting the inner index at i + 1. This avoids redundant pair evaluations and ensures that each distinct combination contributes at most one lookup, preserving the quadratic bound.

By reusing the same helper function for both directions, the code avoids duplication and benefits from the same optimizations regardless of which array supplies the squares. The overall structure keeps memory usage proportional to the size of the first list in each call, as only the squares of that list are stored.

Flow Summary

The execution begins with numTriplets, which immediately delegates to count with the original ordering. Inside count, the squares of the first list are tallied, then every unordered pair of the second list is examined, and matching squares are summed. After the first call returns, the same process repeats with the arguments swapped, and the two partial results are added together to produce the final answer.

The design leverages hash-based counting and careful pair enumeration to efficiently solve the problem while gracefully handling empty inputs, single-element arrays, and duplicate values.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have two boxes filled with numbered blocks. The code is like a little robot designed to find special secret sets of three blocks that work together in a fun way.

The robot starts by taking all the blocks in the first box and multiplying their number by itself to see what their square looks like. It keeps a tally of these squares so it can remember them later. Once it knows all the squares, it picks up two different blocks from the second box, multiplies their numbers together, and checks if that result matches any of the squares it already memorized from the first box. If the numbers match, that is a successful find.

This whole process repeats, but then the robot flips everything around. It takes the blocks from the second box to find the squares, and then it picks up pairs from the first box to see if their product matches one of those squares. It keeps track of every time it finds a match and adds them all up to see how many sets were found in total.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 7 | μ = 6.88 | σ = 1.48

Complexity Analysis

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go TS
Progiez C++ Python Java
github black-shadows C++
charles-wangkai Java
fsq C++
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
wisdompeak C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
fsq C++
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
wisdompeak C++
23 links | 12 authors | 7 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

10 solutions   December 8, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality