Problem 923

Abstract / Summary

Given an integer array and an integer target, count how many triplets sum to target considering duplicates in the array.

Note

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

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)
24 lines | 539 bytes | submitted September 28, 2023 | GitHub   18% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 46% (200k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Counting
  • Hash Table
  • Sorting
  • 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 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.

written by openai gpt

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.

written by google gemini

Code Quality

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

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 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
30 links | 17 authors | 8 languages

Videos

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

Solved On The Same Day

32 solutions   September 28, 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