Target Sum Pairs — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Target Sum Pairs problem optimally.
O(n)O(n)Problem Description
Given an integer array nums and an integer target, locate the two distinct positions i and j (i < j) such that nums[i] + nums[j] equals target. The input guarantees exactly one valid pair and an element cannot be paired with itself. Return the pair of indices as a two‑element array [i, j]. Your algorithm should run in linear time relative to the array size and use only constant extra space beyond the output.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Target Sum Pairs"
WHY DOES IT MATTER?
The two‑sum pattern exemplifies the broader "complement search" technique, which appears in hash‑based deduplication, caching, and cryptographic checksum validation—situations where you need to find a matching counterpart in constant time.
OPTIMIZATION CHALLENGE
Recognizing that the target can be expressed as target‑nums[i] transforms the problem from quadratic pairwise comparison to a single‑pass lookup, collapsing the search space dramatically.
REAL-WORLD CONNECTION
Think of a distributed hash table where each node stores a key; locating a partner node that together satisfies a load‑balancing equation mirrors the complement lookup in two‑sum, enabling rapid pairing without exhaustive scans.
During an interview, write the hash‑map insertion *after* the complement check so you never pair an element with itself; this subtle ordering avoids a common off‑by‑one bug.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The classic "two‑sum" problem asks for two distinct indices whose values add up to a target. A naïve double‑loop checks every pair, yielding O(n²) time, which quickly becomes prohibitive for arrays with millions of elements. The optimal paradigm leverages a hash‑based lookup: as we scan the array once, we store each element's value and its index in a dictionary, then ask whether the complement (target‑value) has already been seen. This single pass guarantees linear time because each element is processed a constant number of times, and the dictionary provides O(1) average‑case look‑ups. The approach also respects the problem’s guarantee of exactly one solution, allowing us to return as soon as the complement is found.
Interview Questions on This Problem
Q1How would you modify the two‑sum solution if the array were sorted and you were required to keep O(1) extra space?
Use a two‑pointer technique: start one pointer at the beginning and another at the end, move the left pointer rightward if the sum is too small, or the right pointer leftward if the sum is too large, until the target is met. This runs in O(n) time and O(1) space.
Q2At a fintech firm you need to detect a pair of transactions that sum to a suspicious amount in a streaming feed. Which data structure would you choose and why?
A hash map (or hash set) keyed by transaction amount to its index allows constant‑time complement checks as each new transaction arrives, supporting real‑time detection with O(1) amortized lookup and insertion.
Q3A startup asks you to return all unique pairs that sum to the target, not just one. How does the algorithm change?
You would still use a hash map, but after finding a pair you must continue scanning, possibly storing used values to avoid duplicates, or sort the array first and apply the two‑pointer method while skipping equal elements, resulting in O(n log n) time if sorting is required, otherwise O(n) average time with extra bookkeeping.
Examples
Input
{"nums":[2,7,11,15],"target":9}Output
[0,1]
Explanation: Scanning from the left, 2 at index 0 needs a complement 7 to reach 9. The value 7 is found at index 1, so the pair [0,1] satisfies the condition.
Input
{"nums":[13,-3,4,8,5],"target":5}Output
[1,3]
Explanation: The element -3 at index 1 requires a complement 8 (5 - (-3)). The value 8 appears at index 3, giving the unique solution [1,3].
Input
{"nums":[0,-1,2,-3,5],"target":2}Output
[0,2]
Explanation: Starting with 0 at index 0, the needed complement is 2. The number 2 is located at index 2, so the answer is [0,2].
Constraints
- 2 <= nums.length <= 100000
- -1000000000 <= nums[i] <= 1000000000
- -1000000000 <= target <= 1000000000
- Exactly one pair of distinct indices satisfies nums[i] + nums[j] = target
Optimal Approach & Strategy
Maintain a hash map of seen values; for each element, look up its complement in O(1) time and return the pair as soon as it is found.
Brute Force Approach
Check every possible pair with two nested loops and return the indices when their sum matches the target.
Code Solutions
function twoSum(nums, target) {
const map = new Map(); // value -> index
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
return [];
}
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = input[idx++];
const nums = input.slice(idx, idx + n); idx += n;
const target = input[idx];
const ans = twoSum(nums, target);
if (ans.length === 2) console.log(ans[0] + ' ' + ans[1]);#include <bits/stdc++.h>
using namespace std;
vector<int> twoSum(const vector<int>& nums, int target) {
unordered_map<int,int> seen; // value -> index
for(int i=0;i<(int)nums.size();++i){
int complement = target - nums[i];
auto it = seen.find(complement);
if(it!=seen.end()){
return {it->second, i};
}
seen[nums[i]] = i;
}
return {};
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
int n; if(!(cin>>n)) return 0; vector<int> nums(n); for(int i=0;i<n;++i)cin>>nums[i]; int target;cin>>target; auto res=twoSum(nums,target); if(res.size()==2) cout<<res[0]<<" "<<res[1]; return 0;}
import java.io.*;
import java.util.*;
public class Main {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>(); // value -> index
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[0];
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
int[] nums = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
int target = Integer.parseInt(br.readLine().trim());
int[] ans = twoSum(nums, target);
if (ans.length == 2) {
System.out.println(ans[0] + " " + ans[1]);
}
}
}
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip().split()
if not data:
sys.exit(0)
it = iter(data)
n = int(next(it))
nums = [int(next(it)) for _ in range(n)]
target = int(next(it))
res = two_sum(nums, target)
if len(res) == 2:
print(res[0], res[1])
function twoSum(nums, target) {
const map = new Map(); // value -> index
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
return [];
}
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = input[idx++];
const nums = input.slice(idx, idx + n); idx += n;
const target = input[idx];
const ans = twoSum(nums, target);
if (ans.length === 2) console.log(ans[0] + ' ' + ans[1]);
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.