Two Sum

Brute Force#

Try every pair (i, j) with i < j and check whether nums[i] + nums[j] == target. Return the indices as soon as a matching pair is found. This is O(n²) and results in a Time Limit Exceeded verdict for large inputs because we redundantly re-examine elements that cannot contribute to the answer.

• Check all pairs

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 vector<int>{i,j};
            }
        }
        return {-1,-1};
    }
};

Time Complexity: O(n^2) --> TLE

Space Complexity: O(1)

Better Solution#

Store each element together with its original index, then sort by value. With a sorted array, we can use two pointers (low from the left, high from the right): if the sum is too small, advance low; if too large, retreat high. Because we preserved original indices alongside the values, we can return the correct answer even after sorting. This runs in O(n log n) for the sort and O(n) extra space for the index pairs — better than O(n²) but the hash map approach below does even better.

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

        sort(eleIdx.begin(), eleIdx.end(), [](const vector<int> &a, const vector<int> &b){
            return a[0] < b[0];
        });

        int low = 0, high = nums.size()-1;

        while(low < high){
            int sum = eleIdx[low][0] + eleIdx[high][0];
            if(sum == target){
                return vector<int> {eleIdx[low][1], eleIdx[high][1]};
            }else if(sum < target){
                low++;
            }else{
                high--;
            }
        }
        return {-1,-1};
    }
};

Time Complexity: O(nlogn)

Space Complexity: O(n)

Optimal Solution#

For each element nums[i], the complement we need is target - nums[i]. If we have already seen that complement at some earlier index, we have found our pair. A hash map records {value → index} as we scan left to right, so each lookup and insert is O(1) on average. This collapses the two-pointer approach into a single pass with O(n) time and O(n) space, and it does not require sorting, preserving original indices naturally.

• Use hashmap for storing previously visited values and there indices

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

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

            valueIdxMap[nums[i]] = i;
        }
        return {-1,-1};
    }
};

Time Complexity: O(n)

Space Complexity: O(n)