The Relay Race —( TwoSum) Leetcode #1

In this problem, we are supposed to find two numbers from a given array that will add up to a specified target number.

For example, [1,2,3,4] is the array, nums and the target is 7. So, we have to return the index of the two numbers that add up to the target from nums. Which in this case is 3,4 and their indexes are 2,3 (as indexing begins at 0).

Say you are the team captain in a Relay Race Event. The rules are simple, you have to pick two athletes. The first person will run a specific distance with a flag. When that person reaches his said distance, then he will pass the flag to the other person, who will then continue and finish the race. You have to recruit the two people such that they cover exactly the distance required to finish the race. Lets take the example we had earlier.

The relay race is 700 m long, and you have a list of people who can run [100,200,300,400] m. You need to pick two such that they can run the exact 700m, no more no less, to be super efficient.

The Brute Force Way

The simplest idea that comes to our mind is to pick one person, say the 100m one, and then compare him with all the other athletes. 100+200,100+300…and so on. Then, if no pair is found, do the same with the other athletes. Check everyone with the 200m one and so on. So if there are n athletes, you will check nearly n times for each athlete. You check through all the athletes for the first attempt, the all for the second, till you have scanned all. In the worst case, it is an O(n²) time complexity, which is not very efficient.

The wise person

The way I solved this problem is by using Hashmaps. A hashmap can be compared to a person who can remember anything. So, now, I keep a person with me who can remember all the data I give him. We put all the athletes in a line, and then check them. We go to the first person. 100m. We keep a mental note that for that person to participate, we need a person with 600m. Then we move on to the next person. 200m. For him, we need 500m. Do you have a mental note of 500m? The person replies “No”. So we keep a note of 500m and move on. This way when we reach 300m, we keep a note that we need 400m. When we reach 400m, I ask him. Do we have a mental note of 400m? and he Replies, “yes”. This way, we can find the team in one iteration.

Hash Maps are simply functions, that accept a value and return something. You can check my article on hashmaps here: https://medium.com/@itsarnavsh/the-fastest-algorithm-hash-functions-dd9c27363652

These allow us to check for values and data from a list in O(1) time, which is crazy.

The Pseudo Code

• First of all, we make an empty Hashmap
• next, we iterate through the array
• For each element:
• We check if that element exists in the hashmap. If it does, we return its index and that number’s index that made that hashmap entry. Meaning the numbers at both index add up to the target value
• If that element does not exist in the hashmap yet, we will add target-number to the hashmap. Say we see 300 and the target is 700. So we will add 400 to the hashmap. If any val matches the hashmap, this means that we have the pair.

C++

This was my first code where I used both Vectors and Hashmaps in cpp. Heck, I didn’t even know HashMaps exist in cpp!

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        std::vector<int> myVector;
        unordered_map<int, int> hashmap;
        std::size_t vectorLength = nums.size();
        for(int i=0;i<vectorLength;i++)
        {
             auto it = hashmap.find(nums[i]);
             if (it != hashmap.end()) {
                // Key found
                myVector.push_back(it->second);
                myVector.push_back(i);
                return myVector;
            } else {
                // Key not found
                hashmap[target-nums[i]] = i;
            }
        }
        return myVector;
    }
};

Rust

Rust gives us the opportunity to save on memory as much as possible. The constrains said the will be under 10⁴, so I used an 16 bit integer instead of the default 32 bit wherever possible.

This, obviously introduced a lot of errors, as I am not that fluent with rust. It does not implicitly convert something like a 32 bit integer to a 16 bit one, which is like a huge shock coming form a language from JavaScript that allows to just multiply an object with a string with no consequences!

In this solution, I made a hashmap with two Data-Value pairs, a 32 bit integer and an unsigned 16 bit integer. The former to store the target-number value and the second to keep a track of its index.

Then we loop over it from 0 to nums.len(), exluding the latter.Then, we see if the current value exists in the HashMap, If it does not, then we simply move to the else statement, and add target-number and its index as a key-value pair to the HashMap. If it exists, we exit the code, making a vector with the current index, and the index in the hashmap.

use std::collections::HashMap;
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut index: HashMap<i32, u16> = HashMap::new();
        for i in 0..nums.len() {
            if let Some(&val) = index.get(&nums[i]) {
                return vec![val as i32, i as i32];
            } else {
                index.insert(target - nums[i], i as u16);
            }
        }
        vec![]
    }
}

JavaScript

You do not realize how error prone JS is if you have not coded in some “secure” languages! Now, Do not get me wrong. The best part about JS is that it does not give you stupid errors, the way rust does on adding a 32 bit with a 16 bit integer. The worst part about it is that it does not give stupid errors. When coding, I accidentaly wrote for(let i=0;i<nums.length;nums++). num is an array. And num++ returns NaN when you try that on the terminal. Why not give me an error, instead of just letting it be? This might be dumb on my side, ,but when on larger projects, this error is needed to secure safety of the project.

In this language, I simply made a object that I am calling hashmap, as you can make key-value pair using objects here, and followed the pseudocode.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) 
{
    let hashMap = {};
    for(let i=0;i<nums.length;i++)
    {
        if(nums[i] in hashMap)
            return [i,hashMap[nums[i]]];
        else
            hashMap[target-nums[i]] = i;
    }
};

If you want to add anything, or contribute a different method of solving, feel free to contact!