← C++ roadmap

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.

  1. Scan in order.
  2. Search target-current.
  3. 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?
Practise C++ with the AI mentor

Can't find a C++ topic you need for exams or placements? Request it and we'll add it.