Arrays & Strings

• 1: 1. Two Sum

1 - 1. Two Sum

Problem Description

LeetCode Problem Link

Given an array of integers nums and an integer target, return indices of the two numbers in nums such that they add up to target.

Constraints:

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

Example:

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

Intuition and Approach

Intuition

For each number in the array, we need its complement (target - number) to form the target sum. Instead of searching for this complement repeatedly, we can use a hash map for O(1) lookups.

Approach

1. Create a hash map to store number-to-index mappings
2. Iterate through the array once:
   • Calculate the complement (target - current number)
   • Check if complement exists in hash map
   • If found, return current index and complement’s index
   • If not found, store current number and its index

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int)
    
    for i, num := range nums {
        complement := target - num
        if j, exists := seen[complement]; exists {
            return []int{j, i}
        }
        seen[num] = i
    }
    return nil
}

Time and Space Complexity

Time Complexity: O(n)

• Single pass through the array
• Hash map operations (insertion and lookup) are O(1)

Space Complexity: O(n)

• Hash map stores at most n elements
• Additional space grows linearly with input size