C++: Two Sum

Thought Process

To solve the Two Sum problem, we use a hash map to store numbers and their indices as we iterate through the array. For each number, we calculate its complement i.e target - nums[i]. If the complement exists in the map, we return the current index and the stored index. Otherwise, we store the current number and its index in the map. 

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        map<int, int> mp;
        vector<int> ans(2);
        for(int i=0;i<nums.size();i++){
            
            int complement = target - nums[i];
            if(mp.count(complement)){
                ans[0] = i;
                ans[1] = mp[complement];
            }
            else{
                mp.insert(make_pair(nums[i], i));
            }
        }
        return ans;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the array once, and each lookup/insert operation in the map is O(1) on average.

Space Complexity: O(n)

The map stores at most n key-value pairs, where 'n' is the size of the input array.

Code copied!