18. Find All Pairs With a Given Sum

Given an array and a target value, count the number of index pairs (i, j) with i < j such that arr[i] + arr[j] equals the target. Print that count.

Input: The first line contains an integer n. The second line contains n space-separated integers. The next line contains the target sum. Output: Print a single integer - the count of index pairs (i, j) with i < j whose values sum to the target.

1 <= n <= 10^5

This is the 'count pairs' cousin of the classic Two Sum problem - Two Sum finds the actual indices of ONE pair, while this counts how many valid pairs exist in total, both solved with the same frequency-map technique.

Count how many pairs of positions in an array have values that add up to exactly a given target. Brute force: Check every possible pair of positions directly with two nested loops - this costs O(n²), too slow for large arrays. Optimised: Since you only need to count pairs (not list their exact positions), a frequency map lets you find how many valid partners for the CURRENT element already exist in O(1) time, checking each element against everything seen so far in a single linear pass rather than comparing every pair explicitly.

Sort the array, then use two pointers starting at the two ends: if the sum at the pointers is less than the target, move the left pointer inward to increase the sum; if it's greater, move the right pointer inward to decrease it; if it equals the target, count all pairs formed by the run of equal values at each pointer together (handling duplicates carefully) before moving both pointers past that run. Sorting brings matching values together so the pointers only ever need to sweep inward once, but since sorting discards original index positions, the counting is done by value-multiplicity rather than reconstructing explicit index pairs. Time: O(n log n) Space: O(1) extra (O(n) if sort isn't in-place)

Traverse the array once while maintaining a hash map of how many times each value has appeared so far among elements already processed. For each new element arr[j], look up how many times (target - arr[j]) has already occurred earlier in the array and add that count to the running answer (this exactly counts every valid pair with i < j), then increment arr[j]'s own count in the map. This finds the answer in a single linear pass with no sorting needed at all. Time: O(n) Space: O(n)

Check every pair of indices i < j directly with a nested loop, and increment a counter whenever arr[i] + arr[j] equals the target. This checks literally every possible pair so it's trivially correct, but the number of pairs grows quadratically with the array size. Time: O(n^2) Space: O(1)

1. Build a frequency map of every value in the array as you scan. 2. For each element, check how many times its complement (target minus this element) has ALREADY been seen so far, and add that count to your running total. 3. Then record the current element in the frequency map before moving to the next.

Time: O(n) - one single pass, with instant hash lookups at each step. Space: O(n), for the frequency map of values seen so far.

n = 1 (no pair is possible, count is 0); duplicate values that both satisfy the target sum, as in the example; and n = 10^5 (largest, confirming the hashmap-count approach is O(n)).

Be careful about counting each UNORDERED pair exactly once - checking against values seen ONLY BEFORE the current position (not the whole array) is precisely what avoids double-counting a pair as both (i,j) and (j,i).