Day 1 - Two Sum

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

How to Approach It
Start with the brute force idea: try every pair of numbers and check if they add up to the target. It works but is inefficient.

The key insight? You don’t need to check every pair. Instead, as you loop through the array, you can ask:
"What number would I need to have seen already to make this current number add up to the target?"

Use a hash map to store numbers you've already seen and their indices. That lets you check in constant time if the complement exists — bringing your solution down to O(n).

Think of it as solving a puzzle one piece at a time, and the hash map is your memory of the pieces you've already placed.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numMap = {}
        n = len(nums)

        for i in range(n):
            complement = target - nums[i]
            if complement in numMap:
                return [numMap[complement], i]
            numMap[nums[i]] = i

        return []  # No solution found