Two Sum – All Approaches
Problem: Given an array nums and an integer target, return indices of two
numbers such that they add up to target.
Approach 1: Brute Force
Check all pairs (i, j) see if nums[i] + nums[j] == target.
Time: O(n²) | Space: O(1)
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
Approach 2: Sorting + Two Pointers
Sort the array (store value & index). Use two pointers.
Time: O(n log n) | Space: O(n)
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
vector<pair<int, int>> arr;
for (int i = 0; i < n; i++) {
arr.push_back({nums[i], i});
}
sort(arr.begin(), arr.end());
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left].first + arr[right].first;
if (sum == target) {
return {arr[left].second, arr[right].second};
}
else if (sum < target) {
left++;
}
else {
right--;
}
}
return {};
Approach 3: Hashmap (Best)
}
Use a hashmap to store seen numbers and check complement.
Time: O(n) | Space: O(n)
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (mp.find(complement) != mp.end()) {
return {mp[complement], i};
}
mp[nums[i]] = i;
}
return {};
Summary:
• Brute force = Easy but slow (O(n²))
• Sorting + Two Pointers = Better (O(n log n))
• Hashmap = Fastest (O(n)), best for interviews
