Two Sum Problem

Problem Statement

Write a Java program that uses a hash table to solve the Two Sum problem: given an array of integers and a target sum, find two numbers in the array that add up to the target sum and return their indices. The hash table should store numbers as keys and their indices as values. The solution should assume each input has at most one valid pair of indices and that no number can be used twice. Test the implementation with different arrays and target sums, including cases with no solution, valid solutions, and edge cases like empty arrays or arrays with fewer than two elements. You can visualize this as searching a list of numbers to find a pair of puzzle pieces that fit together to match a specific total.

Input:

• An array of integers and a target sum (integer). Output: An array of two integers representing the indices of the two numbers that sum to the target, or an empty array if no solution exists. Constraints:
• The array length is between 0 and 10^5.
• Array elements and the target sum are integers in the range [-10^9, 10^9].
• Each input has at most one valid solution.
• The same element cannot be used twice. Example:
• Input: Array = [2, 7, 11, 15], Target = 9
• Output: [0, 1]
• Explanation: 2 + 7 = 9, indices 0 and 1.
• Input: Array = [3, 2, 4], Target = 8
• Output: []
• Explanation: No pair sums to 8.
• Input: Array = [], Target = 5
• Output: []
• Explanation: Empty array, no solution.

Pseudocode

FUNCTION twoSum(numbers, target)
    CREATE hashTable as new HashMap
    FOR i from 0 to numbers length - 1
        SET complement to target - numbers[i]
        IF hashTable contains complement THEN
            RETURN array of [hashTable[complement], i]
        ENDIF
        SET hashTable[numbers[i]] to i
    ENDFOR
    RETURN empty array
ENDFUNCTION

FUNCTION main()
    SET testCases to array of (numbers, target) pairs
    FOR each testCase in testCases
        PRINT test case details
        CALL twoSum(testCase.numbers, testCase.target)
        PRINT result
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define twoSum: a. Create a HashMap<Integer, Integer> to store numbers and their indices. b. For each number at index i:
   • Compute complement = target - number.
   • If complement exists in hash table, return [hashTable[complement], i].
   • Otherwise, add number and its index to hash table. c. If no solution is found, return empty array.
2. In main, test with: a. Arrays with a valid solution. b. Arrays with no solution. c. Empty array. d. Array with one element. e. Array with duplicate numbers.

Java Implementation

import java.util.*;

public class TwoSumProblem {
    // Solves the Two Sum problem using a hash table
    public int[] twoSum(int[] numbers, int target) {
        HashMap<Integer, Integer> hashTable = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            int complement = target - numbers[i];
            if (hashTable.containsKey(complement)) {
                return new int[] {hashTable.get(complement), i};
            }
            hashTable.put(numbers[i], i);
        }
        return new int[] {};
    }

    // Main method to test Two Sum
    public static void main(String[] args) {
        TwoSumProblem solver = new TwoSumProblem();

        // Test cases
        Object[] testCases = {
            new Object[] {new int[] {2, 7, 11, 15}, 9},    // Valid solution
            new Object[] {new int[] {3, 2, 4}, 8},         // No solution
            new Object[] {new int[] {}, 5},                // Empty array
            new Object[] {new int[] {1}, 2},               // Single element
            new Object[] {new int[] {3, 3}, 6}             // Duplicate numbers
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            int[] numbers = (int[]) ((Object[]) testCases[i])[0];
            int target = (int) ((Object[]) testCases[i])[1];
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Input array: " + Arrays.toString(numbers));
            System.out.println("Target sum: " + target);
            int[] result = solver.twoSum(numbers, target);
            System.out.println("Result: " + Arrays.toString(result) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input array: [2, 7, 11, 15]
Target sum: 9
Result: [0, 1]

Test case 2:
Input array: [3, 2, 4]
Target sum: 8
Result: []

Test case 3:
Input array: []
Target sum: 5
Result: []

Test case 4:
Input array: [1]
Target sum: 2
Result: []

Test case 5:
Input array: [3, 3]
Target sum: 6
Result: [0, 1]

Explanation:

• Test case 1: 2 + 7 = 9, returns indices [0, 1].
• Test case 2: No pair sums to 8, returns [].
• Test case 3: Empty array, returns [].
• Test case 4: Single element, no pair possible, returns [].
• Test case 5: 3 + 3 = 6, returns indices [0, 1].

How It Works

• twoSum:
  • Uses a HashMap<Integer, Integer> to store numbers and their indices.
  • For each number, checks if complement (target - number) exists in hash table.
  • If found, returns indices of complement and current number.
  • Otherwise, adds current number and index to hash table.
  • Returns empty array if no solution is found.
• Example Trace (Test case 1):
  • Input: [2, 7, 11, 15], target=9.
  • i=0: complement=9-2=7, hashTable={}, add {2:0}.
  • i=1: complement=9-7=2, hashTable={2:0}, return [0, 1].
• Main Method: Tests valid solution, no solution, empty array, single element, and duplicates.

Complexity Analysis Table

Note:

• n is the length of the input array.
• Time complexity: O(n) for single pass through array; HashMap operations (put, get) are O(1) average case.
• Space complexity: O(n) for storing up to n numbers in HashMap.
• Worst case: O(n) time and space when all numbers are processed.

✅ Tip: Use a single-pass approach with a hash table to achieve O(n) time complexity, storing numbers and indices to quickly find the complement.

⚠ Warning: Ensure the solution handles edge cases like empty arrays or arrays with fewer than two elements. Avoid using the same element twice by checking the complement before adding the current number.