1. Two Sum

Intuition

The Two Sum problem requires us to find two numbers in an array that add up to a target value. The key insight is that for each number we encounter, we need to find its complement (target - current number) in the array. A hash map is the perfect data structure for this because:

1. We can store numbers we’ve seen and their indices
2. We can look up complements in O(1) time
3. We only need to traverse the array once

Approach

The solution uses a hash map to efficiently find pairs of numbers that sum to the target:

1. Create a hash map to store numbers we’ve seen and their indices
2. For each number in the array:
   • Calculate the complement (target - current number)
   • If the complement exists in our hash map, we found our pair
   • If not, store the current number and its index in the hash map
3. Return the indices when a valid pair is found

This approach ensures we only need to traverse the array once, making it very efficient.

Solution Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Stores numbers we've seen and their index: {number: index}
        seen_numbers = {} 
 
        # Loop through each number and its index
        for index, num in enumerate(nums):
            # Calculate the value needed to reach the target
            complement = target - num
 
            # If we've seen the 'complement' before, we found our pair!
            if complement in seen_numbers:
                return [index, seen_numbers[complement]]
            
            # Add the current number and its index to our 'seen' list
            seen_numbers[num] = index
        
        # Should not be reached for typical LeetCode Two Sum problems
        return []

Time & Space Complexity

• Time Complexity: O(n)

  • We only need to traverse the array once
  • Hash map operations (insertion and lookup) are O(1) on average
  • Therefore, the overall time complexity is O(n)

• Space Complexity: O(n)

  • In the worst case, we might need to store n-1 numbers in the hash map
  • This happens when the target sum is found using the last element
  • Therefore, the space complexity is O(n)