2 Sum

Practice Link

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Naive Approach:#

Try every pair (i, j) with i < j and check if nums[i] + nums[j] == target. Simple but O(n²) — redundant for large arrays.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        for(int i=0;i<nums.size();i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                if(nums[i] + nums[j] == target)
                    return {i,j};
            }
        }
        return {-1,-1};
    }
};

Time Complexity: O(n^2)

Space Complexity: O(1)

Better Approach - HashMap#

For each element nums[i], check whether its complement target - nums[i] was already seen (stored in the map). If yes, the pair is found. If not, store nums[i] → i in the map. A single pass suffices because we only need to check elements that come before the current index, which are exactly those already inserted. Reduces time to O(n) but requires O(n) extra space.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;

        for(int i=0;i<nums.size();i++)
        {
            if(mp.find(target-nums[i])!=mp.end())
                return {i, mp[target-nums[i]]};
            mp[nums[i]]= i;
        }
        return {-1,-1};
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Optimal Approach#

Store (value, originalIndex) pairs and sort by value. Use two pointers low and high starting at opposite ends. If their sum equals the target, return their original indices; if the sum is too small move low right; if too large move high left. Sorting takes O(n log n) but the two-pointer scan is O(n). The extra O(n) array preserves original indices that would otherwise be lost after sorting.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int,int>> arr;
        for(int i=0;i<nums.size();i++)
        {
            arr.push_back(make_pair(nums[i],i));
        }
        sort(arr.begin(), arr.end());

        int low = 0, high = nums.size()-1;
        while(low<=high)
        {
            int sum = arr[low].first + arr[high].first;
            if(sum == target)
                return {arr[low].second,arr[high].second};
            else if(sum < target)
                low++;
            else
                high--;
        }
        return {-1,-1};
    }
};

Time Complexity: O(n) + O(nlogn)

Space Complexity: O(n)