One of the most foundational algorithmic questions in software engineering interviews is the Two Sum problem, often presented on coding platforms like HackerRank. The problem statement is simple: given an array of integers and a target sum, determine if there exists a pair of numbers in the array that add up to the target.

While a straightforward solution involving nested loops is easy to implement, it suffers from a slow O(N²) quadratic time complexity. This makes it impractical for large datasets. Fortunately, we can optimize this lookup to linear O(N) time complexity using a complements search with a hash set.

Illustration representing index pairs and target sum complement search
Real-World Analogy: The Social Security Matchmaker

To understand this optimized search, imagine you are a matchmaker hosting a party. Your task is to find if there are any two guests in the room whose cards add up to 10.

Instead of having everyone walk around and ask every other guest for their number, you set up a blackboard (our hash set) near the entrance:

  • The first guest arrives holding card 3. They calculate: *"To get to 10, I need a partner holding card 7 (10 - 3 = 7)."*
  • They look at the blackboard. Since card 3 is not written on the board, they calculate their complement partner needed (10 - 3 = 7), write 7 on the blackboard, and mingle.
  • A few minutes later, another guest arrives holding card 7. They calculate: *"To get to 10, I need a partner holding card 3 (10 - 7 = 3)."*
  • They look at the board, see 7 is already written there (written by the guest who brought card 3), and declare: *"We have a match!"*
This strategy allows us to find a valid pair in a single pass, without requiring guests to compare cards with everyone else.

Technical Strategy

In Java, we can implement this search using a HashSet:

  • As we iterate through the integer array, we check if the current element is in our complements board.
  • If the HashSet already contains the current number, it means a previous number was waiting for this exact number. We return true.
  • If the current number is not in the set, we calculate its complement (target - currentNumber) and store it in our complements board.
By using a hash set, we reduce lookup times to constant O(1) time, achieving an overall linear runtime.

Step-by-Step Scenario Trace

Let's trace the execution on a sample input: arr = [10, 15, 3, 7] with a target sum of 10:

  1. First element (10): Set is empty. Complements set does not contain 10. We insert complement 10 - 10 = 0. Set: [0].
  2. Second element (15): Set doesn't contain 15. We insert complement 10 - 15 = -5. Set: [0, -5].
  3. Third element (3): Set doesn't contain 3. We insert complement 10 - 3 = 7. Set: [0, -5, 7].
  4. Fourth element (7): Set contains 7! This means a previous element (which was 3) calculated that it needed a 7, and stored it. We return true immediately.
Match found! We return true in one pass.

Java Implementation Code

We can write this cleanly using Java 8 Stream's anyMatch() method:

package io.practise.hackerrank;
 
import java.util.HashSet;
import java.util.stream.IntStream;
 
public class FindSumPair {
    public static void main(String[] args) {
        int[] arr = {10, 15, 3, 7};
        int target = 10;
 
        HashSet<Integer> complements = new HashSet<>();
 
        boolean hasPair = IntStream.of(arr).anyMatch(num -> {
            // If the current number is the complement some previous number was looking for
            if (complements.contains(num)) {
                return true; 
            }
            // Store the complement partner needed for the current number
            complements.add(target - num);
            return false;
        });
 
        System.out.println("Has pair summing to " + target + "? " + hasPair); // Prints: true (7 + 3)
    }
}

Conclusion & Complexity Analysis

Using a HashSet to store complement demands transforms a slow O(N²) nested loop search into a fast O(N) lookup. HashSet contains check operations run in constant O(1) time, representing the most optimal scaling solution for search pairings.