What is the brute force approach and complexity for 3Sum With Multiplicity?

Three loops over positions; count matches with time complexity O(N³) and space complexity O(1).

What is the optimal approach and complexity for 3Sum With Multiplicity?

Count copies of each value; two pointers over ≤ 101 distinct values; combine with combinatorics with optimal time complexity O(N + W²) and space complexity O(W).

3Sum With Multiplicity

Q: How do you identify the pattern for 3Sum With Multiplicity?

Look for key signals in the prompt: "count triplets i < j < k" indicates k-sum family, but counting, so a match may stand for many triplets.; "repeats count separately" indicates Opposite of 3Sum: equal values must be **counted**, not skipped.; "values 0 ≤ arr[i] ≤ 100" indicates Very few distinct values → squash into counts and work on values, not positions.; "modulo 10^9 + 7" indicates The count can be huge (C(3000,3) ≈ 4.5·10^9) → long long and mod..

Medium·LeetCode #923 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

You are given an integer array arr and a number target.

Count the triplets of positions i < j < k with arr[i] + arr[j] + arr[k] == target.

This time repeats do count: if the same values can be picked from different positions, each choice of positions is a separate triplet. The answer can be huge, so return it modulo 10^9 + 7.

Input

An integer array arr and an integer target.

Output

One integer: the number of position-triplets i < j < k whose values add up to target, modulo 10^9 + 7.

Example 1

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

Output: 20

Values (1, 2, 5) can be picked 2 × 2 × 2 = 8 ways, (1, 3, 4) also 8 ways, (2, 2, 4) 1 × 2 = 2 ways, and (2, 3, 3) 2 × 1 = 2 ways. Total 20.

Example 2

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

Output: 12

Only (1, 2, 2) works. Pick one of the two 1s (2 ways) and two of the four 2s (6 ways): 2 × 6 = 12.

Example 3

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

Output: 1

1 + 2 + 3 = 6, and there is only one way to pick it.

Constraints

• 3 ≤ arr.length ≤ 3000
• 0 ≤ arr[i] ≤ 100
• 0 ≤ target ≤ 300

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“count triplets i < j < k”

→ k-sum family, but counting, so a match may stand for many triplets.

“repeats count separately”

→ Opposite of 3Sum: equal values must be **counted**, not skipped.

“values 0 ≤ arr[i] ≤ 100”

→ Very few distinct values → squash into counts and work on values, not positions.

“modulo 10^9 + 7”

→ The count can be huge (C(3000,3) ≈ 4.5·10^9) → long long and mod.

Approach Complexity Ladder

Brute Force — count every tripletO(N³)O(1)

Three loops over positions; count matches

Better — sort, fix one, two pointers that count runsO(N²)O(1)

Sort; fix i; on a match, count equal runs (cl × cr, or C(m, 2) if both sides are equal)

Optimal — count each value, then 3Sum on distinct valuesO(N + W²)O(W)

Count copies of each value; two pointers over ≤ 101 distinct values; combine with combinatorics

Brute Force Intuition

Try every i < j < k and count the ones whose values add up to target. Take the count modulo 10^9 + 7 at the end.

Recognition rule for this sub-pattern:

Sort, fix one element (or more), and solve the rest as a two-pointer pair problem. Skip duplicates carefully.

Remember this · Two Pointers

Trigger

Sorted array, pairs/triplets with a target, comparing from both ends, compacting an array in place.

Think

If I compare the elements at two positions, can I safely discard one side?

Key question

Which pointer moves, and why can the skipped elements never be the answer?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Two Pointers translate into production architectures and low-level memory mechanics.

LLD Architecture

Circular Buffer & Ring Queue

Two pointer read/write head synchronization in production memory pools.

Explore Track

C++ Internals

Pointers vs References Deep Dive

Pointer arithmetic, dereferencing semantics, and memory layout behind in-place array passes.

Explore Track

C++ Internals

const Correctness & East-Const

Passing read-only spans with const int* without copying buffers.

Explore Track

4Sum