leetcode-1 Two Sum

[1] Two Sum

Key Concept: Hash Map for O(1) Lookup - Use a hash map to store seen numbers and their indices. For each number, check if (target - current) exists in the map. This is the foundation for many sum-based problems.

Pattern: This is the most fundamental hash map pattern in coding interviews.

# 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.
#
# Example 1:
# Input: nums = [2,7,11,15], target = 9
# Output: [0,1]
# Explanation: nums[0] + nums[1] == 9, 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 <= 10^4
# -10^9 <= nums[i] <= 10^9
# -10^9 <= target <= 10^9
# Only one valid answer exists.

class Solution:
    # Approach 1: Hash Map (Optimal)
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Map: number -> index
        seen = {}

        for i, num in enumerate(nums):
            complement = target - num

            # Check if complement exists
            if complement in seen:
                return [seen[complement], i]

            # Store current number and its index
            seen[num] = i

        return []  # Should never reach here given constraints

    # Approach 2: Brute Force (for comparison)
    def twoSum2(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

# Hash Map: Time O(n), Space O(n)
# Brute Force: Time O(n^2), Space O(1)
#
# Key Pattern: Trade space for time using hash map
# - Store what we've seen
# - For each element, check if its "complement" exists
#
# This pattern extends to:
# - 3Sum (use two pointers after sorting)
# - 4Sum
# - Two Sum II (sorted array - use two pointers)
# - Two Sum III (data structure design)
#
# AirBnB: Fundamental problem, often used as warm-up