Two Sum Problem

Problem Statement

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.

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.

Examples

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]
Explanation: Because nums[1] + nums[2] == 6, we return [1, 2].

Example 3:

Input: nums = [3, 3], target = 6
Output: [0, 1]

Your Task

Implement the two_sum function in the solution.py file. The function should:

• Take a list of integers nums and an integer target as parameters
• Return a list of two indices where the corresponding numbers add up to the target
• Handle edge cases appropriately

Testing Your Solution

Click the "Check" button to run the test cases and verify your solution works correctly.

Solution Approaches

Approach 1: Brute Force (O(n²) time, O(1) space)

The simplest approach is to use two nested loops to check every possible pair of numbers:

def two_sum_brute_force(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Time Complexity: O(n²) - We check every pair of numbers Space Complexity: O(1) - We only use a constant amount of extra space

Approach 2: Hash Map (O(n) time, O(n) space)

A more efficient approach uses a hash map to store previously seen numbers:

def two_sum_hash_map(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Time Complexity: O(n) - We only need to traverse the array once Space Complexity: O(n) - We store at most n elements in the hash map

Approach 3: Two Pointers (O(n log n) time, O(1) space) - For Sorted Arrays

If the array is sorted, we can use two pointers:

def two_sum_two_pointers(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

Time Complexity: O(n log n) - Due to sorting (if not already sorted) Space Complexity: O(1) - We only use two pointers

Key Insights

1. Hash Map Approach is Optimal: For the general case, the hash map approach provides the best time complexity
2. Trade-offs: The hash map approach trades space for time efficiency
3. Edge Cases: Always consider cases with duplicate numbers and ensure you don't use the same element twice

Interview Tips

• Start with the brute force approach to show you understand the problem
• Mention the time/space complexity trade-offs
• Discuss edge cases and how your solution handles them
• Consider asking clarifying questions about input constraints