Want to Contribute to us or want to have 15k+ Audience read your Article ? Or Just want to make a strong Backlink?

1000X faster two sum leetcode solution

On this article you’re going to be taught in regards to the methods to resolve two sum leetcode downside, Within the article we’re going to see a number of options for the 2 sum leetcode downside and as effectively, you’ll be able to replace the given code beneath as your requirement.



Two sum leetcode downside assertion:

Given an array of integers nums and an integer goal, return indices of the 2 numbers such that they add as much as goal.

It’s possible you’ll assume that every enter would have precisely one resolution, and you could not use the identical component twice.

You possibly can return the reply in any order.

Instance 1:

Enter: nums = [2,7,11,15], goal = 9
Output: [0,1]
Rationalization: As a result of nums[0] + nums[1] == 9, we return [0, 1].
Enter fullscreen mode

Exit fullscreen mode

Instance 2:

Enter: nums = [3,2,4], goal = 6
Output: [1,2]
Enter fullscreen mode

Exit fullscreen mode

Instance 3:

Enter: nums = [3,3], goal = 6
Output: [0,1]
Enter fullscreen mode

Exit fullscreen mode

I assume that you just guys have an understanding now about what we now have to do and should you’re nonetheless confused, I’m right here let me clarify it for you.

Assume that we now have an unsorted array referred to as arr = [2, 7, 11, 15] and a goal worth goal=9, and should you sum index 0 worth which is 2 and index 1 worth which is 7 of arr you’ll get the the reply 9 which is precisely identical as goal worth which we want, as a result of we don’t want all attainable pairs of two sum we will return again the indexes we obtained which is [0, 1], so this can be our reply as per given downside sequence of indexes could be change like from [0, 1] to [1, 0] it will likely be acceptable in two sum leetcode downside.

Runtime: 2 ms, sooner than 99.24% of Go on-line submissions for Two Sum.
Reminiscence Utilization: 4.3 MB, much less than 54.46% of Go on-line submissions for Two Sum.
Enter fullscreen mode

Exit fullscreen mode



Approaches to resolve two sum leetcode downside:

Beneath is the all attainable approaches to resolve two sum leetcode downside in Go

  • Brute power (Utilizing two loops)
  • Utilizing Go map
  • Utilizing left and proper pointer
  • All Attainable Pairs

These are the all attainable implementations you will notice within the motion beneath, so with out taking any additional time let’s see the implementations one after the other.



1. Brute power or Naive strategy

Brute power or naive strategy is the best strategy do get the outcomes, what we now have to do on this that we require two loops on this strategy so we will iterate sequentially on every index one after the other to examine the sum is the same as the given goal worth is it matches then we’ll instantly return the indexes of each component, as I discussed earlier than that the order of indexes in return doesn’t matter on this.



Algorithm:

  • Step 1: Create a perform and the perform could have two arguments: first unsorted array and second argument can be goal worth and the perform can even return again the array/slice of indexes.
  • Step 2: Create a loop i=0 and iterate over the unsorted array size
  • Step 3: Create a second loop and begin its iteration from j = i+1 to the size of the unsorted array.
  • Step 4: Contained in the second loop, Sum the values of arr[i] and arr[j] on every iteration and retailer it in a variable referred to as sum = arr[i] + arr[j].
  • Step 5: Within the second loop after getting the sum of every index, write a if situation and examine, sum == goal.
  • Step 6: If step 5 is true then return the indexes return []int{i, j}, you’ll be able to change the i, j place.

Now we now have an algorithm. Let’s comply with the sequence to implement it.



Code:

Beneath is the code of the naive strategy

bundle primary
import (
    "fmt"
)
func TwoSumNaive(slice []int, goal 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 == goal { // step 5
                return []int{i, j} // step 6
            }
            proceed
        }
    }
    return []int{}
}
func primary() {
    slice := []int{2, 7, 2, 11, 15, 6}
    goal := 9
    sum := TwoSumNaive(slice, goal)
    fmt.Println(sum)
}
Enter fullscreen mode

Exit fullscreen mode



Rationalization:

As you’ll be able to see within the code we’ve an unsorted array/slice slice := []int{2, 7, 2, 11, 15, 6} and a goal worth goal := 9, then we’re calling TwoSumNaive() perform and passing each slice and goal variable as argument to the perform. Inside TwoSumNaive() first we began the loop over the unsorted array/slice from 0 to len(arr)-1 and after first loop we began one other loop from i+1 until the final component of unsorted array, so the execution will occur like this, e.g. i=0 and j=0+1 which is 1 , and worth of index 0 of slice is 2, and for index 1 it’s 7 then the sum worth can be 2 + 7 = 9, sum = 9, subsequent we’re evaluating sum with goal as we now have sum 9 and goal can be 9 then it’ll return again the indexes of i and j so our reply can be [0, 1] or [1, 0].

Beneath is the leetcode and native system execution outcomes:

$ go run .primary.go
[0 1]
Enter fullscreen mode

Exit fullscreen mode

Leetcode end result:

Runtime: 46 ms, sooner than 22.60% of Go on-line submissions for Two Sum.
Reminiscence Utilization: 3.6 MB, much less than 74.60% of Go on-line submissions for Two Sum.
Enter fullscreen mode

Exit fullscreen mode

Leetcode outcomes don’t look good for this because it’s taking extra time then I’ve talked about above within the article.



2. Utilizing Hashmap

Naïve strategy was the most straightforward strategy a programmer can assume, however for the massive size array the naïve strategy doesn’t work a lot sooner as we want, as you’ll be able to for this array {2, 7, 2, 11, 15, 6} it took virtually 46 ms which isn’t a lot quick so, for making it sooner we first must remove our second loop, and we additionally want new knowledge construction HashMap, In Go it’s a Map so what we are going to do is that as an alternative of including our values we’ll examine that diff = goal – arr[index], e.g. diff = 9 – 2 and diff can be 7 as we now have remaining worth we’ll look into our map for the 7 and if it exists in our map then get the worth and return it indexes again.



Algorithm

  • Step 1: Create a perform and the perform could have two arguments: first unsorted array and second argument can be goal worth and the perform can even return again the array/slice of indexes.
  • Step 2: Declare a variable of kind map so we will search for for remaining worth.
  • Step 3: Create a loop and iterate over the unsorted array/slice.
  • Step 4. Subtract goal worth from array/slice for the index e.g. diff = goal – slice[idx].
  • Step 5: Cross the distinction worth as the important thing to the map, to examine if the important thing exists in our hashmap.
  • Step 6: If key exists in our hashmap extract worth of the important thing and return again the present index and worth.
  • Step 7: If key doesn’t exist then add worth of present index and present index as key and worth into our HashMap.

We now have our algorithm let’s implement it and see the outcomes of it, Beneath is the implementation of the algorithm:



Code

bundle primary

import (
    "fmt"
)

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

func primary() {
    slice := []int{2, 7, 2, 11, 15, 6}
    goal := 9
    sum := TwoSumHashmap(slice, goal)
    fmt.Println(sum)
}
Enter fullscreen mode

Exit fullscreen mode



Rationalization:

We’re utilizing map on this instance of code and you may see that we now have a perform referred to as TwoSumHashmap and it has two arguments: first unsorted array and second is our goal worth and it’s additionally returning the []int.

Inside our perform we now have declared a map referred to as hashMap as everyone knows that Go’s map holds the important thing and worth pair info so it’s higher for us to make use of this as an alternative of one other loop for iterating over all values as we did in strategy 1.

After declaring a map we’re operating our loop over the given slice/array until the final component of the array. Contained in the loop we’re subtracting the goal – slice[idx] on every iteration, and within the subsequent step we’re instantly passing the distinction as the important thing to our map. In Go you’ll be able to examine like this for if the handed key exists or not in a map as a result of the second return worth return a Boolean worth which can be true if the offered key exists in key if not then it’ll return a false worth, So if our key exists within the map then we are going to instantly return again the present index of array and the worth we obtained from the important thing which can be a index, and if it’s false then we’ll go to subsequent step during which we’ll add present index arrays/slice worth as key and the present index because it’s worth, so it’ll work till it founds the important thing and can return the indexes again and if it doesn’t discovered something the perform will return again the nil.

Beneath is the output of the code for Leetcode and native system:

$ go run .primary.go
[1 0]
Enter fullscreen mode

Exit fullscreen mode

Leetcode end result

Runtime: 2 ms, sooner than 99.24% of Go on-line submissions for Two Sum.
Reminiscence Utilization: 4.3 MB, much less than 54.46% of Go on-line submissions for Two Sum.
Enter fullscreen mode

Exit fullscreen mode

HashMap is method higher compared to the brute power strategy. Hashmap is nearly 2300% sooner than brute power.

Beneath is the another strategy to get the only pair of two sum let’s see it



3. Left and Proper Pointer

Disclaimer: This strategy won’t work within the leetcode as a result of this strategy solely works for sorted arrays and through sorting indexes may change and so your reply.

On this strategy we’ll first type our array after which we’ll create a for loop (infinite) and add some situations and based mostly on that situation our left and proper pointers will transfer ahead and backwards. Lets see the algorithm for this:



Algorithm

  • Step 1: Create a perform and the perform could have two arguments: first unsorted array and second argument can be goal worth and the perform can even return again the array/slice of indexes.
  • Step 2: Declare two variables left pointer and proper pointer and initialize their values left = 0, proper=len(arr).
  • Step 3: Kind your array first, In go you need to use the Kind bundle for this Kind.Ints().
  • Step 4. Create a for ever loop for begin != finish.
  • Step 5: Sum the left and proper array index values.
  • Step 6: Add situation if sum > goal: if true then proper = proper – 1 transfer pointer backwards.
  • Step 7: else if sum < goal: if true then left = left + 1, transfer pointer ahead.
  • Step 8: else: return []int{left, proper}.



Code

bundle primary

import (
    "fmt"
    "type"
)

func TwoSumSortedArray(slice []int, goal int) []int {
    if len(slice) < 2 {
        fmt.Println("cannot course of")
        return nil
    }
    type.Ints(slice)
    begin := 0
    finish := len(slice) - 1
    fmt.Println("After Sorting:", slice)

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

func primary() {
    slice := []int{2, 7, 2, 11, 15, 6}
    goal := 9
    fmt.Println("Earlier than Sorting:", slice)
    sum := TwoSumSortedArray(slice, goal)
    fmt.Println(sum)
}

Enter fullscreen mode

Exit fullscreen mode



Rationalization

As you’ll be able to see within the TwoSumSortedArray perform first we now have added a situation to examine if array/slice have sufficient size of knowledge or not as a result of we don’t need our program to panic :), after which we sorted our array/slice now the order has modified of the array so outcomes now gained’t be like we had in earlier examples. Subsequent we declared our pointers and assigned the values as effectively.

We began the loop and added a situation as effectively so every time our pointer values are equal then the loop will finish.

In loop we’re including left and proper indexes values and passing it to the situation we now have and transferring our tips to left and proper based mostly on the sum and goal worth if goal worth in better than the joint worth of left and proper pointer array index values, then we’ll transfer our finish pointer one step again and for elseif situation we’re transferring our begin(left) pointer ahead and if each situation not glad then we’ll return the beginning(left) and finish(proper) values.

$ go run .primary.go
Earlier than Sorting: [2 7 2 11 15 6]
After Sorting: [2 2 6 7 11 15]
[0 3]
Enter fullscreen mode

Exit fullscreen mode

This text is initially posted on programmingeeksclub.com

My Private Running a blog Web site : Programming Geeks Club
My Fb Web page : Programming Geeks Club
My Telegram Channel : Programming Geeks Club
My Twitter Account : Kuldeep Singh
My Youtube Channel: Programming Geeks Club

On this article you are going to be taught in regards to the methods to how resolve two sum leetcode downside, we’re going to see a number of options

favicon
programmingeeksclub.com



Add a Comment

Your email address will not be published. Required fields are marked *

Want to Contribute to us or want to have 15k+ Audience read your Article ? Or Just want to make a strong Backlink?