~/leetcode $ 1. Two-Sum

Classic problem, the brute force way would be to check all pairs of elements in the array and return the indices of the two elements that sum to the target.

I feel like the optimal solution to this problem isn’t that intuitive but I’ve come across the problem before so…

The brute force method would take O(n^2) time since we would need to iterate through every pair. The optimal solution is to store the complement of each number we go through (complement being the target minus that number) and its corresponding index. Then, whenever we come across a number that is already in this set of complements, we can return that index and the index of the number that gave us the complement.

This would run in O(n) linear time.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> complements {};
        for (int i = 0; i < nums.size(); i++) {
            if (complements.contains(nums[i])) {
                return vector<int>{i, complements[nums[i]]};
            }
            complements[target - nums[i]] = i;
        }
        return vector<int>{-1, -1};
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: 2m 51s