Loading…

mediumBinary SearchFrequently asked

Pairs

Q: How do you solve Pairs using the Brute Force — All Pairs approach?

When to use it: State it first to fix the definition, then note the O(n²) cost at n = 10⁵. The literal reading: a valid pair is two elements whose difference is k. Enumerate every unordered pair and count the matches. **Why i < j.** Starting the inner loop at i + 1 visits each unordered pair once and never compares an element with itself, so we don't double count or self-match. **Why absolute difference.** Using `Math.abs(arr[i] − arr[j]) == k` handles either ordering of the two values within the pair. **Why we don't ship it.** With n up to 10⁵, n²/2 ≈ 5×10⁹ comparisons is too slow. Sorting plus binary search (or a single hash-set pass) brings it down dramatically. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Pairs using the Sort + Binary Search (Optimal) approach?

When to use it: The answer they want: sort once, then an O(log n) existence query per element for the larger partner. Sort the array. Now every value x has a unique potential partner `x + k` (the larger element of the pair). Binary search the sorted array for `x + k`; each hit is one valid pair. **Why search for the larger partner only.** A pair `(x, x + k)` could be discovered from either side — from x looking up for `x + k`, or from `x + k` looking down for x. To count it exactly once, we fix a direction: every value searches *upward* for `x + k`. The smaller member of each pair finds the larger; the larger member searches for an even larger value that completes a *different* pair (or none). No pair is counted twice and none is missed. **Why distinct values simplify it.** Since all elements are distinct, a successful search means exactly one partner exists — the count increments by one, with no frequency multiplication. **Why exact match, not a boundary search.** The difference must equal k exactly, so we need plain 'does `x + k` exist?' — an equality binary search. (If the problem asked for difference ≤ k, we'd switch to counting a range via two pointers.) **Overflow note.** `x + k` can exceed 2³¹ since x < 2³¹ and k < 10⁹. Compute the key in a 64-bit type (long) before searching to avoid wraparound. **Two-pointer equivalent.** On the sorted array, keep two indices i ≤ j: advance j while `arr[j] − arr[i] < k`; if it equals k, count and advance both; if it exceeds k, advance i. That's O(n) after the sort and avoids the per-element log factor — mention it as the streamlined alternative. Time complexity: O(n log n). Space complexity: O(1).

Binary Search · 16 of 16 · 8 min

Given an array of n distinct integers and a target value k, count the number of unordered pairs of elements whose difference is exactly k.

That is, count the pairs (a, b) with a − b = k (equivalently |a − b| = k), where a and b are two different elements of the array.

In plain English

Every valid pair consists of a smaller value x and a larger value x + k. If we sort the array, the question 'is there a partner for x?' becomes 'does x + k appear in the array?', answerable by binary search in O(log n). Counting from the smaller side (searching for x + k) guarantees each pair is counted exactly once. Distinct values mean a found target contributes exactly one pair.

Examples

Example 1

Input: arr = [1, 5, 3, 4, 2], k = 2
Output: 3
Note: Sorted [1,2,3,4,5]. Pairs with difference 2: (1,3), (2,4), (3,5). Count 3.

Example 2

Input: arr = [1, 3, 5, 8, 6, 4, 2], k = 3
Output: 4
Note: Sorted [1,2,3,4,5,6,8]. Partners x+3 found for 1→4, 2→5, 3→6, 5→8. Count 4.

Example 3

Input: arr = [10, 20, 30], k = 5
Output: 0
Note: No two values differ by exactly 5, so the count is 0.

Constraints

2 ≤ n ≤ 10⁵
0 < k < 10⁹
All array elements are distinct
0 < arr[i] < 2³¹

Clarifying questions4First question: Is the difference exact, or at most k?Explore questions

Q1.Is the difference exact, or at most k?
Exact: a − b = k. That calls for an exact-match search, not a count of everything within a range.
Q2.Are the elements distinct?
Yes. So a successful search for x + k means exactly one pair — no need to multiply by frequencies.
Q3.Are pairs ordered or unordered?
Unordered: (a, b) and (b, a) are the same pair. Searching only for the larger partner x + k counts each once.
Q4.Could x + k overflow?
arr[i] < 2³¹ and k < 10⁹, so x + k can exceed the signed 32-bit range. Use a 64-bit type (long) for the search key, or be careful in languages with fixed-width ints.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Count the pairs of elements whose difference is exactly k. Sort the array, then for each value x do a binary search for x + k; every hit is one valid pair. Sorting makes the lookup O(log n), so the whole thing is O(n log n). Because the values are distinct, each pair is found exactly once (search forward for the larger partner). A sorted two-pointer sweep is the equivalent O(n)-after-sort alternative.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you move from the O(n²) all-pairs scan to a sorted structure that answers 'does x + k exist?' in O(log n) — and whether you avoid double counting by searching only for the larger partner.

Where candidates slip

Searching for both x + k and x − k (double counting each pair), comparing |a − b| in a nested loop and timing out, or using an exact search where the values aren't sorted.

How to stand out

Note that searching only for x + k counts each pair once by construction, then offer the two-pointer sweep as an even cleaner O(n)-after-sort variant and mention a hash set as an O(n) average alternative.

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 — All Pairs	`O(n²)`	`O(1)`	State it first to fix the definition, then note the O(n²) cost at n = 10⁵.	Read
2	Sort + Binary Search (Optimal)Optimal	`O(n log n)`	`O(1)`	The answer they want: sort once, then an O(log n) existence query per element for the larger partner.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewSort the arrayFound?YesNoExplore the full tree

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 — All Pairs

TimeO(n²)SpaceO(1)

State it first to fix the definition, then note the O(n²) cost at n = 10⁵.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What's the most direct way to test whether two elements differ by exactly k?

2Hint 2Explore hint

Compare every unordered pair (i, j) with i < j and check if their difference equals k.

3Hint 3Explore hint

Increment a counter on each match; no early exit since we want the total count.

A · Core idea

The literal reading: a valid pair is two elements whose difference is k. Enumerate every unordered pair and count the matches.

Why i < j. Starting the inner loop at i + 1 visits each unordered pair once and never compares an element with itself, so we don't double count or self-match.

Why absolute difference. Using Math.abs(arr[i] − arr[j]) == k handles either ordering of the two values within the pair.

Why we don't ship it. With n up to 10⁵, n²/2 ≈ 5×10⁹ comparisons is too slow. Sorting plus binary search (or a single hash-set pass) brings it down dramatically.

B · Visual dry run

Interactive dry run

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

arr = [1, 5, 3, 4, 2], k = 2

Array state

i=3 (4)

|4 − 2| = 2 → count++

[0]

[1]

[2]

i ↓

[3]

j ↓

[4]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

Reference implementation previewpublic int pairsBrute(int[] arr, int k) { int n = arr.length, count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (Math.abs((long) arr[i] - arr[j]) == k) {Explore the full code

solution.javaJava

Brute Force — All Pairs — reference

2 teaching notes

1
public int pairsBrute(int[] arr, int k) {
2
    int n = arr.length, count = 0;
3
    for (int i = 0; i < n; i++) {
4
        // j starts at i+1 so each unordered pair is checked once and never
5
        // self-matches.
6
        for (int j = i + 1; j < n; j++) {
7
            // Cast to long so the subtraction can't overflow before abs.
8
            if (Math.abs((long) arr[i] - arr[j]) == k) {
9
                count++;
10
            }
11
        }
12
    }
13
    return count;
14
}

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

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

The inner loop re-asks 'is there a partner for arr[i]?' by scanning everything. That repeated existence question is exactly what a sorted array + binary search (or a hash set) answers in sub-linear / constant time.

ComplexityO(n²) time, O(1) space — Two nested loops over all i < j → n(n−1)/2 ≈ n²/2 comparisons, O(n²).

E · Edge cases and pitfalls3Starting j at 0 — self-matches and double counts.Explore edge cases

Pitfalls

Starting j at 0 — self-matches and double counts.
Subtracting without widening to long — can overflow for large values.
Running O(n²) on n = 10⁵ and timing out.

03.2

Approach 2 of 2 · Optimal

Sort + Binary Search (Optimal)

TimeO(n log n)SpaceO(1)

The answer they want: sort once, then an O(log n) existence query per element for the larger partner.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If the array were sorted, how could you check whether a specific partner value exists without scanning?

2Hint 2Explore hint

For each x, its larger partner is x + k. Binary search the sorted array for that exact value.

3Hint 3Explore hint

Count one for each successful search. Searching only for x + k (the larger side) counts each pair exactly once.

A · Core idea

Sort the array. Now every value x has a unique potential partner x + k (the larger element of the pair). Binary search the sorted array for x + k; each hit is one valid pair.

Why search for the larger partner only. A pair (x, x + k) could be discovered from either side — from x looking up for x + k, or from x + k looking down for x. To count it exactly once, we fix a direction: every value searches upward for x + k. The smaller member of each pair finds the larger; the larger member searches for an even larger value that completes a different pair (or none). No pair is counted twice and none is missed.

Why distinct values simplify it. Since all elements are distinct, a successful search means exactly one partner exists — the count increments by one, with no frequency multiplication.

Why exact match, not a boundary search. The difference must equal k exactly, so we need plain 'does x + k exist?' — an equality binary search. (If the problem asked for difference ≤ k, we'd switch to counting a range via two pointers.)

Overflow note. x + k can exceed 2³¹ since x < 2³¹ and k < 10⁹. Compute the key in a 64-bit type (long) before searching to avoid wraparound.

Two-pointer equivalent. On the sorted array, keep two indices i ≤ j: advance j while arr[j] − arr[i] < k; if it equals k, count and advance both; if it exceeds k, advance i. That's O(n) after the sort and avoids the per-element log factor — mention it as the streamlined alternative.

B · Visual dry run

Interactive dry run

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

arr = [1, 5, 3, 4, 2], k = 2

Array state

x=3

search 3+2=5 → found at index 4

[0]

[1]

x ↓

[2]

[3]

hit ↓

[4]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Sort + Binary Search (Optimal) — optimal

3 teaching notes

1
public int pairs(int[] arr, int k) {
2
    // Binary search needs sorted input; this dominates the runtime at O(n log n).
3
    java.util.Arrays.sort(arr);
4
    int count = 0;
5
    for (int x : arr) {
6
        // Cast to long so x + k can't overflow 2³¹ before the search.
7
        if (binarySearch(arr, (long) x + k)) {
8
            count++;
9
        }
10
    }
11
    return count;
12
}
13
 
14
private boolean binarySearch(int[] arr, long target) {
15
    int lo = 0, hi = arr.length - 1;
16
    while (lo <= hi) {
17
        int mid = (lo + hi) >>> 1;
18
        // Exact match — the difference must equal k precisely.
19
        if (arr[mid] == target) return true;
20
        if (arr[mid] < target) lo = mid + 1;
21
        else hi = mid - 1;
22
    }
23
    return false;
24
}

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

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

Sorting converts a quadratic 'find a partner for everyone' into a logarithmic existence test, and fixing the search direction (always look up for x + k) is the clean trick that prevents double counting without any extra bookkeeping. The same sort-then-search shape solves 'two sum on a sorted array' and 'count pairs with a given difference/sum'.

ComplexityO(n log n) time, O(1) space — Sorting is O(n log n). Then n binary searches at O(log n) each → O(n log n). No extra space beyond the sort (O(1) auxiliary).

E · Edge cases and pitfalls5arr = [10, 20, 30], k = 5 — No search for x+5 (15, 25, 35) succeeds → count 0.Explore edge cases

Edge cases handled

arr = [10, 20, 30], k = 5No search for x+5 (15, 25, 35) succeeds → count 0.
arr = [1, 2], k = 1x=1 finds 2 → count 1; x=2 searches 3, not found. Total 1, counted once from the smaller side.

Pitfalls

Also searching for x − k — counts every pair twice.
Forgetting to widen x + k to long — overflow for large values.
Using an exact search on an unsorted array — sort first.

Practice

Try the solution yourself

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

Editable code previewpublic int pairs(int[] arr, int k) { java.util.Arrays.sort(arr); int count = 0; for (int x : arr) { if (binarySearch(arr, (long) x + k)) {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.

Double counting by searching both directions

If you look for both x + k and x − k, each pair is discovered from both members and counted twice. Fix one direction.

Explore the code comparison

Don't write this

if found(arr, x + k): count += 1
if found(arr, x - k): count += 1

Write this instead

if found(arr, x + k): count += 1   # larger partner only

Exact search on unsorted data

Binary search assumes sorted order; running it on the raw input returns wrong (or random) results.

Explore the code comparison

Don't write this

// no sort
for (int x : arr) if (binarySearch(arr, (long) x + k)) count++;

Write this instead

java.util.Arrays.sort(arr);
for (int x : arr) if (binarySearch(arr, (long) x + k)) count++;

Overflow on the partner value

x < 2³¹ and k < 10⁹, so x + k can exceed Integer.MAX_VALUE and wrap negative, breaking the search.

Explore the code comparison

Don't write this

binarySearch(arr, x + k);          // int + int can overflow

Write this instead

binarySearch(arr, (long) x + k);   // 64-bit key

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort, then binary-search for x + k (the larger partner)

Code pattern to memorize

sort(arr)
count = 0
for x in arr:
    if binarySearch(arr, x + k) found:
        count += 1
return count

Rules to remember

1Search for x + k, the larger partner — each pair (x, x+k) is then discovered exactly once, from its smaller side.
2The array values are distinct, so a found target is one unique pair (no multiplicity bookkeeping).
3Sort first: binary search and two-pointer both require sorted input.
4Difference is exact (= k), not ≤ k — use an exact-match search, not a boundary/upper-bound count.
5Equivalent O(n) sweep: two pointers i, j; advance j while arr[j] − arr[i] < k, count on equality, advance i otherwise.

Use this pattern when

Count pairs satisfying an exact additive relation in a set of distinct values
You can sort, and each query becomes 'does value v exist?'
A 'difference equals k' / 'sum equals target' count over a static array

Choose another pattern when

Difference ≤ k (a range, not exact) → two-pointer window counting instead of exact search
Duplicates allowed and pairs counted with multiplicity → use a frequency map, not a set
Values fit in a small range → a boolean presence array beats sorting

Interview takeaway

Sorting turns 'find a partner with an exact difference' into an O(log n) existence query. Always search for the larger partner (x + k) so each pair is counted once — or sweep two pointers for the same result without per-element search overhead.

Continue

Transfer the pattern to another problem

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

Transferable patternSort-then-search for an exact partner: sorting turns 'find an element with a fixed difference/sum' into an O(log n) existence query, and fixing the search direction (look up for x + k) counts each pair once. The two-pointer sweep is the O(n)-after-sort equivalent. Same shape as Two Sum II and count-pairs-with-sum.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Pairs with difference at most k
Coming soon
Switch the exact search to a two-pointer window count over the sorted array.
Two Sum II — Sorted Array
Coming soon
Sorted input, find a pair summing to target — two pointers or binary search.
Count Pairs with Given Sum
Coming soon
Same idea for sums instead of differences — search for target − x or use a frequency map.

Same pattern

←

Ternary Search on a Unimodal Function

mediumBinary SearchFrequently asked

Pairs

Binary Search · 16 of 16 · 8 min

Given an array of n distinct integers and a target value k, count the number of unordered pairs of elements whose difference is exactly k.

That is, count the pairs (a, b) with a − b = k (equivalently |a − b| = k), where a and b are two different elements of the array.

In plain English

Examples

Example 1

Input: arr = [1, 5, 3, 4, 2], k = 2
Output: 3
Note: Sorted [1,2,3,4,5]. Pairs with difference 2: (1,3), (2,4), (3,5). Count 3.

Example 2

Input: arr = [1, 3, 5, 8, 6, 4, 2], k = 3
Output: 4
Note: Sorted [1,2,3,4,5,6,8]. Partners x+3 found for 1→4, 2→5, 3→6, 5→8. Count 4.

Example 3

Input: arr = [10, 20, 30], k = 5
Output: 0
Note: No two values differ by exactly 5, so the count is 0.

Constraints

2 ≤ n ≤ 10⁵
0 < k < 10⁹
All array elements are distinct
0 < arr[i] < 2³¹

Clarifying questions4First question: Is the difference exact, or at most k?Explore questions

Q1.Is the difference exact, or at most k?
Exact: a − b = k. That calls for an exact-match search, not a count of everything within a range.
Q2.Are the elements distinct?
Yes. So a successful search for x + k means exactly one pair — no need to multiply by frequencies.
Q3.Are pairs ordered or unordered?
Unordered: (a, b) and (b, a) are the same pair. Searching only for the larger partner x + k counts each once.
Q4.Could x + k overflow?
arr[i] < 2³¹ and k < 10⁹, so x + k can exceed the signed 32-bit range. Use a 64-bit type (long) for the search key, or be careful in languages with fixed-width ints.

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 move from the O(n²) all-pairs scan to a sorted structure that answers 'does x + k exist?' in O(log n) — and whether you avoid double counting by searching only for the larger partner.

Where candidates slip

Searching for both x + k and x − k (double counting each pair), comparing |a − b| in a nested loop and timing out, or using an exact search where the values aren't sorted.

How to stand out

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 — All Pairs	`O(n²)`	`O(1)`	State it first to fix the definition, then note the O(n²) cost at n = 10⁵.	Read
2	Sort + Binary Search (Optimal)Optimal	`O(n log n)`	`O(1)`	The answer they want: sort once, then an O(log n) existence query per element for the larger partner.	Read

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 — All Pairs

TimeO(n²)SpaceO(1)

State it first to fix the definition, then note the O(n²) cost at n = 10⁵.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What's the most direct way to test whether two elements differ by exactly k?

2Hint 2Explore hint

Compare every unordered pair (i, j) with i < j and check if their difference equals k.

3Hint 3Explore hint

Increment a counter on each match; no early exit since we want the total count.

A · Core idea

The literal reading: a valid pair is two elements whose difference is k. Enumerate every unordered pair and count the matches.

Why i < j. Starting the inner loop at i + 1 visits each unordered pair once and never compares an element with itself, so we don't double count or self-match.

Why absolute difference. Using Math.abs(arr[i] − arr[j]) == k handles either ordering of the two values within the pair.

Why we don't ship it. With n up to 10⁵, n²/2 ≈ 5×10⁹ comparisons is too slow. Sorting plus binary search (or a single hash-set pass) brings it down dramatically.

B · Visual dry run

Interactive dry run

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

arr = [1, 5, 3, 4, 2], k = 2

Array state

i=3 (4)

|4 − 2| = 2 → count++

[0]

[1]

[2]

i ↓

[3]

j ↓

[4]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Brute Force — All Pairs — reference

2 teaching notes

1
public int pairsBrute(int[] arr, int k) {
2
    int n = arr.length, count = 0;
3
    for (int i = 0; i < n; i++) {
4
        // j starts at i+1 so each unordered pair is checked once and never
5
        // self-matches.
6
        for (int j = i + 1; j < n; j++) {
7
            // Cast to long so the subtraction can't overflow before abs.
8
            if (Math.abs((long) arr[i] - arr[j]) == k) {
9
                count++;
10
            }
11
        }
12
    }
13
    return count;
14
}

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

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

ComplexityO(n²) time, O(1) space — Two nested loops over all i < j → n(n−1)/2 ≈ n²/2 comparisons, O(n²).

E · Edge cases and pitfalls3Starting j at 0 — self-matches and double counts.Explore edge cases

Pitfalls

Starting j at 0 — self-matches and double counts.
Subtracting without widening to long — can overflow for large values.
Running O(n²) on n = 10⁵ and timing out.

03.2

Approach 2 of 2 · Optimal

Sort + Binary Search (Optimal)

TimeO(n log n)SpaceO(1)

The answer they want: sort once, then an O(log n) existence query per element for the larger partner.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If the array were sorted, how could you check whether a specific partner value exists without scanning?

2Hint 2Explore hint

For each x, its larger partner is x + k. Binary search the sorted array for that exact value.

3Hint 3Explore hint

Count one for each successful search. Searching only for x + k (the larger side) counts each pair exactly once.

A · Core idea

Sort the array. Now every value x has a unique potential partner x + k (the larger element of the pair). Binary search the sorted array for x + k; each hit is one valid pair.

Why distinct values simplify it. Since all elements are distinct, a successful search means exactly one partner exists — the count increments by one, with no frequency multiplication.

Overflow note. x + k can exceed 2³¹ since x < 2³¹ and k < 10⁹. Compute the key in a 64-bit type (long) before searching to avoid wraparound.

B · Visual dry run

Interactive dry run

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

arr = [1, 5, 3, 4, 2], k = 2

Array state

x=3

search 3+2=5 → found at index 4

[0]

[1]

x ↓

[2]

[3]

hit ↓

[4]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Sort + Binary Search (Optimal) — optimal

3 teaching notes

1
public int pairs(int[] arr, int k) {
2
    // Binary search needs sorted input; this dominates the runtime at O(n log n).
3
    java.util.Arrays.sort(arr);
4
    int count = 0;
5
    for (int x : arr) {
6
        // Cast to long so x + k can't overflow 2³¹ before the search.
7
        if (binarySearch(arr, (long) x + k)) {
8
            count++;
9
        }
10
    }
11
    return count;
12
}
13
 
14
private boolean binarySearch(int[] arr, long target) {
15
    int lo = 0, hi = arr.length - 1;
16
    while (lo <= hi) {
17
        int mid = (lo + hi) >>> 1;
18
        // Exact match — the difference must equal k precisely.
19
        if (arr[mid] == target) return true;
20
        if (arr[mid] < target) lo = mid + 1;
21
        else hi = mid - 1;
22
    }
23
    return false;
24
}

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

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

ComplexityO(n log n) time, O(1) space — Sorting is O(n log n). Then n binary searches at O(log n) each → O(n log n). No extra space beyond the sort (O(1) auxiliary).

E · Edge cases and pitfalls5arr = [10, 20, 30], k = 5 — No search for x+5 (15, 25, 35) succeeds → count 0.Explore edge cases

Edge cases handled

arr = [10, 20, 30], k = 5No search for x+5 (15, 25, 35) succeeds → count 0.
arr = [1, 2], k = 1x=1 finds 2 → count 1; x=2 searches 3, not found. Total 1, counted once from the smaller side.

Pitfalls

Also searching for x − k — counts every pair twice.
Forgetting to widen x + k to long — overflow for large values.
Using an exact search on an unsorted array — sort first.

Practice

Try the solution yourself

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

Editable code previewpublic int pairs(int[] arr, int k) { java.util.Arrays.sort(arr); int count = 0; for (int x : arr) { if (binarySearch(arr, (long) x + k)) {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.

Double counting by searching both directions

If you look for both x + k and x − k, each pair is discovered from both members and counted twice. Fix one direction.

Explore the code comparison

Don't write this

if found(arr, x + k): count += 1
if found(arr, x - k): count += 1

Write this instead

if found(arr, x + k): count += 1   # larger partner only

Exact search on unsorted data

Binary search assumes sorted order; running it on the raw input returns wrong (or random) results.

Explore the code comparison

Don't write this

// no sort
for (int x : arr) if (binarySearch(arr, (long) x + k)) count++;

Write this instead

java.util.Arrays.sort(arr);
for (int x : arr) if (binarySearch(arr, (long) x + k)) count++;

Overflow on the partner value

x < 2³¹ and k < 10⁹, so x + k can exceed Integer.MAX_VALUE and wrap negative, breaking the search.

Explore the code comparison

Don't write this

binarySearch(arr, x + k);          // int + int can overflow

Write this instead

binarySearch(arr, (long) x + k);   // 64-bit key

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort, then binary-search for x + k (the larger partner)

Code pattern to memorize

sort(arr)
count = 0
for x in arr:
    if binarySearch(arr, x + k) found:
        count += 1
return count

Rules to remember

1Search for x + k, the larger partner — each pair (x, x+k) is then discovered exactly once, from its smaller side.
2The array values are distinct, so a found target is one unique pair (no multiplicity bookkeeping).
3Sort first: binary search and two-pointer both require sorted input.
4Difference is exact (= k), not ≤ k — use an exact-match search, not a boundary/upper-bound count.
5Equivalent O(n) sweep: two pointers i, j; advance j while arr[j] − arr[i] < k, count on equality, advance i otherwise.

Use this pattern when

Count pairs satisfying an exact additive relation in a set of distinct values
You can sort, and each query becomes 'does value v exist?'
A 'difference equals k' / 'sum equals target' count over a static array

Choose another pattern when

Difference ≤ k (a range, not exact) → two-pointer window counting instead of exact search
Duplicates allowed and pairs counted with multiplicity → use a frequency map, not a set
Values fit in a small range → a boolean presence array beats sorting

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

Pairs with difference at most k
Coming soon
Switch the exact search to a two-pointer window count over the sorted array.
Two Sum II — Sorted Array
Coming soon
Sorted input, find a pair summing to target — two pointers or binary search.
Count Pairs with Given Sum
Coming soon
Same idea for sums instead of differences — search for target − x or use a frequency map.

Same pattern

←

Ternary Search on a Unimodal Function