Pair Sum in Java: An Optimized Solution using HashSet

 Finding a pair in an array whose sum is equal to a given number is a common problem in computer science. The straightforward solution to this problem involves using nested loops to compare each element with every other element in the array, resulting in a time complexity of O(n^2). However, this approach can be inefficient for large arrays. In this article, we will discuss an optimized solution using HashSet in Java to solve this problem in linear time complexity.

The problem statement is as follows: Given an array of integers and a target sum, determine whether any pair of integers in the array adds up to the target sum. If such a pair exists, return true; otherwise, return false.

Let's take an example to understand the problem better.

Example:

Input: arr[] = {5, 9, 8, 13, 2, 4}, sum = 7 Output: True Explanation: 5 + 2 = 7

Input: arr[] = {5, 9, 8, 13, 2, 4}, sum = 3 Output: False Explanation: No pairs sum = 3

Approach:

To solve this problem, we can use a HashSet data structure to store the elements of the array as we traverse it. For each element in the array, we check if the difference between the target sum and the current element is present in the HashSet. If it is, we know that we have found a pair whose sum is equal to the target sum. If it's not, we add the current element to the HashSet, and the loop continues.

Let's break down the approach into the following steps:

1. Create an empty HashSet.
2. Traverse the array.
3. For each element in the array, find the difference between the target sum and the current element.
4. Check if the difference is present in the HashSet.
5. If it is, return true.
6. If it's not, add the current element to the HashSet.
7. Repeat steps 3 to 6 for the rest of the elements in the array.
8. If no such pair is found, return false.

Let's implement the above approach in Java.

Implementation:

import java.util.HashSet;

public class PairSum {

csharp
public static boolean checkPairSum(int[] arr, int sum) {
    
    // Create an empty HashSet
    HashSet<Integer> set = new HashSet<>();
    
    // Traverse the array
    for(int i = 0; i < arr.length; i++) {
        
        // Find the difference between the target sum and the current element
        int diff = sum - arr[i];
        
        // Check if the difference is present in the HashSet
        if(set.contains(diff)) {
            return true;
        }
        
        // Add the current element to the HashSet
        set.add(arr[i]);
    }
    
    // If no such pair is found
    return false;
}

public static void main(String[] args) {
    
    int[] arr = {5, 9, 8, 13, 2, 4};
    int sum = 7;
    
    if(checkPairSum(arr, sum)) {
        System.out.println("True");
    }
    else {
        System.out.println("False");
    }
}

}

Output: True

Time Complexity:

The time complexity of the above approach is O(n) since we are traversing the array only once. The time complexity of checking if an element is present in a HashSet is O(1) on average. Therefore, the total time complexity of the algorithm is O(n).

Space Complexity:

The space complexity of the above approach is O(n) since we are creating a HashSet to store the elements. However, this space complexity is necessary as we need to store all the elements to be able to check if there exists a pair whose sum is equal to the given sum.

It is important to note that this approach works only for arrays with distinct elements. If the array contains duplicates, this approach may give incorrect results. In such cases, we would need to modify the approach to handle duplicates.

In conclusion, we can use a HashSet to efficiently solve the problem of finding a pair in an array whose sum is equal to a given sum. The time complexity of the approach is O(N) and the space complexity is O(N). This approach can be further optimized by sorting the array and then using two pointers to traverse the array from both ends. This approach would have a time complexity of O(NlogN) due to sorting, but the space complexity would be reduced to O(1) as we would not need to create a HashSet to store the elements.