LeetCode : 1. Two Sum Solution

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.

You can return the answer in any order.

Example:

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

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

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

Approach:

1. Brute Force

The brute force approach involves checking every pair of numbers to see if they add up to the target.

Algorithm:

1. Iterate through each element in the array with index i.

2. For each element, iterate through the rest of the array starting from index i+1.

3. Check if the sum of the two elements equals the target.

4. If a pair is found, return their indices.

Code:

def two_sum(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]

Code:

function twoSum(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
}

Complexity Analysis:

• Time Complexity: O(n^2)

• Space Complexity: O(1)

2. Two-Pass Hash Table

This approach uses a hash table to store the elements of the array and their indices. In the first pass, we add each element and its index to the hash table. In the second pass, we check if the complement of each element (i.e., target - nums[i]) exists in the hash table.

Algorithm:

1. Initialize an empty hash table.

2. Iterate through the array and add each element and its index to the hash table.

3. Iterate through the array again and for each element, check if target - nums[i] exists in the hash table.

4. If the complement exists and is not the same as the current element, return the indices.

Code:

def two_sum(nums, target):
    hash_table = {}
    for i, num in enumerate(nums):
        hash_table[num] = i
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_table and hash_table[complement] != i:
            return [i, hash_table[complement]]

Code:

function twoSum(nums, target) {
    const hashTable = {};
    for (let i = 0; i < nums.length; i++) {
        hashTable[nums[i]] = i;
    }
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (hashTable[complement] !== undefined && hashTable[complement] !== i) {
            return [i, hashTable[complement]];
        }
    }
}

Complexity Analysis:

• Time Complexity: O(n)

• Space Complexity: O(n)

3. One-Pass Hash Table

This approach improves on the two-pass hash table by combining both steps into a single pass. As we iterate through the array, we simultaneously check for the complement and add the current element to the hash table.

Algorithm:

1. Initialize an empty hash table.

2. Iterate through the array.

3. For each element, calculate its complement (target - nums[i]).

4. Check if the complement exists in the hash table.

5. If the complement exists, return the indices.

6. If the complement does not exist, add the current element and its index to the hash table.

Code:

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

Code:

function twoSum(nums, target) {
    const hashTable = {};
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (hashTable[complement] !== undefined) {
            return [hashTable[complement], i];
        }
        hashTable[nums[i]] = i;
    }
}

Complexity Analysis:

• Time Complexity: O(n)

• Space Complexity: O(n)

Conclusion:

The "Two Sum" problem is a classic exercise in understanding and utilizing hash tables to achieve optimal time complexity. The brute force method, while easy to understand, is inefficient for larger datasets. The two-pass hash table approach offers better performance but can be further optimized. The one-pass hash table approach is the most efficient, providing O(n) time complexity and making it the preferred solution.

By exploring different approaches, you enhance your problem-solving skills and gain insights into the importance of choosing the right data structures for optimization. Happy coding!