Pair Sum Match — Problem Statement & Solution Guide
Problem Description
You are provided with an array of integers and a specific target sum. Your task is to determine if there exists at least one pair of distinct indices (i, j) such that the sum of the elements at these positions equals the target value. Note that the indices must be different, meaning you cannot use the same element twice, even if its value appears multiple times in the array.
The input consists of two lines. The first line contains two space-separated integers: n, representing the number of elements in the array, and target, the desired sum. The second line contains n space-separated integers representing the array elements.
Output a single line containing the string "YES" if such a pair exists, or "NO" if no such pair can be formed. The solution should be efficient, ideally operating in linear time relative to the size of the array.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Pair Sum Match"
WHY DOES IT MATTER?
Two‑sum exemplifies the hash‑lookup pattern, a cornerstone for many interview problems that require constant‑time existence checks, such as detecting duplicates, frequency counts, and sliding‑window constraints.
OPTIMIZATION CHALLENGE
The key insight is to transform the additive condition a[i] + a[j] = target into a membership query: does target − a[i] already exist? This flips a quadratic search into a linear scan with constant‑time checks.
REAL-WORLD CONNECTION
In a payment gateway, matching incoming transaction amounts against a list of pending refunds is essentially a two‑sum lookup; using a hash map ensures the system can reconcile millions of records in real time without bottlenecking.
During an interview, write the hash‑set solution first, then discuss edge cases (duplicates, negative numbers) and optionally mention the two‑pointer alternative for sorted inputs to showcase depth.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The Pair Sum Match problem is a classic instance of the two‑sum family, where we need to discover whether any two distinct elements in a collection add up to a given target. A naïve double‑loop checks every possible pair, leading to O(n²) time, which quickly becomes infeasible for large n (e.g., n > 10⁵) due to the quadratic explosion of comparisons. The optimal paradigm leverages a hash‑based lookup: as we iterate through the array, we store each element's complement (target − value) in a hash set and instantly verify if the current element has already been seen as a complement, achieving linear time.
Hash tables provide O(1) average‑case insert and membership operations, turning the problem into a single pass over the data. This approach also respects the distinct‑index constraint because we only consider a complement that was encountered at a previous index, guaranteeing i ≠ j. The method scales gracefully with input size and works for both positive and negative integers, making it the go‑to solution for interview settings and production code where performance guarantees are critical.
Interview Questions on This Problem
Q1How would you modify the two‑sum solution to return all unique pairs that sum to the target instead of just a boolean answer?
Maintain a hash set for complements and another set (or list) to store pairs; before adding a pair, sort the two numbers or use a tuple with ordered indices to avoid duplicates, and continue scanning the array. This still runs in O(n) average time but may require O(k) extra space for k unique pairs.
Q2If the input array is sorted, can you solve the problem without extra space? Explain the trade‑offs.
Yes, use the two‑pointer technique: start one pointer at the beginning and another at the end, move them inward based on the sum compared to the target. This yields O(n) time and O(1) space, but it requires the array to be sorted, which may add O(n log n) preprocessing time if the original order must be preserved.
Q3Why might a hash‑set based solution fail in the worst case, and how would you safeguard against it in a production system?
Hash tables have O(n) worst‑case lookup if many collisions occur (e.g., pathological inputs or poor hash functions). To mitigate, use a robust hash implementation, reserve capacity to avoid rehashing, and optionally fall back to a sorted‑array binary search approach when the load factor exceeds a threshold.
Examples
Input
5 10 3 7 1 9 4
Output
YES
Explanation: We iterate through the array. At index 0, value is 3. We check if (10 - 3) = 7 exists in our seen set. It does not, so we add 3 to the set. At index 1, value is 7. We check if (10 - 7) = 3 exists in the set. It does (added at index 0). Since the indices are distinct (0 and 1), we return YES.
Input
4 15 2 4 6 8
Output
NO
Explanation: We check all pairs. 2+4=6, 2+6=8, 2+8=10, 4+6=10, 4+8=12, 6+8=14. None of these sums equal 15. Alternatively, using a hash set: for 2, need 13 (not seen); for 4, need 11 (not seen); for 6, need 9 (not seen); for 8, need 7 (not seen). No match found, so output is NO.
Input
3 10 5 5 2
Output
YES
Explanation: At index 0, value is 5. Need 5. Set is empty. Add 5. At index 1, value is 5. Need 5. Set contains 5 (from index 0). Since indices 0 and 1 are distinct, the pair (5, 5) sums to 10. Output is YES.
Input
1 5 5
Output
NO
Explanation: The array has only one element. We cannot form a pair with two distinct indices. Therefore, the answer is NO.
Constraints
- 1 <= n <= 10^5
- -10^9 <= nums[i] <= 10^9
- -2*10^9 <= target <= 2*10^9
- All elements in the array are integers.
Optimal Approach & Strategy
Iterate once through the array while storing each needed complement in a hash set; for each element, a constant‑time lookup tells you if a matching partner has already been seen. This reduces the runtime to O(n) with O(n) auxiliary space.
Brute Force Approach
Loop over every possible pair of indices (i, j) and test if arr[i] + arr[j] equals the target. This requires two nested loops, resulting in O(n²) time.
Verified Code Solutions
function hasPairSum(nums, target) {
const seen = new Set();
for (const num of nums) {
const complement = target - num;
if (seen.has(complement)) {
return true;
}
seen.add(num);
}
return false;
}
const fs = require('fs');
const data = fs.readFileSync(0, 'utf-8').split(/\s+/);
let index = 0;
function readInt() {
return parseInt(data[index++]);
}
const n = readInt();
const target = readInt();
const nums = [];
for (let i = 0; i < n; i++) {
nums.push(readInt());
}
if (hasPairSum(nums, target)) {
console.log("YES");
} else {
console.log("NO");
}#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
bool hasPairSum(const vector<int>& nums, int target) {
unordered_set<int> seen;
for (int num : nums) {
int complement = target - num;
if (seen.count(complement)) {
return true;
}
seen.insert(num);
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, target;
if (!(cin >> n >> target)) return 0;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
if (hasPairSum(nums, target)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}import java.util.*;
import java.io.*;
public class Main {
public static boolean hasPairSum(int[] nums, int target) {
Set<Integer> seen = new HashSet<>();
for (int num : nums) {
int complement = target - num;
if (seen.contains(complement)) {
return true;
}
seen.add(num);
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int target = Integer.parseInt(st.nextToken());
int[] nums = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
if (hasPairSum(nums, target)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}def has_pair_sum(nums, target):
seen = set()
for num in nums:
complement = target - num
if complement in seen:
return True
seen.add(num)
return False
if __name__ == "__main__":
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0])
target = int(data[1])
nums = list(map(int, data[2:2+n]))
if has_pair_sum(nums, target):
print("YES")
else:
print("NO")function hasPairSum(nums, target) {
const seen = new Set();
for (const num of nums) {
const complement = target - num;
if (seen.has(complement)) {
return true;
}
seen.add(num);
}
return false;
}
const fs = require('fs');
const data = fs.readFileSync(0, 'utf-8').split(/\s+/);
let index = 0;
function readInt() {
return parseInt(data[index++]);
}
const n = readInt();
const target = readInt();
const nums = [];
for (let i = 0; i < n; i++) {
nums.push(readInt());
}
if (hasPairSum(nums, target)) {
console.log("YES");
} else {
console.log("NO");
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.