1. Overview
In this tutorial, we’ll discuss three methods to check whether or not the sum of any two numbers in an array matches a given number.
First, we’ll begin the discussion with the naive solution. Then we’ll discuss two optimal solutions to solve the same problem.
2. Problem Statement
Given an unsorted array of integer nums and an integer target, we need to check if the sum of any two numbers from the nums array matches with the target. The method should return the boolean true or false value to indicate success or failure.
Let’s understand this with a few examples.
2.1. When the Pair With the Given Sum Exists
- Input: nums = [10, 5, 15, 7, 14, 1, 9], target = 6
- Output: true
- Explanation: Here, the method should return a boolean true because the array has two numbers whose sum is 6. These two numbers are present at index 1 and 5 respectively.
2.2. When the Pair With the Given Sum Doesn’t Exist
- Input: nums = [10, 5, 15, 7, 14, 1, 9], target = 27
- Output: false
- Explanation: In this example, the method should return a boolean false because there aren’t two numbers in the nums array whose sum is 27.
3. Brute Force Solution
We can use the brute force approach to solve this problem. This method uses two nested loops.
Initially, the outer loop points to the first element of the array, whereas the inner loop point to the second element of the array. Then for each iteration, we check if two numbers are present whose sum matches the given target.
The pseudo-code for the brute force method looks like the following:
algorithm BruteForceSolution(A, n, t):
// INPUT:
// A = an unsorted array of integers, indexed from 0 to n - 1
// n = the size of the array
// t = the target sum
// OUTPUT:
// Returns true or false to indicate success or failure
for i <- 0 to n - 1:
for j <- i + 1 to n - 1:
sum <- A[i] + A[j]
if sum = t:
return true
return false
In this example, we are visiting each and every element of the array using two nested while loops. Hence the time complexity of this algorithm is O( n2 ). Whereas the space complexity is constant, i.e. O(1).
4. Optimal Solution
In the previous section, we used the brute force method. However, that isn’t the most efficient method. This section will discuss two optimal solutions that use sorting and additional space to improve time complexity.
4.1. Using the Sorting and Two Pointers Method
We can use the sorting and two-pointer method to solve this problem. This method improves the runtime complexity without affecting the space complexity.
To use this method, the array elements must be sorted in ascending order. First, we’ll initialize two pointers that point to the first and last elements of the array respectively. Then, we’ll increment the first pointer if the sum of the two numbers is lesser than the target sum. Similarly, we’ll decrement the last pointer if the sum of the two numbers is greater than the target sum.
We’ll repeat this process until we find the required pair or the array elements are exhausted.
Now, let’s write the pseudo-code for the same:
algorithm SortingAndTwoPointers(A, n, t):
// INPUT:
// A = an unsorted array of integers (0-based indexing)
// n = the size of the array
// t = the target sum
// OUTPUT:
// Returns true or false to indicate success or failure
sort the array A
start <- 0
end <- n - 1
while start < end:
sum <- A[start] + A[end]
if sum = t:
return true
else if sum < t:
start <- start + 1
else:
end <- end - 1
return false
Here, we sort the array and then iterate over it to find the target sum. The average time complexity of the sorting algorithm is O(nlogn) if we use in-place sorting algorithms, such as quick sort or heap sort. In addition, the array traversal’s time complexity is O(n).
So the overall time complexity of this algorithm is O(nlogn), whereas the space complexity is constant, i.e. O(1)
4.2. Using the Hash Table
In the previous example, we improved the time complexity by sorting the array. However, we can improve the time complexity further by using some additional space. To accomplish this, we can use the hash table data structure.
For each iteration, we’ll calculate the diff by subtracting the current element from the target. Then, we’ll return true if the diff is present in the hash table otherwise we’ll insert the current element into the hash table. This process will repeat until we find the required pair or the array elements are exhausted.
The pseudo-code for this algorithm looks like the following:
algorithm HashTableMethod(A, n, t):
// INPUT:
// A = an unsorted array of integers (0-based indexing)
// n = the size of the array
// t = the target sum
// OUTPUT:
// Returns true or false to indicate success or failure
hashtable = make an empty hash table
for i <- 0 to n - 1:
diff <- t - A[i]
if diff in hashtable:
return true
insert A[i] into hashtable
return false
In this example, we used the Hash Table, which performs insert and lookup operations in constant time. In the worst case, we have to visit and insert each and every element of the array. Hence, this algorithm’s time/space complexity is linear, i.e. O(n).
5. Conclusion
In this article, we discussed three methods to check if there are two numbers whose sum matches a given number.
First, we discussed the problem statement. Then, we discussed the brute force solution. Next, we used a sorting mechanism to solve the problem in logarithmic time. Finally, we used an additional space to solve the problem in linear time.