Topic 24 of 27 · Intermediate
Find distinct indices with a target sum using a hash map
Return the first pair encountered by a left-to-right scan, or {-1,-1}.
IntermediateJunior · 1–3 yearsHashing
C++20; compile with g++ -std=c++20.
Problem statement
Return the first pair encountered by a left-to-right scan, or {-1,-1}.
Find two balancing entries without overflow in complement calculation.
Input: vector<int>, long long target.
Output: pair<int,int>.
- Size <= INT_MAX.
- target is within signed 32-bit range, so subtracting an int fits long long.
Sample 1
Input: [3,3],6
Output: {0,1}Distinct indices may have equal values.
Sample 2
Input: [1],2
Output: {-1,-1}The same index cannot be reused.
Brute-force solution
Check all index pairs with wide arithmetic.
O(n) expected; O(n²) worst-case hash collision behavior.
#include <vector>
#include <unordered_map>
#include <utility>
#include <iostream>
#include <cassert>
std::pair<int,int> pair_sum(const std::vector<int>& a,long long target){std::unordered_map<long long,int> seen;for(int i=0;i<static_cast<int>(a.size());++i){auto it=seen.find(target-a[i]);if(it!=seen.end())return {it->second,i};seen.try_emplace(a[i],i);}return {-1,-1};}
int main() {
auto p=pair_sum({3,3},6);assert(p.first==0 && p.second==1);auto q=pair_sum({},0);assert(q.first==-1);std::cout<<p.first<<" "<<p.second<<"\n";
return 0;
}
Optimized solution
Store earlier values and test the complement before inserting.
- Scan in order.
- Search target-current.
- Preserve first prior index.
#include <vector>
#include <unordered_map>
#include <utility>
#include <iostream>
#include <cassert>
std::pair<int,int> pair_sum(const std::vector<int>& a,long long target){std::unordered_map<long long,int> seen;for(int i=0;i<static_cast<int>(a.size());++i){auto it=seen.find(target-a[i]);if(it!=seen.end())return {it->second,i};seen.try_emplace(a[i],i);}return {-1,-1};}
int main() {
auto p=pair_sum({3,3},6);assert(p.first==0 && p.second==1);auto q=pair_sum({},0);assert(q.first==-1);std::cout<<p.first<<" "<<p.second<<"\n";
return 0;
}
Complexity analysis
Time: O(n) expected; O(n²) worst-case hash collision behavior.
Auxiliary space: O(n)
Test cases
- Duplicate.
- No result.
- INT_MIN/INT_MAX.
Supplied main asserts a duplicate pair and empty input.Common mistakes
- Inserting before lookup.
- Using int for potentially overflowing subtraction.
Key takeaways
- Use wide arithmetic.
- Only match previous indices.
- Qualify hash complexity.
Follow-up challenges
- When would sorted two pointers be preferable?
- How do adversarial hashes change the complexity?