1. Two Sum

Amazon

Problem

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.

Example 1:

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Solution

Brute Force - O(n²) time - O(1) space

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> solution = {-1, -1};
 
		for (int i = 0; i < nums.size(); i++) {
			for (int j = i + 1; j < nums.size(); j++) {
				if (nums[i] + nums[j] == target) {
					solution.at(0) = i;
					solution.at(1) = j;
					return solution;
				}
			}
		}
		return solution;
	}
};```
 
## Two pass [[Hash Table]] - [[O(n)]] time - [[O(n)]] space
 
```cpp
class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            hash[nums[i]] = i;
        }
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (hash.find(complement) != hash.end() && hash[complement] != i) {
                return {i, hash[complement]};
            }
        }
        return {};
    }
};

One pass Hash Table - O(n) time - O(n) space

1. Create an empty hash table to store elements and their indices.
2. Iterate through the array from left to right.
3. For each element nums[i], calculate the complement by subtracting it from the target: complement = target - nums[i].
4. Check if the complement exists in the hash table. If it does, we have a solution.
5. If the complement does not exist in the hash table, add the current element nums[i] to the hash table with its index as the value.
6. Repeat until we find a solution or reach the end of the array.
7. If no solution is found, return an empty array or an appropriate indicator.

class Solution {
	public:
	vector<int> twoSum(vector<int>& nums, int target) {
		unordered_map<int, int> hash_table;
		int n = nums.size();
		
		for (int i = 0; i < n; i++) {
			int complement = target - nums[i];
			
			if (hash_table.count(complement)) {
				return {i, hash_table[complement]};
			} else {
				hash_table[nums[i]] = i;
			}	
		}
		return {};
	}
};