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)
Difficulty
and has an acceptance rate of about 44% (60k+ submissions).
Typical patterns to solve this problem:
- Array
- Hash Table
- Math
- Two Pointers
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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++ |
Videos
Solved On The Same Day
- problem 1400: Construct K Palindrome Strings
- problem 1442: Count Triplets That Can Form Two Arrays of Equal XOR
- problem 1519: Number of Nodes in the Sub-Tree With the Same Label
- problem 1593: Split a String Into the Max Number of Unique Substrings
- problem 1604: Alert Using Same Key-Card Three or More Times in a One Hour Period
- problem 1638: Count Substrings That Differ by One Character
- problem 1695: Maximum Erasure Value
- problem 1726: Tuple with Same Product
- problem 1368: Minimum Cost to Make at Least One Valid Path in a Grid
Extra
- 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