[BOJ-3273] Let's Solve the Two Sum Problem in Two Ways (Hash, Two Pointers) With Go

Problem

Link to BOJ-3273

n positive integers a1, a2, ..., an are given, and they are distinct. The value of ai is a natural number, satisfying 1 ≤ ai ≤ 1000000.

Given a natural number x, write a program to find the number of pairs (ai, aj) such that ai + aj = x (1 ≤ i < j ≤ n).

The problem asks whether there exists a pair in the array that sums to the specified number x.

For convenience, I will refer to x as target below.

1. Solving with a Double Loop

Upon initially receiving the problem, a simple thought was to loop through the array twice to search for the pairs.

The core logic can be extracted as follows:

package main

import "fmt"

func main() {
	// ... Initialization code

	count := 0
	for i, num := range arr {
		for j, num2 := range arr {
			if i >= j {
				continue
			}
			if num+num2 == target {
				count++
			}
		}
	}
	fmt.Println(count)
}

This method blindly searches by looping twice through the array.

However, given the constraint on n, where 1 ≤ n ≤ 100000, using this method results in a worst-case scenario of O(n^2).

If the maximum input is provided, you would need to compare 100,000 * 100,000 = 10,000,000,000 values.

Naturally, running this code results in a timeout error.

We need to think of a faster and more efficient solution.

2. Solving with Two Pointers

There is a method called Two Pointers. It involves moving two pointers over a single array to find the solution.

In this problem, if we sort the array, we can easily solve it using the two-pointer technique.

For a sorted array, the start pointer begins at 0 and the end pointer starts at n-1.

Let’s assume we receive the following input:

arr = [5, 1, 3, 2, 4]
target = 5

Sorting this will give:

Now, let’s see what happens as we start searching with start at 0 and end at 4.

Stage 1

count = 0

The sum of the two numbers is 6.

Since it’s greater than 5, we decrement end.

Stage 2

count = 0

Now, the sum of the two numbers is 5.

Since the sum equals target, we increment count.

With distinct values in the array, we move both pointers. start goes to 1 and end goes to 2.

Stage 3

count = 1

Even after moving the pointers, the sum remains 5.

Since it equals target, we increment count again.

After moving the pointers, start goes to 2 and end goes to 1.

Now that start is greater than end, we end our search.

Time Complexity

The time complexity of this logic using the two-pointer method is O(n) since after sorting it requires an additional O(n*Log(n)), making the final time complexity O(n*Log(n)).

Final Code

The final code is as follows:

package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"sort"
)

// https://www.acmicpc.net/problem/3273 - Two Sum

func main() {
	writer := bufio.NewWriter(os.Stdout)
	reader := bufio.NewReader(os.Stdin)
	defer writer.Flush()

	var n int
	if _, err := fmt.Fscanln(reader, &n); err != nil {
		log.Fatal(err)
	}

	arr := make([]int, n)
	for i := 0; i < n; i++ {
		if _, err := fmt.Fscan(reader, &arr[i]); err != nil {
			log.Fatal(err)
		}
	}
	if _, err := fmt.Fscanln(reader); err != nil {
		log.Fatal(err)
	}
	var target int
	if _, err := fmt.Fscanln(reader, &target); err != nil {
		log.Fatal(err)
	}

	sort.Ints(arr)

	count := 0
	start, end := 0, len(arr)-1
	for start < end {
		sum := arr[start] + arr[end]
		if sum == target {
			count++
			start++
			end--
		}
		if sum > target {
			end--
		}
		if sum < target {
			start++
		}
	}

	fmt.Println(count)
}

3. Implementing with Hash

We can also solve the problem using hash maps.

With complements and a hash map, for a complement of 10 and a value of 4, it would be calculated as 10 - 4 = 6.

Let’s look at the logic with the same array as before:

Stage 1

count = 0

Array

Hash Map

Initially, when i is at index 0, the value is 5. We check if the complement 0 is present in the hash map.

Since it is not, we keep the count as is and add the current value to the hash map.

Stage 2

count = 0

Array

Hash Map

Next, when i=1, the value is 1. We look for its complement, 4, in the hash map.

Since the key 4 is not present in the hash map, we keep the count as is and add the current value to the hash map.

Stage 3

count = 0

Array

Hash Map

Next, i=2 has the value 3. Its complement 2 is looked up in the hash map.

The key 2 is not there, so we keep the count and add the current value to the hash map.

Stage 4

count = 0

Array

Hash Map

Now, i=3 has the value 2, which has complement 3 in the hash map.

Since the key 3 exists, we increment the count and add the current value to the hash map.

Stage 5

count = 1

Array

Hash Map

Finally at i=4, the value is 4. Looking for its complement 1 in the hash map gives a key match.

We increment the count to 2.

Result

count = 2

Array

Hash Map

When i reaches 5, the process terminates. The final count is 2.

Time Complexity

Using the hash approach does not require sorting and involves only a single loop, leading to a time complexity of O(n).

However, due to the nature of maps, the memory usage may significantly increase depending on the input. (Of course, the space complexity differs based on the implementation of the hash map.)

Final Code

Here is the implementation in Go:

package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
)

// https://www.acmicpc.net/problem/3273 - Two Sum

func main() {
	writer := bufio.NewWriter(os.Stdout)
	reader := bufio.NewReader(os.Stdin)
	defer writer.Flush()

	var n int
	if _, err := fmt.Fscanln(reader, &n); err != nil {
		log.Fatal(err)
	}

	arr := make([]int, n)
	for i := 0; i < n; i++ {
		if _, err := fmt.Fscan(reader, &arr[i]); err != nil {
			log.Fatal(err)
		}
	}
	if _, err := fmt.Fscanln(reader); err != nil {
		log.Fatal(err)
	}
	var target int
	if _, err := fmt.Fscanln(reader, &target); err != nil {
		log.Fatal(err)
	}

	count := 0
	idxMap := make(map[int]int)
	for i, num := range arr {
		// Check for complement of num in the hash map
		if _, ok := idxMap[target-num]; ok {
			count++
		}
		// Add current value to the hash map
		idxMap[num] = i
	}

	if _, err := fmt.Fprintln(writer, count); err != nil {
		log.Fatal(err)
	}
}

Conclusion

We have successfully solved the problem using both hash and two-pointer methods.

Reviewing and organizing my thoughts on similar problems I may face during coding tests was helpful.

Admittedly, I initially solved it using the first method in a rather foolish way. 🤣

(It seems like I’ve lost my touch after a long time without solving algorithm problems; I over-simplified my thinking.)

Afterwards, I tried solving it with Binary Search and faced failures but realized a good approach after some more thought.

(I wonder why I can’t think of these methods during exams. 😭)

Regularly practicing similar problems and documenting them when they come to mind will undoubtedly aid during tests.

Let’s go, fighting!