LeetCode WalkThru: 'TwoSum'

☁️☁️Hi everyone!☁️☁️

Today, I will be walking us through LeetCode's 'TwoSum' problem in JavaScript. This problem reflects the implementation of a beginner's understanding to Data Structures and Algorithms.

So, yes -- this is a simple coding challenge, but we will be approaching it in a few different ways.

Here is the link to the problem on LeetCode. Pull up the problem on your end if you want and let's get started!
☁️☁️☁️

Breaking Down the Instructions

These are the instructions provided in the left-hand menu 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.

Given this information, we can deduce a few things:

1. There are two (2) parameters: nums and target.
2. nums is an array of integers.
3. target is an integer.
4. Output = the indices of two numbers. (Example: [1, 2])
5. We cannot use the same integer at the same index twice to come to the target total.

Looking At Some Examples

Also, on the left-hand menu, LeetCode provides some examples. Let's look at one:

Input: nums = [3,2,5], target = 7
Output: [1,2]

Given our nums array and target integer, we can reconcile that the integers (the array items), at the indices of '1' and '2', together are equivalent to the target integer.

[1,2]

At the index of 1, in nums, we have the integer '2'.
At the index of 2, in nums, we have the integer of '5'.
Together, their sum (2+5) equates to 7.

If you are still wary, go ahead and look at the other examples LeetCode provides and maybe try to come up with your own example for good measure.

How Can We Approach This?

Like aforementioned, there are many ways to attempt to approach this problem. There are some obvious modus operandi and some not so obvious.

Approaching the obvious way is not wrong at all! In fact, it is good to consider all options and think aloud -- even if the obvious way is not the best or most efficient solution.

I don't know about you, but with arrays, I automatically consider iteration. Iteration (or colloquially, known as "looping through") is an extremely useful tool to break down the items of an array in order to access each item, all in an one-stop fashion.

We definitely want to iterate, because we need to see what is inside the array to come to conclusion of what two (2) array items equal our target.

First Approach

My brute-force-inspired solution involves a nested loop. A nested loop is a loop inside of another loop. While this is a totally solid way of coding, it is not necessarily readable nor efficient. Nested loops slow down the time it takes for the code to run and come to a solution.

** Think about it: everytime any item of the array is accessed, we have to go through the rest of the array to see if together, those two array items, equal the target. If the first array item of the array does not work, the computer moves to the second array item of the array and then goes through the array fully AGAIN... and so on until it finds the solution. This takes a lot of time! **

However, in its applicability, nested loops "make sense" while explaining verbally + in code.

So, here is what we can do:

1. Loop through the array "nums" and access each array item.
2. Loop through the array "nums", for a second time, and access each array item.
3. Compare the array items and see if any combination equate to the target.

Let's take a look at what a nested loop is doing:

const array = [a, b, c]

// Nested Looping

// a => b, c
// b => a, c
// c => a, b

While the first item is accessed, we are looping through the remainder of the array and accessing what is left.

Let's code this out to find the target sum:

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return [i, j]
            }
        }
    }
}

What are we doing here?

• The first "for" loop iterates through the array; accessing each item.
• The second "for" loop iterates through the remainder of the array. The second "for" loop is inside the first.
• I create an "if" statement: if any two (2) of the array items equal the value of the target integer then return the indices of the array items as an array.

Now, I know this may be confusing to wrap your head around, but please take a look at this resource if you need help.

You may have noticed I used the term "brute-force". "brute-force" just means, to me, coding a solution as you would explain it in your native language to someone who does not code. Yes, it works and yes, it may be elementary in ideological terms, but it is not the fastest or most efficient method. Considering this, let's move onto our second approach. Take a break here if you need.

Second Approach

Something I forgoed in the first attempt is "checking" for "edge-cases". Meaning checking to see if the given input allows a solution to be made. For this example, we are going to check the array to see if the array's length is '2'. If the length is equal to '2', then we are going to simply return the indices [0, 1].

For example:

const shortArray = [1, 7]
const exampleTarget = 8

We have to return the indices of the first two array items, because that is our only option. If we know the array is made up of two array items whose sum equates to the target integer, those indices contain the array items.

var twoSum = function(nums, target) {

  // if the array given only has two array items, return the 
  first and second index
  if (nums.length === 2) return [0,1]

}

You could also consider building out an error message if given an array that does not have the potential to equal the target integer.

Now that we have done some "checking", we can now consider how we can solve this problem without a nested loop.

We can create a hash! In JavaScript, a "hash" is a data structure that allows you to create a list of paired values. You may notice that this is similar to an object in JavaScript. Both have the ability to store key-value pair(s) in memory. And both transforms a key into an integer index.

A hash's syntax looks something like this:

let hash = {
    'a': 'apple',
    'b': 'banana',
    'c': 'cherry'
}

So, with this example, 'a' would have an index of 0; 'b' would have an index of 1; 'c' would have an index of 2.

Hashes are known not only for this, but also for it's efficient access quality. Knowing this, we can store the array items of the "nums" array into a hash; setting the array items as the keys and setting the indices as the values.

var twoSum = function(nums, target) {

  if (nums.length === 2) return [0,1]
  const length = nums.length
  // create an empty hash table to store the value of the array items as keys and the indices of those items as values. 
  let hash = {}
    // loop through the nums array
    for (let i = 0; i < nums.length; i++){
        // store the index of the array item as a value of the key in the hash
        hash[nums[i]] = i
    }
}

If we were to console.log(hash[nums[i]]), our console would show:

0
1
2

These are the indices of the array items of "nums". As you can see, we then set these indices to the variable "i". So, if we console.log(i), our console would also return:

0
1
2

Given 'nums = [1, 2, 4]' hash now looks like this:

let hash = {
  1: 0,
  2: 1, 
  4: 2
}

Now that we have established a hash, we can now loop through the nums array again to figure out the complement of each array item. Meaning complement + array item = target integer.

for (let i = 0; i < length; i++){
      // simple formula to figure out the complement of each number that would add to the target integer
      let complement = target - nums[i]

      // set variable "found" to the hashes complement
      let found = hash[complement]

      // as long as "found" is not undefined and does not equal the array item of itself, return the indices as an array
      if (found !== undefined && found != i){
        return [i, found]
      }
    }

Given 'nums = [1, 2, 4]' and 'target = 6', logging "complement" would return:

5 // 1 + 5 = 6
4 // 2 + 4 = 6
2 // 4 + 2 = 6

Well, what if there are not two array items that equal the target integer? What if 'nums = [1, 2, 70]'? None of those array items equate to the integer of 6. For these cases, we can return an error message of somesort at the end of our function.

Our final code should look something like this:

const exampleNums = [1, 2, 4]
const exampleTarget = 6


var twoSum = function(nums, target) {
    if (nums.length === 2) return [0,1]

    let hash = {}

    for (let i = 0; i < nums.length; i++){
        hash[nums[i]] = i
    }

    for (let i = 0; i < nums.length; i++){
      let complement = target - nums[i]
      let found = hash[complement]
      if (found !== undefined && found != i){
        return [i, found]
      }
    }
    return 'Sorry! Not valid.'
}

Testing Our Second Approach

Here are some tests you can run in your code + console:

Test #1

• const nums = [1, 2, 33]
• const target = 43

Test #2

• const nums = [3, 4]
• const target = 7

Test #3

• const nums = [17, 0, 1]
• const target = 17

Test #4

• const nums = [12, undefined, 1]
• const target = 14 ____________________________________________________________

Summary

This is a beginner's walk thru to data structures "array" and "hash". Remember there is not one singular way to code to a solution. There are brute force attempts like Approach #1. And there are more complex, and thus, more efficient ways like Approach #2. Code in a way that makes the most sense to you.

REMINDERS

1. Keep your code readable.
2. Keep your code scalable.
3. Consider edge cases (like nums only holding two array items).
4. Write down your input data types and output data types.
5. Write notes explaining what your code is doing, either above each line of code or at the bottom of the file.
6. Keep trying new methods!!

☁️☁️☁️☁️☁️☁️☁️☁️☁️☁️☁️☁️☁️

Thank you for reading and coding along with me. Please feel free to leave questions, comments or suggestions -- but always be kind and patient with everyone. We are all learning :)