Loading…

easyArraysFrequently asked

Count Pairs with given sum

Q: How do you solve Count Pairs with given sum using the Brute Force — Nested Pair Scan approach?

When to use it: State it first to define the count, then improve to a single pass. Check every unordered pair directly. The outer loop fixes `i`; the inner loop runs `j` from `i + 1` to the end so each pair `{i, j}` is examined exactly once. **Why `j = i + 1`.** Starting `j` past `i` avoids pairing an element with itself and avoids counting `{i, j}` twice (once as `(i, j)`, once as `(j, i)`). This is the same loop-invariant trick as in Two Sum. **Why it's only a warm-up.** For `n = 10⁵`, ~5×10⁹ comparisons is far too slow. It establishes the definition of the count; the frequency map makes it linear. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Count Pairs with given sum using the Frequency Map — One Pass (Optimal) approach?

When to use it: The answer they want — adapt Two Sum's complement lookup to counting. Walk the array once, maintaining `freq`, a map from value to how many times it has appeared **so far**. For the current element `x`, the number of new pairs it completes is `freq[target − x]` — every earlier element equal to the complement pairs with `x`. Add that to the count, then record `x` by incrementing `freq[x]`. **Why look up before inserting.** By querying `freq` *before* adding `x`, the map contains only elements at earlier indices. So each pair is counted exactly once, at the moment its *later* element is processed. No factor-of-two correction, no separate handling for the `x = target − x` case — equal earlier elements are already in the map with the right multiplicity. **Why a frequency, not an index.** Two Sum stores value → index because it needs one witness. Here duplicates matter: if the complement appeared 3 times before, `x` forms 3 pairs. So we store value → *count*. **Why accumulate, not return.** The task is a total, so we never short-circuit. The accumulator should be wide enough — an all-equal array gives `C(n,2)` pairs, which can overflow a 32-bit int for large `n` (use `long` in Java). Time complexity: O(n). Space complexity: O(n).

Arrays & Hashing · 70 of 83 · 8 min

Given an array arr of n integers and an integer target, count the number of pairs of indices (i, j) with i < j such that arr[i] + arr[j] = target.

Return the count. Values may repeat and may be negative.

In plain English

Tally how many unordered index pairs sum to target. Duplicates multiply the count: if value v appears p times and target − v appears q times (v ≠ target − v), that's p·q pairs; if v = target − v, it's C(p,2). The single-pass complement-frequency method produces this total without explicit casework.

Examples

Example 1

Input: arr = [1, 5, 7, -1, 5], target = 6
Output: 3
Note: (1,5) at indices (0,1), (1,5) at (0,4), and (7,−1) at (2,3). The doubled 5 creates two pairs with the single 1.

Example 2

Input: arr = [1, 1, 1, 1], target = 2
Output: 6
Note: Every pair of 1s sums to 2 → C(4,2) = 6.

Example 3

Input: arr = [10, 12, 10, 15, -1], target = 125
Output: 0
Note: No two values sum to 125 → count stays 0.

Constraints

1 ≤ n ≤ 10⁵
-10⁷ ≤ arr[i] ≤ 10⁷
-10⁷ ≤ target ≤ 10⁷
Pairs are unordered: (i, j) and (j, i) are the same pair

Clarifying questions4First question: Are pairs ordered or unordered?Explore questions

Q1.Are pairs ordered or unordered?
Unordered. (i, j) and (j, i) are the same pair, so each must be counted once — the before-insert lookup guarantees that.
Q2.Can the same element be used twice?
No, i ≠ j. But two different indices holding the same value is a valid pair, e.g. arr = [3, 3], target = 6 → 1 pair.
Q3.Can values be negative?
Yes. The complement target − x works for negatives too; don't assume positivity.
Q4.Do we count or return the pairs?
Count. That's the key difference from Two Sum — we accumulate matches across the whole array instead of returning on the first.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Count the number of index pairs `(i, j)` with `i < j` and `arr[i] + arr[j] = target`. Walk once with a frequency map of values seen so far: for each `x`, add `freq[target − x]` to the running count (every earlier occurrence of the complement forms one pair with the current element), then increment `freq[x]`. O(n) time, O(n) space — and unlike Two Sum we add the frequency rather than returning on the first hit, because we want *all* pairs.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you adapt the complement-lookup pattern from 'find one pair' to 'count all pairs' without double counting, and whether you reason about duplicates.

Where candidates slip

Double counting by scanning the whole map (counting both (i,j) and (j,i)), inserting before the lookup, or storing an index instead of a frequency so duplicates are undercounted.

How to stand out

Note that looking up before inserting makes the count 'pairs with an earlier element', which is exactly each unordered pair once — no division by two, no special case for equal halves.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Nested Pair Scan	`O(n²)`	`O(1)`	State it first to define the count, then improve to a single pass.	Read
2	Frequency Map — One Pass (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want — adapt Two Sum's complement lookup to counting.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewNext element xMore elements?YesNoExplore the full tree

Count, don't return

How to read it:For each element, add the number of earlier complements, then record the element.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Nested Pair Scan

TimeO(n²)SpaceO(1)

State it first to define the count, then improve to a single pass.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

How many unordered pairs are there, and how would you test each one's sum?

2Hint 2Explore hint

Two nested loops with j > i so each pair is visited once.

3Hint 3Explore hint

Increment a counter whenever arr[i] + arr[j] == target.

A · Core idea

Check every unordered pair directly. The outer loop fixes i; the inner loop runs j from i + 1 to the end so each pair {i, j} is examined exactly once.

Why `j = i + 1`. Starting j past i avoids pairing an element with itself and avoids counting {i, j} twice (once as (i, j), once as (j, i)). This is the same loop-invariant trick as in Two Sum.

Why it's only a warm-up. For n = 10⁵, ~5×10⁹ comparisons is far too slow. It establishes the definition of the count; the frequency map makes it linear.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 5, 7, -1, 5], target = 6

Array state

i=0

1+5 and 1+5 → two pairs

i ↓

[0]

[1]

[2]

-1

[3]

[4]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

Reference implementation previewpublic long countPairs(int[] arr, int target) { long count = 0; for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) { if (arr[i] + arr[j] == target) {Explore the full code

solution.javaJava

Brute Force — Nested Pair Scan — reference

2 teaching notes

1
public long countPairs(int[] arr, int target) {
2
    long count = 0;
3
    for (int i = 0; i < arr.length; i++) {
4
        // j starts past i so each unordered pair is counted exactly once.
5
        for (int j = i + 1; j < arr.length; j++) {
6
            if (arr[i] + arr[j] == target) {
7
                // Tally — we never return early because we want all pairs.
8
                count++;
9
            }
10
        }
11
    }
12
    return count;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

The j = i + 1 bound is what makes the brute force count unordered pairs once. Keep that 'each pair once' framing — the optimal version reproduces it by only looking at earlier elements.

ComplexityO(n²) time, O(1) space — n(n−1)/2 pairs, each summed and compared in O(1).

E · Edge cases and pitfalls5arr = [3, 3], target = 6 — Single pair (0,1) → 1.Explore edge cases

Edge cases handled

arr = [3, 3], target = 6Single pair (0,1) → 1.
arr = [1, 2, 3], target = 100No pair matches → 0.

Pitfalls

Starting j at 0 — pairs an element with itself and double counts.
Returning on the first match — this is a count, not a find.
Using int for the accumulator when n is large and many pairs match.

03.2

Approach 2 of 2 · Optimal

Frequency Map — One Pass (Optimal)

TimeO(n)SpaceO(n)

The answer they want — adapt Two Sum's complement lookup to counting.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each element x, how many already-seen elements equal target − x? Each is one pair with x.

2Hint 2Explore hint

Keep a map of value → count of occurrences so far. Look up target − x before inserting x.

3Hint 3Explore hint

Add freq[target − x] to the answer, then bump freq[x]. One pass, all pairs counted once.

A · Core idea

Walk the array once, maintaining freq, a map from value to how many times it has appeared so far. For the current element x, the number of new pairs it completes is freq[target − x] — every earlier element equal to the complement pairs with x. Add that to the count, then record x by incrementing freq[x].

Why look up before inserting. By querying freq before adding x, the map contains only elements at earlier indices. So each pair is counted exactly once, at the moment its later element is processed. No factor-of-two correction, no separate handling for the x = target − x case — equal earlier elements are already in the map with the right multiplicity.

Why a frequency, not an index. Two Sum stores value → index because it needs one witness. Here duplicates matter: if the complement appeared 3 times before, x forms 3 pairs. So we store value → count.

Why accumulate, not return. The task is a total, so we never short-circuit. The accumulator should be wide enough — an all-equal array gives C(n,2) pairs, which can overflow a 32-bit int for large n (use long in Java).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 5, 7, -1, 5], target = 6

Hash-map state

x=5 (index 1)

lookup 1

ValueIndex / state

1→ 1

5→ 1

Match found

need 1, found once → count = 1

Final result3

C · Code with teaching comments

solution.javaJava

Frequency Map — One Pass (Optimal) — optimal

2 teaching notes

1
public long countPairs(int[] arr, int target) {
2
    Map<Integer, Integer> freq = new HashMap<>();
3
    long count = 0;
4
    for (int x : arr) {
5
        // Every earlier element equal to the complement forms one pair with x — counted
6
        // before x is inserted.
7
        count += freq.getOrDefault(target - x, 0);
8
        // Record x's occurrence so later elements can pair with it.
9
        freq.merge(x, 1, Integer::sum);
10
    }
11
    return count;
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

This is the counting twin of Two Sum: same complement-lookup skeleton, but 'store index, return early' becomes 'store frequency, accumulate'. Recognizing that one-line-of-thought difference lets you reuse the pattern across find-vs-count variants (Subarray Sum Equals K is the prefix-sum version of this exact move).

ComplexityO(n) time, O(n) space — Single pass with O(1) average map operations; the map holds up to n distinct keys → O(n) time and space.

E · Edge cases and pitfalls5arr = [1,1,1,1], target = 2 — Each new 1 sees all earlier 1s → 0+1+2+3 = 6 = C(4,2).Explore edge cases

Edge cases handled

arr = [1,1,1,1], target = 2Each new 1 sees all earlier 1s → 0+1+2+3 = 6 = C(4,2).
arr = [4, 2], target = 6x=4 sees nothing; x=2 needs 4, found once → 1.

Pitfalls

Inserting before the lookup — counts an element against itself when 2x = target.
Iterating the whole map per element — that's O(n²) and double counts.
Storing an index instead of a count — undercounts duplicates.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long countPairs(int[] arr, int target) { Map<Integer, Integer> freq = new HashMap<>(); long count = 0; for (int x : arr) { count += freq.getOrDefault(target - x, 0);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Insert before lookup (self-pair / double count)

If x is recorded before the complement lookup and 2x = target, x pairs with itself; more generally it shifts every count and breaks the 'each pair once' invariant.

Explore the code comparison

Don't write this

freq[x] += 1
count += freq[target - x]

Write this instead

count += freq[target - x]
freq[x] += 1

Index instead of frequency

Two Sum stores value → index because it needs one witness. Counting needs multiplicity: storing only the last index loses how many earlier complements exist.

Explore the code comparison

Don't write this

Map<Integer, Integer> lastIndex = new HashMap<>();
// ... if contains complement, count++;

Write this instead

Map<Integer, Integer> freq = new HashMap<>();
// ... count += freq.getOrDefault(target - x, 0);

Overflow on the count

An all-equal array gives C(n,2) pairs ≈ n²/2, which overflows int for n around 10⁵.

Explore the code comparison

Don't write this

int count = 0;

Write this instead

long count = 0;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Complement frequency lookup (count, don't return)

Code pattern to memorize

count = 0
freq = {}
for x in arr:
    count += freq.get(target - x, 0)   # all earlier complements
    freq[x] = freq.get(x, 0) + 1       # then record x

Rules to remember

1Add freq[target − x] before inserting x — this counts the current element against every earlier complement, so each unordered pair is counted exactly once.
2Store value → count, not value → index — you need the multiplicity, since duplicates create multiple pairs.
3Don't return early: this is a counting problem, so accumulate over the whole array.
4Use a count accumulator wide enough for the worst case — all-equal arrays give C(n,2) pairs, which can exceed int for large n.
5Handle the complement equal to the current value naturally: the freq map already holds only earlier equal elements, so x + x = target duplicates are counted correctly without special casing.

Use this pattern when

Count (not just find) pairs/matches that sum or XOR to a target
Unsorted array, duplicates allowed, need multiplicity
One-pass streaming is acceptable
You can phrase the question as 'how many earlier elements complete me?'

Choose another pattern when

Array is sorted and you want O(1) space → two pointers counting pairs
You need the actual pairs/indices, not a count → collect them instead of tallying
You only need one pair → Two Sum's return-on-first-hit
Target relation isn't a simple complement (e.g. product) → adjust the lookup key

Interview takeaway

Counting pairs is Two Sum with two tweaks: keep a frequency *count* instead of an index, and *accumulate* matches instead of returning. Looking up the complement before inserting guarantees each pair is counted once.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternComplement frequency counting. The Two Sum skeleton with two changes: store a count (for duplicates) and accumulate instead of returning. Looking up before inserting counts each unordered pair exactly once.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Two Sum
Find one pair and return indices — store value → index, return on first hit.
Subarray Sum Equals K
Coming soon
Same count-the-complement idea applied to prefix sums.
Count Triplets
Extend frequency counting to triplets by fixing the middle element.

Same pattern

←

Weighted Uniform Strings

Continue · Next problem

Count Triplets

easyArraysFrequently asked

Count Pairs with given sum

Arrays & Hashing · 70 of 83 · 8 min

Given an array arr of n integers and an integer target, count the number of pairs of indices (i, j) with i < j such that arr[i] + arr[j] = target.

Return the count. Values may repeat and may be negative.

In plain English

Examples

Example 1

Input: arr = [1, 5, 7, -1, 5], target = 6
Output: 3
Note: (1,5) at indices (0,1), (1,5) at (0,4), and (7,−1) at (2,3). The doubled 5 creates two pairs with the single 1.

Example 2

Input: arr = [1, 1, 1, 1], target = 2
Output: 6
Note: Every pair of 1s sums to 2 → C(4,2) = 6.

Example 3

Input: arr = [10, 12, 10, 15, -1], target = 125
Output: 0
Note: No two values sum to 125 → count stays 0.

Constraints

1 ≤ n ≤ 10⁵
-10⁷ ≤ arr[i] ≤ 10⁷
-10⁷ ≤ target ≤ 10⁷
Pairs are unordered: (i, j) and (j, i) are the same pair

Clarifying questions4First question: Are pairs ordered or unordered?Explore questions

Q1.Are pairs ordered or unordered?
Unordered. (i, j) and (j, i) are the same pair, so each must be counted once — the before-insert lookup guarantees that.
Q2.Can the same element be used twice?
No, i ≠ j. But two different indices holding the same value is a valid pair, e.g. arr = [3, 3], target = 6 → 1 pair.
Q3.Can values be negative?
Yes. The complement target − x works for negatives too; don't assume positivity.
Q4.Do we count or return the pairs?
Count. That's the key difference from Two Sum — we accumulate matches across the whole array instead of returning on the first.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you adapt the complement-lookup pattern from 'find one pair' to 'count all pairs' without double counting, and whether you reason about duplicates.

Where candidates slip

Double counting by scanning the whole map (counting both (i,j) and (j,i)), inserting before the lookup, or storing an index instead of a frequency so duplicates are undercounted.

How to stand out

Note that looking up before inserting makes the count 'pairs with an earlier element', which is exactly each unordered pair once — no division by two, no special case for equal halves.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Nested Pair Scan	`O(n²)`	`O(1)`	State it first to define the count, then improve to a single pass.	Read
2	Frequency Map — One Pass (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want — adapt Two Sum's complement lookup to counting.	Read

Count, don't return

How to read it:For each element, add the number of earlier complements, then record the element.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Nested Pair Scan

TimeO(n²)SpaceO(1)

State it first to define the count, then improve to a single pass.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

How many unordered pairs are there, and how would you test each one's sum?

2Hint 2Explore hint

Two nested loops with j > i so each pair is visited once.

3Hint 3Explore hint

Increment a counter whenever arr[i] + arr[j] == target.

A · Core idea

Check every unordered pair directly. The outer loop fixes i; the inner loop runs j from i + 1 to the end so each pair {i, j} is examined exactly once.

Why it's only a warm-up. For n = 10⁵, ~5×10⁹ comparisons is far too slow. It establishes the definition of the count; the frequency map makes it linear.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 5, 7, -1, 5], target = 6

Array state

i=0

1+5 and 1+5 → two pairs

i ↓

[0]

[1]

[2]

-1

[3]

[4]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Brute Force — Nested Pair Scan — reference

2 teaching notes

1
public long countPairs(int[] arr, int target) {
2
    long count = 0;
3
    for (int i = 0; i < arr.length; i++) {
4
        // j starts past i so each unordered pair is counted exactly once.
5
        for (int j = i + 1; j < arr.length; j++) {
6
            if (arr[i] + arr[j] == target) {
7
                // Tally — we never return early because we want all pairs.
8
                count++;
9
            }
10
        }
11
    }
12
    return count;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

The j = i + 1 bound is what makes the brute force count unordered pairs once. Keep that 'each pair once' framing — the optimal version reproduces it by only looking at earlier elements.

ComplexityO(n²) time, O(1) space — n(n−1)/2 pairs, each summed and compared in O(1).

E · Edge cases and pitfalls5arr = [3, 3], target = 6 — Single pair (0,1) → 1.Explore edge cases

Edge cases handled

arr = [3, 3], target = 6Single pair (0,1) → 1.
arr = [1, 2, 3], target = 100No pair matches → 0.

Pitfalls

Starting j at 0 — pairs an element with itself and double counts.
Returning on the first match — this is a count, not a find.
Using int for the accumulator when n is large and many pairs match.

03.2

Approach 2 of 2 · Optimal

Frequency Map — One Pass (Optimal)

TimeO(n)SpaceO(n)

The answer they want — adapt Two Sum's complement lookup to counting.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For each element x, how many already-seen elements equal target − x? Each is one pair with x.

2Hint 2Explore hint

Keep a map of value → count of occurrences so far. Look up target − x before inserting x.

3Hint 3Explore hint

Add freq[target − x] to the answer, then bump freq[x]. One pass, all pairs counted once.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 5, 7, -1, 5], target = 6

Hash-map state

x=5 (index 1)

lookup 1

ValueIndex / state

1→ 1

5→ 1

Match found

need 1, found once → count = 1

Final result3

C · Code with teaching comments

solution.javaJava

Frequency Map — One Pass (Optimal) — optimal

2 teaching notes

1
public long countPairs(int[] arr, int target) {
2
    Map<Integer, Integer> freq = new HashMap<>();
3
    long count = 0;
4
    for (int x : arr) {
5
        // Every earlier element equal to the complement forms one pair with x — counted
6
        // before x is inserted.
7
        count += freq.getOrDefault(target - x, 0);
8
        // Record x's occurrence so later elements can pair with it.
9
        freq.merge(x, 1, Integer::sum);
10
    }
11
    return count;
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Single pass with O(1) average map operations; the map holds up to n distinct keys → O(n) time and space.

E · Edge cases and pitfalls5arr = [1,1,1,1], target = 2 — Each new 1 sees all earlier 1s → 0+1+2+3 = 6 = C(4,2).Explore edge cases

Edge cases handled

arr = [1,1,1,1], target = 2Each new 1 sees all earlier 1s → 0+1+2+3 = 6 = C(4,2).
arr = [4, 2], target = 6x=4 sees nothing; x=2 needs 4, found once → 1.

Pitfalls

Inserting before the lookup — counts an element against itself when 2x = target.
Iterating the whole map per element — that's O(n²) and double counts.
Storing an index instead of a count — undercounts duplicates.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Insert before lookup (self-pair / double count)

If x is recorded before the complement lookup and 2x = target, x pairs with itself; more generally it shifts every count and breaks the 'each pair once' invariant.

Explore the code comparison

Don't write this

freq[x] += 1
count += freq[target - x]

Write this instead

count += freq[target - x]
freq[x] += 1

Index instead of frequency

Two Sum stores value → index because it needs one witness. Counting needs multiplicity: storing only the last index loses how many earlier complements exist.

Explore the code comparison

Don't write this

Map<Integer, Integer> lastIndex = new HashMap<>();
// ... if contains complement, count++;

Write this instead

Map<Integer, Integer> freq = new HashMap<>();
// ... count += freq.getOrDefault(target - x, 0);

Overflow on the count

An all-equal array gives C(n,2) pairs ≈ n²/2, which overflows int for n around 10⁵.

Explore the code comparison

Don't write this

int count = 0;

Write this instead

long count = 0;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Complement frequency lookup (count, don't return)

Code pattern to memorize

count = 0
freq = {}
for x in arr:
    count += freq.get(target - x, 0)   # all earlier complements
    freq[x] = freq.get(x, 0) + 1       # then record x

Rules to remember

1Add freq[target − x] before inserting x — this counts the current element against every earlier complement, so each unordered pair is counted exactly once.
2Store value → count, not value → index — you need the multiplicity, since duplicates create multiple pairs.
3Don't return early: this is a counting problem, so accumulate over the whole array.
4Use a count accumulator wide enough for the worst case — all-equal arrays give C(n,2) pairs, which can exceed int for large n.
5Handle the complement equal to the current value naturally: the freq map already holds only earlier equal elements, so x + x = target duplicates are counted correctly without special casing.

Use this pattern when

Count (not just find) pairs/matches that sum or XOR to a target
Unsorted array, duplicates allowed, need multiplicity
One-pass streaming is acceptable
You can phrase the question as 'how many earlier elements complete me?'

Choose another pattern when

Array is sorted and you want O(1) space → two pointers counting pairs
You need the actual pairs/indices, not a count → collect them instead of tallying
You only need one pair → Two Sum's return-on-first-hit
Target relation isn't a simple complement (e.g. product) → adjust the lookup key

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Two Sum
Find one pair and return indices — store value → index, return on first hit.
Subarray Sum Equals K
Coming soon
Same count-the-complement idea applied to prefix sums.
Count Triplets
Extend frequency counting to triplets by fixing the middle element.

Same pattern

←

Weighted Uniform Strings

Continue · Next problem

Count Triplets