Improved the time complexity of a real project with hashing

I’m working for a software company and needed to improve the time complexity. I used “hashing strategy” and the time complexity decreased to O(N) from O(N²). The programming language is Go.

The original situation

There was nested for loops like below.

Array1 = {1,2,3,4,5}
Array2 = {1,2,3,4,5}
var counts int
for i := range Array1 {
  for j := range Array2 {
    if(Array[i].ID == Array[j].ID){
      counts++
    }
  }
}

This is O(N²). We needed to improve it.

Hashing

I utilized hash map for this problem instead of array like below.

    idCounts := make(map[int]int)
    for _, item := range Array1 {
        idCounts[item.ID]++
    }
    var counts int
    for _, item := range Array2 {
        if _, exists := idCounts[item.ID]; exists {
            counts++
        }
    }

This is O(N).

This is a famous trick, but I could make use of this strategy in actual project which in I earn salary. I think that it is a big step for my algorithm journey.

Feel free to reach out to me on LinkedIn, which you can find below. Looking forward to connecting!

https://www.linkedin.com/in/tomoharu-tsutsumi-56051a126/