#923

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

3Sum With Multiplicity

Count all unique triplets in an integer array whose sum equals the target, handling multiplicity efficiently using hashing.

array hash table two pointers sorting counting

Problem Statement

Given an integer array arr and an integer target, return the total number of unique triplets (i, j, k) such that i < j < k and arr[i] + arr[j] + arr[k] == target. The result must be returned modulo 10^9 + 7 to prevent overflow.

For example, in arr = [1,1,2,2,3,3,4,4,5,5] with target = 8, the triplets include (1,2,5), (1,3,4), (2,2,4), (2,3,3) with correct multiplicities, yielding 20 total combinations. Arrays may contain repeated values, requiring careful counting rather than simple combination logic.

Examples

Example 1

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8

Output: 20

Enumerating by the values (arr[i], arr[j], arr[k]): (1, 2, 5) occurs 8 times; (1, 3, 4) occurs 8 times; (2, 2, 4) occurs 2 times; (2, 3, 3) occurs 2 times.

Example 2

Input: arr = [1,1,2,2,2,2], target = 5

Output: 12

arr[i] = 1, arr[j] = arr[k] = 2 occurs 12 times: We choose one 1 from [1,1] in 2 ways, and two 2s from [2,2,2,2] in 6 ways.

Example 3

Input: arr = [2,1,3], target = 6

Output: 1

(1, 2, 3) occured one time in the array so we return 1.

Constraints

3 <= arr.length <= 3000
0 <= arr[i] <= 100
0 <= target <= 300

Solution Approach

Sort and use two-pointer scanning

Sort the array and for each fixed first element, use two pointers for the remaining subarray to find pairs summing to the adjusted target. Count multiplicities carefully when elements are equal to avoid overcounting.

Hash counting of elements

Use a hash map to store the frequency of each number. For every pair (i,j), compute the needed third number and multiply by the frequency of that number in the map, adjusting for index ordering to prevent invalid triplets.

Handle special cases with repeated numbers

When numbers are repeated, compute combinations like C(freq,2) or C(freq,3) depending on how many indices share the same value. This ensures correct multiplicity without enumerating every triplet explicitly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity varies: sorting takes O(n log n), scanning with two pointers is O(n^2), and hash counting may reduce repeated computations. Space complexity is O(101) for the hash map due to the value constraint 0 <= arr[i] <= 100.

What Interviewers Usually Probe

Interviewer may ask how to handle repeated numbers without overcounting.
Interviewer may check if hash counting correctly respects index order i<j<k.
Interviewer may probe understanding of combinatorial counting with multiplicities.

Common Pitfalls or Variants

Common pitfalls

Failing to account for duplicate elements leading to incorrect counts.
Incorrectly applying two-pointer logic without adjusting for identical values.
Returning raw counts without modulo 10^9 + 7 causing overflow.

Follow-up variants

4Sum With Multiplicity extending the pattern to quadruplets.
Targeted Pair Sum With Multiplicity using the same hash counting for pairs.
Subset sum variants with multiplicity constraints on array elements.

FAQ

What is 3Sum With Multiplicity?

It is a problem where you count all triplets in an array whose sum equals a target, considering repeated numbers and returning modulo 10^9 + 7.

How do repeated elements affect the solution?

Repeated elements require combinatorial counting like C(freq,2) or C(freq,3) to account for multiplicity without overcounting.

Can I use a two-pointer approach here?

Yes, after sorting, fix one element and use two pointers on the remaining array, adjusting counts when elements are equal.

What is the best way to handle large arrays efficiently?

Use a hash map to count element frequencies and compute triplet contributions without enumerating all index combinations.

Why modulo 10^9 + 7 is required?

Because the number of triplets can be very large, taking modulo prevents integer overflow and matches problem constraints.

terminal

Solution

Solution 1: Counting + Enumeration

We can use a hash table or an array $cnt$ of length $101$ to count the occurrence of each element in the array $arr$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def threeSumMulti(self, arr: List[int], target: int) -> int:
        mod = 10**9 + 7
        cnt = Counter(arr)
        ans = 0
        for j, b in enumerate(arr):
            cnt[b] -= 1
            for a in arr[:j]:
                c = target - a - b
                ans = (ans + cnt[c]) % mod
        return ans

Continue Practicing

#1782 count pairs of nodes #1048 longest string chain #1054 distant barcodes