Pairwise Sum Equality — Problem Statement & Solution Guide
Problem Description
Given a non-empty array of integers and a target sum, determine if there exist two elements in the array that add up to the target sum. The two elements can be the same or different.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Pairwise Sum Equality"
WHY DOES IT MATTER?
The two-pointer and hash-set patterns are foundational for solving a wide range of problems involving pairwise relationships, such as finding pairs with a given difference, checking for anagrams, or detecting collisions. Mastery of these patterns allows engineers to quickly identify efficient solutions and avoid costly quadratic approaches.
OPTIMIZATION CHALLENGE
The key insight is that you can transform the problem from "check all pairs" to "for each element, look up its complement in constant time." This reduces the time complexity from O(n^2) to O(n) and, with sorting, to O(n log n) while keeping space minimal.
REAL-WORLD CONNECTION
Consider a distributed logging system where you need to detect if two log entries sum to a critical threshold. By hashing timestamps or event values, you can instantly check for complementary pairs without scanning the entire log, mirroring the two-sum hash approach in a real-time monitoring context.
When explaining this pattern in an interview, emphasize the trade-off between time and space: hash sets give linear time but linear space, whereas sorting gives linear time after an O(n log n) sort but constant space. Highlight that the choice depends on constraints like memory limits or data immutability.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The Pairwise Sum Equality problem is a classic example of the "two-sum" family of problems. A naive approach checks every pair of elements, yielding an O(n^2) time complexity that quickly becomes infeasible for large arrays (e.g., n = 10^5). This brute-force method also consumes only O(1) extra space, but its quadratic runtime dominates the cost.
The optimal paradigm leverages a hash-based lookup or the two-pointer technique after sorting. With a hash set, each element is processed once: we compute the complement (target - current) and check if it already exists in the set. This yields O(n) time and O(n) space. Alternatively, sorting the array in O(n log n) time and then using two pointers moving inward from both ends achieves O(n log n) time and O(1) additional space. Both methods avoid the quadratic explosion by reducing the problem to a single pass or a linear scan over a sorted structure.
These optimizations are essential because modern interview questions often involve large input sizes and tight time constraints. Understanding how to transform a quadratic problem into linear or near-linear time demonstrates mastery of algorithmic thinking, data structures, and complexity analysis—skills that top tech companies actively seek.
Interview Questions on This Problem
Q1How would you modify the two-pointer solution if the array could contain duplicate values and you must ensure the two indices are distinct?
After sorting, use two pointers i and j. While i < j, compute sum = arr[i] + arr[j]. If sum equals target, return true. If sum < target, increment i; if sum > target, decrement j. This naturally handles duplicates because i and j are always distinct indices, and the algorithm only considers pairs where i < j.
Q2A fintech platform needs to detect fraudulent transactions that sum to a suspicious amount. Which data structure would you recommend for real-time detection, and why?
Use a hash set (or hash map) to store transaction amounts seen so far. For each new transaction, compute the complement (suspiciousAmount - current). If the complement exists in the set, a fraudulent pair is found. This gives O(1) average lookup and insertion, enabling real-time detection even under high throughput.
Q3During a coding interview, the interviewer asks: "Can you solve this problem in O(n) time and O(1) space?" How would you respond?
Yes, by first sorting the array in O(n log n) time and then applying the two-pointer technique, which uses only constant extra space. While the time complexity is slightly higher than O(n), the space requirement is O(1), satisfying the interviewer's constraints.
Examples
Input
[2, 7, 11, 15], 9
Output
True
Explanation: Step-by-step: with input [2, 7, 11, 15] and target sum 9, we can find two elements (2 and 7) that add up to the target sum.
Input
[1, 1, 3], 2
Output
True
Explanation: Step-by-step: with input [1, 1, 3] and target sum 2, we can find two elements (1 and 1) that add up to the target sum.
Constraints
- Array size is at most 10^4
- Target sum is a positive integer
- Array elements are distinct integers
- All elements in the array are non-negative
Optimal Approach & Strategy
Iterate through the array once, storing seen numbers in a hash set. For each element, compute the complement (target - element) and check if it exists in the set; if so, return true. This runs in O(n) time and O(n) space.
Brute Force Approach
Check every pair of elements in the array and see if their sum equals the target. This requires nested loops and runs in O(n^2) time with O(1) extra space.
Verified Code Solutions
// Pairwise Sum Equality - Two Pointers solution
function hasPairWithSum(nums, target) {
// Create a copy and sort it
const a = nums.slice().sort((x, y) => x - y);
let l = 0, r = a.length - 1;
while (l <= r) {
const sum = a[l] + a[r];
if (sum === target) return true;
if (sum < target) ++l; // need larger sum
else --r; // need smaller sum
}
return false;
}
// Example usage
const nums = [2, 7, 11, 15];
const target = 9;
console.log(hasPairWithSum(nums, target) ? "True" : "False"); // True#include <bits/stdc++.h>
using namespace std;
bool hasPairWithSum(const vector<int>& nums, int target) {
vector<int> a = nums; // make a copy to sort
sort(a.begin(), a.end());
int l = 0, r = (int)a.size() - 1;
while (l <= r) {
int sum = a[l] + a[r];
if (sum == target) return true;
if (sum < target) ++l; // need larger sum
else --r; // need smaller sum
}
return false;
}
int main() {
vector<int> nums = {2, 7, 11, 15};
int target = 9;
cout << (hasPairWithSum(nums, target) ? "True" : "False") << endl; // True
return 0;
}
import java.util.*;
public class PairwiseSumEquality {
// Returns true if two (possibly same) elements sum to target
public static boolean hasPairWithSum(int[] nums, int target) {
int[] a = nums.clone(); // copy to avoid mutating input
Arrays.sort(a);
int l = 0, r = a.length - 1;
while (l <= r) {
int sum = a[l] + a[r];
if (sum == target) return true;
if (sum < target) ++l; // need larger sum
else --r; // need smaller sum
}
return false;
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
System.out.println(hasPairWithSum(nums, target) ? "True" : "False"); // True
}
}
# Pairwise Sum Equality - Two Pointers solution
def has_pair_with_sum(nums, target):
"""Return True if two (possibly same) elements sum to target.
Uses sorting + two‑pointer technique.
"""
a = sorted(nums)
l, r = 0, len(a) - 1
while l <= r:
s = a[l] + a[r]
if s == target:
return True
if s < target:
l += 1
else:
r -= 1
return False
# Example usage
if __name__ == "__main__":
nums = [2, 7, 11, 15]
target = 9
print("True" if has_pair_with_sum(nums, target) else "False") # True
// Pairwise Sum Equality - Two Pointers solution
function hasPairWithSum(nums, target) {
// Create a copy and sort it
const a = nums.slice().sort((x, y) => x - y);
let l = 0, r = a.length - 1;
while (l <= r) {
const sum = a[l] + a[r];
if (sum === target) return true;
if (sum < target) ++l; // need larger sum
else --r; // need smaller sum
}
return false;
}
// Example usage
const nums = [2, 7, 11, 15];
const target = 9;
console.log(hasPairWithSum(nums, target) ? "True" : "False"); // True
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.