Two Sum, solving a programming challenge

Solving programming challenges is something I'm passionate about: on one hand, it requires understanding the basics of programming, having a deep knowledge of how computers work, knowing about complexity orders and the "Big O" notation, and on the other hand, having some ingenuity and creativity.

There are many platforms where you can find all kinds of challenges like this to learn how to solve them. Personally, I've always liked Project Euler. The other day, I stumbled upon LeetCode and decided to start solving challenges sporadically for fun. It's something I've always enjoyed because you learn a lot by solving these problems, and as I said, it's fun for me.

The first of these challenges is titled Two Sum, and it's the one we're going to solve today. These types of problems are often given in technical interviews to see how a person thinks, how they solve a problem, and to test their knowledge. This is a topic we can debate in another video/post.

What I want to highlight is that you can use any language to solve it, whichever you prefer. Here, I recommend you use it to improve in a language you feel comfortable with or use it to challenge yourself in a language you're learning and want to improve in.

I recommend you stop reading if you want to try solving it yourself first and then come back here.

Big O Notation. Complexity Orders.

Complexity orders are a tool that allows us to classify different algorithms without considering the specific time, but rather how they behave (whether in time or memory) depending on the size of the input.

For example, O(1) means that time or memory is constant, regardless of the input size. O(n) is linear, O(n^2) is quadratic, etc.

As I write this post, I realize that this is a very interesting topic, and I'll add it to my list to discuss in depth in another post.

"Two Sum" Problem

Given an array of integers and a target integer, your mission is to find two numbers in the array that add up to the target. Specifically, you need to return an array with the indices of those numbers.

For example, with a target of 6 and the array [3, 1, 2, 7, 6, 4, 8], the solution would be to find the indices of the numbers 2 and 4, which would be [2, 5].

First Solution: Brute Force

In general, you should always try to solve any problem in the simplest way possible. Why? Because when facing a problem, you should avoid analysis paralysis and have a solution that allows you to move towards a result. A common mistake is to start by trying to optimize a problem since you don't know where the bottleneck in your algorithm might be. That said, it's important to understand the limitations of your solution. Let's get started.

The first idea is to iterate through the array with a double for loop so that for each number (first loop), you go through the array looking for another number (second loop) whose sum is the target number.

For example, an initial solution implemented in Rust could be the following:

impl Solution { pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> { 
    for i in 0..nums.len() { 
        for j in (i+1)..nums.len() { 
            if nums[i] + nums[j] == target { 
                return vec![i as i32, j as i32]; 
            } 
        }
    } 
    return vec![]; 
}

This solution has a complexity order of O(n^2) since the complexity is exponential based on the input size due to the double for loop. Having to iterate and compare each element with all other elements in the array means it requires more time as the input size increases.

Second Solution: Using a Hash Table

The previous code can be improved in the following way. To avoid having a loop inside another loop, which results in a complexity of O(n^2), we could achieve a complexity of O(n) if we manage not to nest the for loops.

I spent some time thinking about this, and the idea is as follows: when you iterate through the example array, if you have a 3, you know you need to find the complementary number, in this case, 9 (target) - 3 (n) = 6 (complementary). Therefore, we can create a HashMap data structure to store the differences, and then on another pass, we can find if any element of the array belongs to this set in constant time O(1) (this is a property of some hash tables).

We could solve it with the following code:

use std::collections::HashMap;

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut dif = HashMap::<i32, i32>::new();
    for i in 0..nums.len() {
        dif.insert(target - nums[i], i as i32);
    }
    for i in 0..nums.len() {
        if let Some(&j) = dif.get(&nums[i]) {
            if i as i32 != j {
                return vec![i as i32,j as i32];
            }
        }
    }

    return vec![];
}

The story doesn't end here, as we can optimize it to calculate it in a single pass, avoiding having to go through the initial array twice.

use std::collections::HashMap;

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut dif = HashMap::<i32, i32>::new();

    for i in 0..nums.len() {
        if let Some(&j) = dif.get(&nums[i]) {
            if i as i32 != j {
                return vec![i as i32,j as i32];
            }
        }

        dif.insert(target - nums[i], i as i32);
    }

    return vec![];
}

I want to highlight that this solution is O(n), but it will require more time because it needs to allocate memory for the hash table data, and although it's more efficient for large data sets, the first solution might be faster for smaller sets. Similarly, for example, solutions 2 and 3 are both O(n), but the second will be practically faster in most cases.

I'll leave this for another post since, as I mentioned, complexity orders are a very interesting and deep topic, and they also allow us to study the timing of two algorithms using statistical tests.