1. Two Sum

Description on LeetCode

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]`

Constraints:

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

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Breakdown

Although this problem is not overly complex, breaking it down can provide further insight. Essentially we have to find two numbers in an array that add up to a given target value. Our task is to return the indices of these two numbers. If no such pair exists in our array, we return an empty array (or Vector in Rust)

Approach

We'll try two different approaches for this exercise a brute force and a hashmap

1. The brute force version uses nested loops to iterate through the pair of elements. Although it's a simple and straightforward approach it's not the most efficient.
2. The HashMap version is more efficient as we only need to iterate through the array once, and check if the target minus the current element is in the array.

Code

Brute Force Approach

// Function to find two numbers in the array that add up to the target
fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    // Iterate over each element in the array with its index
    for (i, num1) in nums.iter().enumerate() {
        // Iterate over the rest of the array starting from the next element
        for (j, num2) in nums.iter().skip(i + 1).enumerate() {
            // Check if the sum of the current pair equals the target
            if num1 + num2 == target {
                // If a pair is found, return their indices
                return vec![i as i32, (j + i + 1) as i32];
            }
        }
    }
    // Return an empty array if no pair is found
    vec![]
}

HashMap Approach

use std::collections::HashMap; // Import the HashMap from the standard library

// Function to find two numbers in the array that add up to the target
fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut hm = HashMap::new(); // Create a new, empty HashMap

    // Iterate over each element in the array with its index
    for (i, num) in nums.iter().enumerate() {
        let complement = target - num; // Calculate the complement of the current number

        // Check if the complement is already in the HashMap
        if let Some(&index) = hm.get(&complement){
            // If found, return the indices of the complement and the current number
            return vec![index as i32, i as i32];
        }
        // Insert the current number and its index into the HashMap
        hm.insert(*num, i);
    }
    // Return an empty array if no pair is found
    vec![]
}

Explanation

The Brute Force Approach iteratively checks each pair of numbers in the array to see if they sum up to the target. This is done by using two nested loops: the outer loop iterates through each element, and the inner loop checks all subsequent elements to find a pair that adds up to the target.

The HashMap Approach is more efficient. It iterates through the array once, using a HashMap to store elements already traversed. For each element, we calculate its complement (target - current element) and check if this complement is already in the HashMap. If it is, we found a pair; if not, we add the current element to the HashMap. This approach significantly reduces the time complexity as it avoids the need for nested iteration.

Complexity Analysis

1. Brute Force Approach:
   • Time Complexity: O(n^2) where n is the number of elements in the array. This is because we need to check each pair of elements.
   • Space Complexity: O(1), as it only uses a few extra variables for iteration and no additional data structures.
2. HashMap Approach:
   • Time Complexity: O(n), as we traverse the list containing n elements only once. Each look up in the table costs only O(1) time.
   • Space Complexity: O(n), to store the elements and their indices in the HashMap.

Additional Information

When implementing solutions like the HashMap approach, it's crucial to consider possible edge cases, such as duplicate elements in the array, and ensure your implementation correctly handles these cases. We can dive deeper into some examples in other problems, for now it's good to just think about the potiental of these cases.

Follow-up Question

The follow up question challenged us to come up with a better solution Can you come up with an algorithm that is less than O(n2) time complexity? and we did so with the HashMap solution so let's dive down a little bit more as to why it's better and how it does it.

HashMap Approach Details

Initialize a HashMap: This map will store elements from the array as keys and their indices as values.

Iterate through the Array:

• For each element, calculate its complement by subtracting it from the target (i.e., complement = target - num).
• Check if the complement is already in the HashMap.
  • If it is, it means we have found a pair of numbers that add up to the target. Return their indices.
  • If not, add the current element and its index to the HashMap.

Return: If no pair is found by the end of the iteration, return an indication that no solution exists (e.g., an empty array).

Time Complexity:

• HashMap Lookups: The time complexity of looking up keys in a HashMap is ( O(1) ) on average.
• Single Iteration: The algorithm iterates through the array only once.
• Therefore, the overall time complexity is ( O(n) ), where ( n ) is the number of elements in the array.

Space Complexity:

• The space complexity is ( O(n) ), as in the worst case, we might need to add every element to the HashMap.

This HashMap approach is significantly more efficient than a brute-force method with nested loops, which has a time complexity of ( O(n^2) ). By utilizing a HashMap to store and quickly look up complements, we reduce the problem to a single pass through the array, achieving the desired time complexity of less than ( O(n^2) ).

Conclusion

In solving the "Two Sum" problem, we explored both a brute force and a HashMap approach, illustrating the trade-offs between time and space complexity. While the brute force method is straightforward, the HashMap approach offers a more efficient solution, highlighting the importance of understanding data structures and algorithms in problem-solving. Practicing such problems enhances not only coding skills but also analytical thinking, which is vital in tackling real-world challenges.