Python 0923.py
class Solution:
def threeSumMulti(self, arr: List[int], target: int) -> int:
result = 0
one = defaultdict(int)
two = defaultdict(int)
for x in arr:
# triple
k = x
ij = target - k
if ij in two:
result += two[ij]
# pair
j = x
for j in one:
two[k + j] += one[j]
# single
i = x
one[i] += 1
return result % (10**9 + 7)
Difficulty
and has an acceptance rate of about 46% (200k+ submissions).
Typical patterns to solve this problem:
- Array
- Counting
- Hash Table
- Sorting
- 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 solves the “three-sum multiplicity” problem: given an integer array arr and a target sum, it counts the number of index triples (i, j, k) with i < j < k such that arr[i] + arr[j] + arr[k] == target. The count is returned modulo 10**9 + 7. The algorithm processes the array in a single forward pass while maintaining frequency maps for previously seen values and for previously seen pairs. This design enables the solution to accumulate the answer without explicit nested loops over all triples.
Key Steps
Initialization of Counters
Two hash maps are created using defaultdict(int). The first map, one, records how many times each individual value has appeared so far. The second map, two, records how many unordered pairs of previously seen values sum to a particular total.
result = 0
one = defaultdict(int)
two = defaultdict(int)
These structures start empty, guaranteeing that the algorithm correctly handles an empty input array because no contributions will be added to result.
Processing Each Element as the Third Member of a Triple
For each element x in the array, the algorithm first treats it as the potential third element k of a triple. It computes the complementary sum ij = target - k. If any previously recorded pair sums to ij, those pairs can be combined with the current k to form valid triples. The number of such pairs is retrieved from two and added to result.
k = x
ij = target - k
if ij in two:
result += two[ij]
This step automatically handles the case where multiple identical pairs exist; the stored count reflects all possible pair combinations, and each contributes to the total number of triples.
Updating Pair Frequencies with the Current Element
After accounting for triples, the current element is used as the second member j of new pairs. For every distinct value j that has already appeared (enumerated via the keys of one), a new pair sum k + j is formed, and the count of such pairs is increased by the frequency of j stored in one. This updates two to include all pairs that end at the current index.
j = x
for j in one:
two[k + j] += one[j]
Because one holds exact occurrence counts, this loop correctly aggregates contributions from duplicate values. If the array contains many repeated numbers, the inner loop still iterates only over distinct values, limiting unnecessary work.
Recording the Current Element as a Single Value
Finally, the algorithm records the current element as a potential first member i for future pairs and triples. The frequency map one is incremented for the value i.
i = x
one[i] += 1
By updating one after the pair-generation step, the current element is excluded from forming a pair with itself in the same iteration, preserving the required index ordering i < j < k.
Modulo Reduction of the Result
After the loop finishes, the accumulated count may exceed the 32-bit integer range. The final statement reduces the result modulo 10**9 + 7, which is the standard modulus for this problem.
return result % (10**9 + 7)
Applying the modulus only once at the end avoids repeated costly reductions while still guaranteeing the correct final value.
Edge Cases Handled
When the input array is empty, the loop body never executes, leaving result at zero; the final modulo operation returns zero, which is the correct count of triples. If the array contains fewer than three elements, the same logic applies: no pair or triple can be formed, and the result remains zero.
The algorithm also gracefully handles arrays with many duplicate values. The frequency maps store counts rather than individual indices, so the combinatorial explosion of identical elements is captured through arithmetic accumulation rather than explicit enumeration. For example, if a value appears c times, the contribution of triples consisting solely of that value is automatically accounted for by the incremental updates to two and result.
Large integer values are safely processed because Python integers have arbitrary precision. The only overflow concern is the final modulo, which is applied after all additions, ensuring the intermediate result can grow arbitrarily before reduction without causing errors.
Performance Optimizations Observed
The solution achieves linear time behavior by avoiding explicit triple nested loops. The primary optimization is the use of two hash maps that allow constant-time look-ups and updates for previously seen values and pair sums. By iterating over the distinct keys of one rather than every prior element, the inner loop’s work is bounded by the number of unique values encountered so far, which is often far smaller than the total number of processed elements.
Incremental counting eliminates the need to recompute pair sums from scratch for each new element. Each new element contributes to two only through existing distinct values, and each contribution is a simple addition of a stored frequency. This approach reduces both computational overhead and memory churn compared to constructing explicit pair lists.
Finally, the algorithm postpones the modulo operation until the very end. Performing the reduction only once saves the cost of repeated modular arithmetic inside the main loop, which can be significant when processing large arrays. The use of defaultdict(int) also removes the need for explicit existence checks before incrementing counts, streamlining the code path for each update.
ELI5 - Simplified Explanation
Imagine a big toy box filled with numbered blocks. The goal is to find sets of three blocks that add up to a secret target number. Because there are so many blocks, looking at every single combination one by one would take a very long time. Instead, the code uses a smart way to keep track of what it sees.
Think of three small boxes. The first box saves single blocks. The second box saves pairs of blocks that have already been put together. Whenever a new block is picked up from the floor, it first checks the second box to see if that block completes a team of three that hits the target. If it does, a counter goes up.
After checking for a team of three, the block mixes with all the single blocks in the first box to make new pairs. These pairs get put into the second box for later. Finally, the block joins the first box so it can be used to make pairs when the next block arrives. By doing this in one path through the floor, the computer finds all the matching teams without getting confused, even if the pile of blocks is huge.
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 | Go | Java | TS | ||||
| LeetcodeHelp | C++ | Python | Java | ||||||
| Progiez | C++ | Python | Java | ||||||
| github | everthis | JS | |||||||
| fpdjsns | C++ | ||||||||
| fsq | C++ | ||||||||
| halfrost | Go | ||||||||
| JoshCrozier | JS | ||||||||
| lkwq007 | Python | ||||||||
| martianoff | Scala | ||||||||
| qiyuangong | C++ | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| wisdompeak | C++ | ||||||||
| YuriSpiridonov | Python | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Python, Java | ||||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | ||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||
| Progiez | C++, Java, Python | ||||||||
| everthis | JavaScript | ||||||||
| fpdjsns | C++ | ||||||||
| fsq | C++ | ||||||||
| halfrost | Go | ||||||||
| JoshCrozier | JavaScript | ||||||||
| lkwq007 | Python | ||||||||
| martianoff | Scala | ||||||||
| qiyuangong | C++ | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| wisdompeak | C++ | ||||||||
| YuriSpiridonov | Python |
Videos
Solved On The Same Day
- problem 880: Decoded String at Index
- problem 912: Sort an Array
- problem 973: K Closest Points to Origin
- problem 1010: Pairs of Songs With Total Durations Divisible by 60
- problem 1054: Distant Barcodes
- problem 1079: Letter Tile Possibilities
- problem 1090: Largest Values From Labels
- problem 1347: Minimum Number of Steps to Make Two Strings Anagram
- problem 1366: Rank Teams by Votes
- problem 1419: Minimum Number of Frogs Croaking
- problem 1738: Find Kth Largest XOR Coordinate Value
- problem 1814: Count Nice Pairs in an Array
- problem 1985: Find the Kth Largest Integer in the Array
- problem 2018: Check if Word Can Be Placed In Crossword
- problem 2150: Find All Lonely Numbers in the Array
- problem 2182: Construct String With Repeat Limit
- problem 2225: Find Players With Zero or One Losses
- problem 2232: Minimize Result by Adding Parentheses to Expression
- problem 2244: Minimum Rounds to Complete All Tasks
- problem 2284: Sender With Largest Word Count
- problem 2343: Query Kth Smallest Trimmed Number
- problem 2526: Find Consecutive Integers from a Data Stream
- problem 2844: Minimum Operations to Make a Special Number
- problem 2860: Happy Students
- problem 906: Super Palindromes
- problem 992: Subarrays with K Different Integers
- problem 1106: Parsing A Boolean Expression
- problem 1601: Maximum Number of Achievable Transfer Requests
- problem 2081: Sum of k-Mirror Numbers
- problem 2122: Recover the Original Array
- problem 2416: Sum of Prefix Scores of Strings
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