1000X faster two sum leetcode solution

In this article you’re going to learn about the ways to solve two sum leetcode problem, In the article we are going to see multiple solutions for the two sum leetcode problem and as well, you can update the given code below as your requirement.

Two sum leetcode 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.

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]

I assume that you guys have an understanding now about what we have to do and if you’re still confused, I’m here let me explain it for you.

Assume that we have an unsorted array called arr = [2, 7, 11, 15] and a target value target=9, and if you sum index 0 value which is 2 and index 1 value which is 7 of arr you’ll get the the answer 9 which is exactly same as target value which we need, because we don’t need all possible pairs of two sum we can return back the indexes we got which is [0, 1], so this will be our answer as per given problem sequence of indexes can be change like from [0, 1] to [1, 0] it will be acceptable in two sum leetcode problem.

Runtime: 2 ms, faster than 99.24% of Go online submissions for Two Sum.
Memory Usage: 4.3 MB, less than 54.46% of Go online submissions for Two Sum.

Approaches to solve two sum leetcode problem:

Below is the all possible approaches to solve two sum leetcode problem in Go

• Brute force (Using two loops)
• Using Go map
• Using left and right pointer
• All Possible Pairs

These are the all possible implementations you will see in the action below, so without taking any extra time let’s see the implementations one by one.

1. Brute force or Naive approach

Brute force or naive approach is the simplest approach do get the results, what we have to do in this that we require two loops in this approach so we can iterate sequentially on each index one by one to check the sum is equal to the given target value is it matches then we’ll immediately return the indexes of both element, as I mentioned before that the order of indexes in return doesn’t matter in this.

Algorithm:

• Step 1: Create a function and the function will have two arguments: first unsorted array and second argument will be target value and the function will also return back the array/slice of indexes.
• Step 2: Create a loop i=0 and iterate over the unsorted array length
• Step 3: Create a second loop and start its iteration from j = i+1 to the length of the unsorted array.
• Step 4: Inside the second loop, Sum the values of arr[i] and arr[j] on each iteration and store it in a variable called sum = arr[i] + arr[j].
• Step 5: In the second loop after getting the sum of each index, write a if condition and check, sum == target.
• Step 6: If step 5 is true then return the indexes return []int{i, j}, you can change the i, j position.

Now we have an algorithm. Let’s follow the sequence to implement it.

Code:

Below is the code of the naive approach

package main
import (
    "fmt"
)
func TwoSumNaive(slice []int, target int) []int { // step 1
    for i := 0; i < len(slice)-1; i++ { // step 2
        for j := i + 1; j < len(slice); j++ { // step 3
            sum := slice[i] + slice[j] // step 4
            if sum == target { // step 5
                return []int{i, j} // step 6
            }
            continue
        }
    }
    return []int{}
}
func main() {
    slice := []int{2, 7, 2, 11, 15, 6}
    target := 9
    sum := TwoSumNaive(slice, target)
    fmt.Println(sum)
}

Explanation:

As you can see in the code we’ve an unsorted array/slice slice := []int{2, 7, 2, 11, 15, 6} and a target value target := 9, then we’re calling TwoSumNaive() function and passing both slice and target variable as argument to the function. Inside TwoSumNaive() first we started the loop over the unsorted array/slice from 0 to len(arr)-1 and after first loop we started another loop from i+1 till the last element of unsorted array, so the execution will happen like this, e.g. i=0 and j=0+1 which is 1 , and value of index 0 of slice is 2, and for index 1 it’s 7 then the sum value will be 2 + 7 = 9, sum = 9, next we’re comparing sum with target as we have sum 9 and target is also 9 then it’ll return back the indexes of i and j so our answer will be [0, 1] or [1, 0].

Below is the leetcode and local system execution results:

$ go run .\main.go
[0 1]

Leetcode result:

Runtime: 46 ms, faster than 22.60% of Go online submissions for Two Sum.
Memory Usage: 3.6 MB, less than 74.60% of Go online submissions for Two Sum.

Leetcode results do not look good for this as it’s taking more time then I have mentioned above in the article.

2. Using Hashmap

Naïve approach was the most simple approach a programmer can think, but for the big length array the naïve approach doesn’t work much faster as we need, as you can for this array {2, 7, 2, 11, 15, 6} it took almost 46 ms which isn’t so much fast so, for making it faster we first need to eliminate our second loop, and we also need new data structure HashMap, In Go it’s a Map so what we will do is that instead of adding our values we’ll check that diff = target – arr[index], e.g. diff = 9 – 2 and diff will be 7 as we have remaining value we’ll look into our map for the 7 and if it exists in our map then get the value and return it indexes back.

Algorithm

• Step 1: Create a function and the function will have two arguments: first unsorted array and second argument will be target value and the function will also return back the array/slice of indexes.
• Step 2: Declare a variable of type map so we can look up for remaining value.
• Step 3: Create a loop and iterate over the unsorted array/slice.
• Step 4. Subtract target value from array/slice for the index e.g. diff = target – slice[idx].
• Step 5: Pass the difference value as the key to the map, to check if the key exists in our hashmap.
• Step 6: If key exists in our hashmap extract value of the key and return back the current index and value.
• Step 7: If key doesn’t exist then add value of current index and current index as key and value into our HashMap.

We have our algorithm let’s implement it and see the results of it, Below is the implementation of the algorithm:

Code

package main

import (
    "fmt"
)

// using HashMap
func TwoSumHashmap(slice []int, target int) []int {
    hashMap := map[int]int{}
    for idx := 0; idx < len(slice); idx++ {
        pmatch := target - slice[idx]
        if v, exists := hashMap[pmatch]; exists {
            return []int{idx, v}
        }
        hashMap[slice[idx]] = idx
    }
    return nil
}

func main() {
    slice := []int{2, 7, 2, 11, 15, 6}
    target := 9
    sum := TwoSumHashmap(slice, target)
    fmt.Println(sum)
}

Explanation:

We are using map in this example of code and you can see that we have a function called TwoSumHashmap and it has two arguments: first unsorted array and second is our target value and it’s also returning the []int.

Inside our function we have declared a map called hashMap as we all know that Go’s map holds the key and value pair information so it’s better for us to use this instead of another loop for iterating over all values as we did in approach 1.

After declaring a map we are running our loop over the given slice/array till the last element of the array. Inside the loop we’re subtracting the target – slice[idx] on each iteration, and in the next step we’re directly passing the difference as the key to our map. In Go you can check like this for if the passed key exists or not in a map because the second return value return a Boolean value which will be true if the provided key exists in key if not then it’ll return a false value, So if our key exists in the map then we will directly return back the current index of array and the value we got from the key which is also a index, and if it’s false then we’ll go to next step in which we’ll add current index arrays/slice value as key and the current index as it’s value, so it’ll work until it founds the key and will return the indexes back and if it doesn’t found anything the function will return back the nil.

Below is the output of the code for Leetcode and local system:

$ go run .\main.go
[1 0]

Leetcode result

Runtime: 2 ms, faster than 99.24% of Go online submissions for Two Sum.
Memory Usage: 4.3 MB, less than 54.46% of Go online submissions for Two Sum.

HashMap is way better in comparison to the brute force approach. Hashmap is almost 2300% faster than brute force.

Below is the one more approach to get the single pair of two sum let’s see it

3. Left and Right Pointer

Disclaimer: This approach might not work in the leetcode because this approach only works for sorted arrays and via sorting indexes might change and so your answer.

In this approach we’ll first sort our array and then we’ll create a for loop (infinite) and add some conditions and based on that condition our left and right pointers will move forward and backwards. Lets see the algorithm for this:

Algorithm

• Step 1: Create a function and the function will have two arguments: first unsorted array and second argument will be target value and the function will also return back the array/slice of indexes.
• Step 2: Declare two variables left pointer and right pointer and initialize their values left = 0, right=len(arr).
• Step 3: Sort your array first, In go you can use the Sort package for this Sort.Ints().
• Step 4. Create a for ever loop for start != end.
• Step 5: Sum the left and right array index values.
• Step 6: Add condition if sum > target: if true then right = right – 1 move pointer backwards.
• Step 7: else if sum < target: if true then left = left + 1, move pointer forward.
• Step 8: else: return []int{left, right}.

Code

package main

import (
    "fmt"
    "sort"
)

func TwoSumSortedArray(slice []int, target int) []int {
    if len(slice) < 2 {
        fmt.Println("can't process")
        return nil
    }
    sort.Ints(slice)
    start := 0
    end := len(slice) - 1
    fmt.Println("After Sorting:", slice)

    for start != end {
        sum := slice[start] + slice[end]
        if sum > target {
            end = end - 1
        } else if sum < target {
            start = start + 1
        } else {
            return []int{start, end}
        }
    }
    return nil
}

func main() {
    slice := []int{2, 7, 2, 11, 15, 6}
    target := 9
    fmt.Println("Before Sorting:", slice)
    sum := TwoSumSortedArray(slice, target)
    fmt.Println(sum)
}

Explanation

As you can see in the TwoSumSortedArray function first we have added a condition to check if array/slice have enough length of data or not because we don’t want our program to panic :), and then we sorted our array/slice now the order has changed of the array so results now won’t be like we had in previous examples. Next we declared our pointers and assigned the values as well.

We started the loop and added a condition as well so whenever our pointer values are equal then the loop will end.

In loop we are adding left and right indexes values and passing it to the condition we have and moving our pointers to left and right based on the sum and target value if target value in greater than the joint value of left and right pointer array index values, then we’ll move our end pointer one step back and for elseif condition we are moving our start(left) pointer forward and if both condition not satisfied then we’ll return the start(left) and end(right) values.

$ go run .\main.go
Before Sorting: [2 7 2 11 15 6]
After Sorting: [2 2 6 7 11 15]
[0 3]

This article is originally posted on programmingeeksclub.com

My Personal Blogging Website : Programming Geeks Club
My Facebook Page : Programming Geeks Club
My Telegram Channel : Programming Geeks Club
My Twitter Account : Kuldeep Singh
My Youtube Channel: Programming Geeks Club

Two sum leetcode 1000X Faster - Programming Geeks Club

In this article you're going to learn about the ways to how solve two sum leetcode problem, we are going to see multiple solutions

programmingeeksclub.com