Two Sum - Leetcode (Easy)

#

The Two Sum problem is a classic algorithmic challenge often found on. The problem can be stated as follows:

Problem Statement

#

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.

You can return the answer in any order.

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]

Example 3:

#

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

The Solution

#

Before diving into coding, ensure you thoroughly understand the requirements. You need to find two distinct indices in the array such that their corresponding values sum up to the target.

Consider Edge Cases

#

Think about edge cases such as:

• The array contains negative numbers.
• The array has fewer than two elements.
• The target is positive or negative.

There are several approaches to solve this problem, but we will focus on two efficient methods: the brute force approach and the hash map approach.

Method 1: Brute Force Approach

#

The brute force approach involves checking every possible pair of numbers in the list to determine if they sum to the target. This method is straightforward but inefficient, especially for large arrays.

Algorithm Steps

#

1. Iterate through each element in the array using a loop.
2. For each element, iterate through the subsequent elements to find a pair.
3. For every pair, check if their sum equals the target.
4. If a pair is found, return their indices.

Time and Space Complexity

#

• Time Complexity: O(n²) because for each element, you may need to check all other elements.
• Space Complexity: O(1) since no additional data structures are being used.

Example

#

For nums = [2, 7, 11, 15] and target = 9:

• Compare 2 (index 0) with 7 (index 1): 2 + 7 = 9 (found the pair).

Implementation

#

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]

• Time Complexity: O(n²)
• Space Complexity: O(1)

Method 2: Hash Map Approach

#

The hash map approach utilizes a hash map (or dictionary) to store the indices of the elements as we iterate through the list. This allows us to check if the complement of the current number (i.e., target - nums[i]) exists in constant time.

How a Hash Map Works

#

A hash map is a data structure that stores key-value pairs. It allows for:

• Fast lookups: Average O(1) time complexity for retrieving values based on keys.
• Dynamic sizing: Automatically resizes as more items are added.

In our approach, the keys are the numbers in the array, and the values are their corresponding indices.

Algorithm Steps

#

1. Initialize an empty hash map to store numbers and their indices.
2. Iterate through the array using a loop:
   • For each number num at index i, calculate its complement: complement = target - num.
   • Check if the complement exists in the hash map:
     • If it does, return the indices of the complement and the current number.
   • If it doesn’t, store the current number and its index in the hash map.
3. Continue until a pair is found.

Time and Space Complexity

#

• Time Complexity: O(n) because each number is processed once, and hash map lookups are O(1) on average.
• Space Complexity: O(n) for storing the numbers in the hash map.

Example

#

For nums = [2, 7, 11, 15] and target = 9:

1. Initialize num_to_index = {}.
2. Iterate over nums:
   • For index 0 (value 2):
     • Calculate complement: 9 - 2 = 7. It’s not in the map.
     • Add 2 to the map: num_to_index = {2: 0}.
   • For index 1 (value 7):
     • Calculate complement: 9 - 7 = 2. It is in the map (index 0).
     • Return [0, 1].

Visualization of the Hash Map

#

1. Initial State:

   • num_to_index = {}

2. After Processing 2:

   • num_to_index = {2: 0}

3. After Processing 7:

   • Check 9 - 7 = 2 → Found in map.
   • Return indices [0, 1].

Implementation

#

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

• Time Complexity: O(n)
• Space Complexity: O(n)

Conclusion

#

The hash map approach is significantly more efficient than the brute force method, especially for larger datasets. By leveraging constant time lookups, we can find the two indices that sum to the target effectively. Understanding how hash maps work is crucial, as they are a powerful tool in solving many algorithmic problems.