Andrew Williams

Posted on Feb 3, 2021

Algorithm Practice: Two Sum

#algorithms #javascript

Why Algorithms?

By definition, in software development, Algorithms are computer procedures designed to accomplish a specific task. Each algorithm consists of a number of steps the computer takes in order to produce a result. The ultimate goal in using algorithms is to find a result or solution in the most efficient way possible.

Creating and studying algorithms is an essential part of being a software engineer. Sure, you may not run into a situation where you have to fulfill the requirements present in many of your study questions, but the techniques you learn will prove beneficial when performing technical analysis. You may find part of an algorithm you studied makes your application run more efficiently or returns the results your end-user needs.

Regardless of how you use them, algorithms are a great problem-solving tool, and for that reason, I have made it a personal goal to practice algorithm development. For however long it takes, I will be working my way through a series of coding challenges, each designed to test my knowledge (or lack of knowledge) on certain software concepts. I will be using this blog as an outlet to discuss what went well and what didn't go so well with each challenge. If you yourself are a new software developer or are exploring the possibility of becoming one, I hope these posts can be encouraging and motivating for you in your own personal journey!

The Problem: Two Sum

The prompt for this challenge is pretty straightforward: write a function, taking in a non-empty array of integers and a target value, that returns a new array with two values from our input array whose sum equals the target value. Below is an example of what we would expect our function to do:

Array = [8, 1, 7, 5, -9, -11, 3]
Target Value = 10

Output = [7, 3] or [3, 7]

If no two numbers in the array sum up to the target value, we simply return an empty array. It should also be noted that the function cannot add an integer to itself (ex. 5 + 5) and that it should be assumed that there is at most one pair of numbers summing up to the target value.

My Initial Solution

While this problem is classified as "easy" on the platform I'm using, I did find it challenging at first since I had little experience with these kinds of questions. After about 30-35 minutes I finally came up with a solution that cleared all the tests:

function twoSum(array, targetSum) {
    let finalArray = []
    let newArray = array

    for(i=0; i < array.length; i++){
        let targetValue = array[i]
        newArray.splice(i,1)

        newArray.map(value => {
            if (targetValue + value === targetSum){
                finalArray.push(targetValue)
                finalArray.push(value)
            }
        })

        if (finalArray.length === 0){
            newArray.splice(i, 0, targetValue)
        } else {
            return finalArray;
        }
    }
    return finalArray
}

Breaking down the code, I first defined two arrays, one set to an empty array and another set to the array that was passed into the function. I then initiate a for loop that is set to run the length of the array. Within the for loop, I define another variable equal to a value in the array where i is the index number. This variable's value will change each time the loop increments. I then took my newArray and spliced out the value that the index of i.

After removing this value, I then map through newArray to check and see if any other value added with the targetValue equals the targetSum. If these two values return the correct sum, I then push each value into the finalArray.

Once the map is complete, I run another conditional that checks the length of our finalArray. If the length is equal to zero, then the target value is inserted back into newArray at the index value of i, continuing the loop's run. If the length is greater than zero, it indicates there are values present and the program returns finalArray. The last return line after this conditional exists to return the empty array if the loop has cycled all the way through and failed to have found a pair of integers.

Refining My Approach

While this algorithm does pass the challenge presented in the prompt, it is a mess on more levels than one. In fact, I was so happy I simply cleared the tests I submitted this problem without taking time to refactor my work. After a few days I finally decided to take a look, and oh boy was it rough!

For starters, I defined a couple of redundant variables, the most obvious example being newArray at the very beginning. The code becomes cluttered with a large number of variables and it becomes increasingly difficult for someone reading the code to figure out what the function is actually doing. For refactoring purposes, I knew I needed to cut out the redundancy.

I had the right approach incorporating a for loop, but somehow made the puzzling decision to incorporate map. Sure, map can be used to iterate over an array and examine each value, but the purpose is to return a new array. Instead of map, I should have used a second for loop, which would have accomplished same goal of iteration without the need to return a value.

Finally, I made the task of returning a final array more difficult than it needed to be. Instead of a complicated exercise in creating an empty array, pushing the correct values into that array, and checking to see if there are any values in the array, I could have just returned an array with the values inside:

return [value1, value2]

I would have to set my code up differently, but this is definitely the preferred way of doing things.

Coding an Alternative Solution

After reviewing these issues, researching big-O notation, and getting advice from some other developers, I submitted a second solution:

function twoSum(array, targetSum) {
   array.sort((a,b) => a - b);
   let leftIndex = 0
   let rightIndex = array.length-1

   while(leftIndex < rightIndex){
    const currentSum = array[leftIndex] + array[rightIndex]

    if(currentSum === targetSum){
       return [array[leftIndex], array[rightIndex]]
    } else if (currentSum < targetSum){
            leftIndex++
    } else if (currentSum > targetSum){
            rightIndex--
    }
   }
   return [];
}

In this version, the first thing I did was sort the integers in the array from smallest to largest. I then created two variables to represent the first and last index of the array. Then I initiated a while loop, which runs continuously until either the leftIndex is greater than or equal to the rightIndex or a return statement is executed.

Within the loop, I created another variable, currentSum, responsible for holding the sum of the left index value and the right index value. Armed with this variable, I created a conditional that checks to see if this value is equal to the targetSum. If it is, the function returns an array with both index values. The other statements check to see if the currentSum is either greater than or less than the targetSum, adjusting the value of either index in order to change the currentSum. If every value in the array has been evaluated and no pairs have produced the targetSum, the algorithm returns an empty array.

This approach works thanks to numeric ordering and the use of left and right "pointers". Let's use the array I defined earlier and pass it into this algorithm. Below would be our initial values before entering the loop:

Target Value = 10
Sorted Array = [-11, -9, 1, 3, 5, 7, 8]
leftIndex = 0
rightIndex = 6

Once we entered the loop, we sum -11 and 8, which results in -3. Since -3 is less than 10, the first else if statement is executed and leftIndex value is increased by one, which is the index for -9 in the array. Over time the function adjusts the position of each index accordingly until a pair is summed equal to the targetSum. In the case of the example above, this would occur when the leftIndex equals 3 and the rightIndex equals 5.

Conclusion

It feels so good to go back, even with the easier problems, and nail down how and why an algorithm is working. Being able to learn from your mistakes and make your code run more efficiently gives you that confidence boost to tackle another coding challenge. Hopefully, when my future self looks back, I can recognize these small accomplishments as stepping stones of knowledge that helped make me a more well-rounded developer!

Top comments (10)

Harsh Rathod • Feb 7 '21 • Edited

The first thing that came to my mind after reading the question was brute force. After that, the mapping solution took me about 1 hour to think and code because I never used it before. Here is my idiomatic Golang solution:

package main

import "fmt"

// Brute force
// Complexity: O(n^2)
func twoSumBruteForce(a *[]int, x int) (r []int) {
    l := len(*a) - 1
    for i := 0; i < l; i++ {
        for j := i + 1; j <= l; j++ {
            if (*a)[i] + (*a)[j] == x {
                r = append(r, (*a)[i], (*a)[j])
                return
            }
        }
    }
    return
}

// Mapping
// Time Ccomplexity: O(n)
// Space Complexity: O(n)
func twoSumMapping(a *[]int, x int) (r []int) {
    hash := make(map[int]int, len(*a))
    for i := range *a {
        if v, ok := hash[(*a)[i]]; ok {
            r = append(r, (*a)[i], v)
            return
        } else {
            hash[x - (*a)[i]] = (*a)[i]
        }
    }
    return
}

func main() {
    // Test 1
    arr := []int{8, 1, 7, 5, -9, -11, 3}
    ans := twoSumBruteForce(&arr, 10)
    fmt.Println(ans)
    // Test 2
    ans = twoSumMapping(&arr, 10)
    fmt.Println(ans)
}

NoMad42 • Feb 14 '21

Same map two sum alternate from "Born to die" php }:->

<?php declare(strict_types = 1);

function twoSumMap(array $arr, int $target): array {
    $hash = [];

    foreach ($arr as $val) {
        if ($hash[$val] ?? false) {
            return [$val, $hash[$val]];
        }

        $hash[$target - $val] = $val;
    }

    return [];
}

function main(): void {
    $arr = [8, 1, 7, 5, -9, -11, 3];

    var_dump(twoSumMap($arr, 10));
}

main();

3v4l.org/253rp

Shwetabh Shekhar • Feb 3 '21

Great job.
You can do it in O(n) if you use a dictionary(but space complexity would be compromised).

Create a dictionary of all elements of the array.
Iterate through the array. From the target-value subtract the current array element and look for it in the map.
If found the current value and the found element in the map will be the target sum pair.

Abdessamad MOUHASSINE • Feb 13 '21 • Edited

typescript solution

function twosum (ints: number[], target: number) {
  for (let i = 0; i < ints.length - 1; i++) {
    for (let j = i + 1; j < ints.length; j++) {
      if (ints[i] + ints[j] == target) {
        return [ints[i], ints[j]] 
      }
    } 
  }

  return [] // no match
}

ѕυηιℓ gαяg • Feb 4 '21

Here is a solution from My side..
for every element you traverse u put totalReq - current element into a Map or dictionary, for next time u will before putting this number search for this new element that u got in next iteration in Map or dictionary, if u found it then u got ur element
totalReq = 10
dictionary ;
temp;
for (elem : arr) {
temp = totalReq - elem;
if (dictionary has temp) {
print "you found req elem"
// also remove the elem or may be not if problem statement requires
} else {
put element in dic;
}
}