LeetCode Problem #1: Two Sum - Explanation and Solutions in Python and JavaScript

Introduction

The Two Sum problem is one of the most popular coding interview questions and is often used to test a candidate's problem-solving and coding skills. In this post, we'll break down the problem, explain the optimal approach, and provide solutions in both Python and JavaScript.

Problem Statement

Given an array of integers nums and an integer target, return the 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:

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

Approach

The brute force approach involves checking every pair of numbers in the array, but this has a time complexity of O(n²). Instead, we can use a hash map (or dictionary) to store the numbers we've seen so far and their indices. This allows us to check if the complement (i.e., target - current number) exists in the hash map in constant time, reducing the time complexity to O(n).

Solution in Python

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

Explanation: We iterate through the array, and for each number, we calculate its complement. If the complement exists in the hash map, we return the indices. Otherwise, we add the current number and its index to the hash map.

Solution in JavaScript

function twoSum(nums, target) {
    const numMap = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (numMap.has(complement)) {
            return [numMap.get(complement), i];
        }
        numMap.set(nums[i], i);
    }
    return [];
}
        

Explanation: Similar to the Python solution, we use a hash map (in this case, a JavaScript Map) to store numbers and their indices. We check if the complement exists in the map and return the indices if found.

Time and Space Complexity

Time Complexity: O(n) - We traverse the list once.
Space Complexity: O(n) - In the worst case, we store all elements in the hash map.

Edge Cases

• No solution exists (though the problem states there is exactly one solution).
• Duplicate numbers in the array.
• Negative numbers in the array.

Conclusion

The Two Sum problem is a great introduction to using hash maps for efficient problem-solving. By understanding this approach, you can solve similar problems like Three Sum or Four Sum. Try solving it on your own and explore related problems on LeetCode!