🌱 Keegan's Digital Garden

1. Two Sum

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

brute force approach: O(n^2)
a nested for loop where we check the sum between every possible pair of indices in nums

we can use a hashmap to optimize this

💡 Explanation of Solution

1. init a hashmap 
	- key: number
	- value: index location of that element in nums

2. iterate through nums
	- calculate the complement for the current element (target - nums[i])
	- check if the complement exists in the map already
		- if it does return its index and the current index
		- if not, insert it into the map

3. return an empty array if we cant find anything (this never reaches)

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

💻 Implementation of Solution

```cpp
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // map stores the value and index since we need to return the corresponding indexes of the sum values
        unordered_map<int,int> map;
 
        for(int i=0; i < nums.size(); i++) {
            int complement = target - nums[i];
 
            auto found = map.find(complement);
 
            if(found != map.end()) {
                return{found->second, i};
            }
            else {
                map[nums[i]] = i;
            }
        }
        return {};
    }
};
    //3,2,4
    //3 --> complement = 6-3 = 3
    //  --> not in map, insert 3 into map

Graph View