Understanding Two Sum in Java

Introduction & Problem Explanation

The Two Sum problem is a fundamental coding question. We are given an array of integers nums and a single integer value target. Our goal is to find the indices of two distinct numbers in the array that sum up to exactly the target value.

This problem is commonly used to test understanding of basic data structures. The key challenges include handling potentially large arrays, avoiding using the same element twice, and finding a solution in optimal time rather than resorting to checking every possible combination.

The Algorithmic Approach

1. The Brute Force Approach (O(n²))

We check every possible pair of elements in the array using two nested loops. While easy to implement, this is highly inefficient because it has a quadratic time complexity of O(n²). For an array of size 10,000, it would require up to 100,000,000 comparisons, which scales poorly.

2. The Optimized Approach (O(n) Time, O(n) Space)

By using a HashMap, we can trade memory for speed. As we iterate through the array once, we calculate the required complement: complement = target - nums[i]. We check if this complement already exists in our map. If it does, we immediately return the stored index and the current index. If it doesn't, we store the current number and its index in the map, ensuring future numbers can find it. This reduces the time complexity to O(n) since lookup operations in a HashMap take O(1) average time.

Step-by-Step Execution Walkthrough

Let's trace the optimized algorithm on the input array nums = [2, 7, 11, 15] with target = 9:

1. Step 1 (Initialization): We create a HashMap to store values as keys and their corresponding indices as values. The map is initially empty: map = {}.
2. Step 2 (Index i = 0): We look at the first number, 2.
   • Calculate the complement: complement = target - nums[0] = 9 - 2 = 7.
   • Check if the complement 7 exists in the map. It does not: map.containsKey(7) is false.
   • Since it's not found, we store the current number 2 and its index 0 in the map. The map is now: {2: 0}.
3. Step 3 (Index i = 1): We move to the second number, 7.
   • Calculate the complement: complement = target - nums[1] = 9 - 7 = 2.
   • Check if the complement 2 exists in the map. Yes! map.containsKey(2) is true. We look up the index of 2, which is 0.
   • We have found a valid pair: nums[0] (2) + nums[1] (7) = 9.
4. Step 4 (Completion): The method immediately returns the pair of indices [0, 1]. The iteration stops, avoiding any further unnecessary searches.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• int complement = target - nums[i];: This calculates the exact mathematical match needed to satisfy the equation nums[i] + complement = target.
• map.containsKey(complement): By looking up the complement in the HashMap, we bypass checking all other elements, reducing the lookup time to a constant O(1).
• map.put(nums[i], i);: Storing each visited element ensures that elements appearing later in the array can match with it.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    
    // Brute Force - O(n^2)
    public int[] twoSumBrute(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }

    // Optimized - O(n) using HashMap
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        TwoSum solver = new TwoSum();
        int[] nums = {2, 7, 11, 15};
        int target = 9;

        System.out.println("--- Two Sum Demonstration ---");
        System.out.println("Input Array: " + Arrays.toString(nums));
        System.out.println("Target: " + target);

        System.out.println("\nExecuting Optimized Approach...");
        System.out.println("Step 1: Create a HashMap to store (number -> index).");
        
        int[] result = solver.twoSum(nums, target);
        System.out.println("Step 2: Iterate through the array:");
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            System.out.printf("  Index %d: value = %d. Complement needed = %d - %d = %d.\n", 
                i, nums[i], target, nums[i], complement);
            if (i == 1) {
                System.out.printf("  Success: Complement %d is already in the map (index 0). Found indices: [0, 1].\n", complement);
            }
        }
        System.out.println("Result Indices: " + Arrays.toString(result));
    }
}

Conclusion

Solving the Two Sum problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.