LeetCode Blind 1/75: Two Sum

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.
Link to problem

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]

Solutions

Approach 1: Brute Force

We essentially check every combination of two values and see if they sum up to our target.
Not optimal, but the first approach anyone would think of.

For example:

Array: [1,2,3,5]
Target: 7

Iteration 1:
Combination of 1 with [2, 3, 5] is checked. Target sum is not found.

Iteration 2:
Combination of 2 with [3, 5] is checked. [2, 5] results in target sum.

Implementation in Rust

fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
    let mut results: Vec<i32> = Vec::new();
    for i in 0..numbers.len() {
        for j in (i+1)..numbers.len() {
            if numbers[i] + numbers[j] == target {
                results.push(i as i32);
                results.push(j as i32);
            }
        }
    }
    results
}

Time complexity: $O(n^2)$
Runtime on LeetCode: $52$ms

Approach 2: HashMap

While traversing through our array, we check if $y = targetSum - x$ exists in our HashMap where $x$ is the current value, if it doesn’t exist - we add it, but if it does then we have found a solution.

Pseudocode

create a new HashMap

iterate over the array
    if (target - current_element) exists in HashMap
        return [the index from HashMap, current_element's index]
    else
        insert current_element and index in HashMap

Implementation in Rust

fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
    let mut results = HashMap::new();

    for i in 0..numbers.len() {
        match results.get(&(&target - &numbers[i])) {
            Some(&index) => return vec![index, i as i32],
            None => results.insert(numbers[i], i as i32),
        };
    }
    vec![]
}

Time Complexity: $O(n)$
Space complexity: $O(n)$
Runtime on LeetCode: $5$ms

Note: There exists a very similar approach which requires you to insert values into hash table first and then check if value exists.
This is known as two-pass HashMap and its time complexity would be $O(2n)$, since we are iterating two times, one during insertion and another while checking.
This is essentially $O(n)$.