1.Two_Sum_(Easy).md

1. Two Sum (Easy)

Link: https://leetcode.com/problems/two-sum/

Question:

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 <= \text{nums.length} <= 10^4$

• $-10^9 <= \text{nums[i]} <= 10^9$

• $-10^9 <= \text{target} <= 10^9$

• Only one valid answer exists.

Hashmap Solution:

For each element from $0^\text{th}$ index to the end, we save the remainder of target - nums[i] into hashmap, so we check if the next element is the remainder we needed in seen, we can just return the previous index with i.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Use hashmap to store {remainder: current index}
        # If remainder from nums exists in hashmap, return [hashmap[remainder], i]
        
        # TC: O(n), n = len(nums), SC: O(n)
        hashmap = {}
        for i in range(len(nums)):
            if nums[i] in hashmap:
                return [hashmap[nums[i]], i]
            else:
                hashmap[target - nums[i]] = i

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

Brute Force Solution:

class Solution(object):
    def twoSum(self, nums, target):
        # Naive approach
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j] == target:
                    return [i, j]

Time Complexity: $O(n^2)$
Space Complexity: $O(1)$