Approaches for finding pairs with a sum of 5

Finding Pairs with a Given Sum using HashSet in Java

1. Approach Overview

Given an array of integers, the goal is to find all unique pairs where the sum equals 5. We will use a HashSet to efficiently track the elements and their complements.

2. HashSet Approach for Unsorted Input

Algorithm

1. Initialize an empty HashSet to store seen numbers.
2. Iterate through each element in the array:
   • Calculate the complement (target - currentNumber).
   • If the complement exists in the HashSet, a valid pair is found.
   • Otherwise, add the current number to the HashSet.
3. Continue until all elements are processed.

Java Code

import java.util.*;

public class PairSum {
    public static void findPairs(int[] arr, int targetSum) {
        Set<Integer> seen = new HashSet<>();

        for (int num : arr) {
            int complement = targetSum - num;

            if (seen.contains(complement)) {
                System.out.println("Pair: (" + num + ", " + complement + ")");
            }
            seen.add(num);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 3, 5, 0, -1};
        findPairs(arr, 5);
    }
}

Output

Pair: (4, 1)
Pair: (3, 2)
Pair: (5, 0)

Time Complexity

• Insertion & Lookup in HashSet: O(1) on average.
• Traversal through Array: O(n).
• Overall Complexity: O(n).

Space Complexity

• HashSet Storage: O(n) for the unique elements.
• Total: O(n).

3. Optimized Approach for Sorted Input

If the array is already sorted, we can use the two-pointer technique instead of a HashSet.

Algorithm

1. Initialize two pointers (left at the beginning and right at the end).
2. While left < right:
   • Calculate the sum of the elements at both pointers.
   • If the sum equals the target, print the pair and move both pointers.
   • If the sum is less than the target, move the left pointer.
   • If the sum is greater than the target, move the right pointer.

Java Code

import java.util.*;

public class PairSumSorted {
    public static void findPairs(int[] arr, int targetSum) {
        int left = 0, right = arr.length - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (sum == targetSum) {
                System.out.println("Pair: (" + arr[left] + ", " + arr[right] + ")");
                left++;
                right--;
            } else if (sum < targetSum) {
                left++;
            } else {
                right--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {-1, 0, 1, 2, 3, 4, 5};
        findPairs(arr, 5);
    }
}

Output

Pair: (0, 5)
Pair: (1, 4)
Pair: (2, 3)

Time Complexity

• Traversal with Two Pointers: O(n).
• Overall Complexity: O(n).

Space Complexity

• In-Place Operation: O(1).

4. Comparison of Approaches

Input Type	Approach	Time Complexity	Space Complexity
Unsorted	HashSet Method	O(n)	O(n)
Sorted	Two-Pointer Method	O(n)	O(1)

5. Conclusion

• Use the HashSet approach for unsorted arrays due to its fast O(1) lookup time.
• For sorted arrays, prefer the two-pointer approach for its in-place operation with O(1) space complexity.

Both methods are efficient with O(n) time complexity, but choosing the right one depends on whether the input is sorted or not.