3. Two Sum

Here’s a progression from brute force to the most optimal solution for the Two Sum problem on LeetCode, with detailed explanations, code examples in Java, and time and space complexity analysis.

---

Problem Statement:

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to the target.

Example:

Input: nums = [2, 7, 11, 15], target = 9  
Output: [0, 1]  
Explanation: nums[0] + nums[1] = 2 + 7 = 9  

---

Approach 1: Brute Force (O(n²))

Steps:

1. Iterate through each number i in the array.
2. For each i, iterate again through the rest of the array j > i.
3. Check if nums[i] + nums[j] == target.
4. Return the indices [i, j] if a match is found.

Code (Java):

public class TwoSumBruteForce {
    public static int[] twoSum(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};  // Found the pair
                }
            }
        }
        throw new IllegalArgumentException("No solution found!");
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println("Indices: [" + result[0] + ", " + result[1] + "]");
    }
}

Time Complexity:

• O(n²) because of the nested loops.

Space Complexity:

• O(1) – No extra space is used, apart from the result array.

---

Approach 2: Using HashMap – Two-pass solution (O(n))

Steps:

1. Create a HashMap to store the difference needed to reach the target.
2. In the first pass, store each number along with its index in the HashMap.
3. In the second pass, check if the complement (target - nums[i]) exists in the HashMap and that it’s not the same index.

Code (Java):

import java.util.HashMap;

public class TwoSumHashMapTwoPass {
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();

        // First pass: add numbers and their indices to the map
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        // Second pass: find complement
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[]{i, map.get(complement)};
            }
        }

        throw new IllegalArgumentException("No solution found!");
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println("Indices: [" + result[0] + ", " + result[1] + "]");
    }
}

Time Complexity:

• O(n) – We iterate through the array twice.

Space Complexity:

• O(n) – We store all numbers in the HashMap.

---

Approach 3: Using HashMap – One-pass solution (Most Optimal)

Steps:

1. Use a single pass through the array.
2. While iterating, calculate the complement (target - nums[i]).
3. Check if the complement already exists in the HashMap:

• If yes, return the current index and the index of the complement.
• If no, store the current number along with its index in the HashMap.

Code (Java):

import java.util.HashMap;

public class TwoSumOptimal {
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();

        // Single pass
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};  // Return complement's index and current index
            }
            map.put(nums[i], i);
        }

        throw new IllegalArgumentException("No solution found!");
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println("Indices: [" + result[0] + ", " + result[1] + "]");
    }
}

Time Complexity:

• O(n) – We iterate through the array once.

Space Complexity:

• O(n) – We store at most n numbers in the HashMap.

---

Summary of Approaches:

Approach	Time Complexity	Space Complexity	Explanation
1. Brute Force	O(n²)	O(1)	Compare every pair of numbers (nested loops).
2. HashMap (Two-pass)	O(n)	O(n)	Two loops: build map, then find complement.
3. HashMap (One-pass)	O(n)	O(n)	Single pass: build map while checking complement.

---

Most Optimal Approach: One-pass HashMap (O(n))

This approach is the fastest and uses efficient constant-time HashMap operations.

---