Two sum problem algorithm and solutions in Java and Python

Let’s go step-by-step through the Two Sum problem, covering:

1️⃣ Definition 2️⃣ Brute-force approach (O(n²)) 3️⃣ Optimized approach using HashMap (O(n)) 4️⃣ Common variations with examples 5️⃣ Code in both Java and Python

---

🧩 1. Problem Definition

Problem statement:

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

You may assume that each input has exactly one solution and you cannot use the same element twice.

Example:

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

---

⚙️ 2. Brute Force Approach (O(n²))

Idea:

Try every possible pair (i, j) and check if nums[i] + nums[j] == target.

🧠 Time complexity:

• O(n²) → double loop
• O(1) extra space

---

✅ Java Version:

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};
                }
            }
        }
        return new int[]{}; // no solution
    }

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

---

✅ Python Version:

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

nums = [2, 7, 11, 15]
target = 9
print(two_sum_brute(nums, target))  # Output: [0, 1]

---

⚡ 3. Optimized Approach — Using HashMap (O(n))

Idea:

Use a hashmap to store visited numbers and their indices. For each number num, check if (target - num) is already in the map.

🧠 Time complexity:

• O(n) time
• O(n) extra space

---

✅ Java Version:

import java.util.*;

public class TwoSumOptimized {
    public static 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[]{};
    }

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

---

✅ Python Version:

def two_sum_optimized(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

nums = [2, 7, 11, 15]
target = 9
print(two_sum_optimized(nums, target))  # Output: [0, 1]

---

🔁 4. Variations of the Two Sum Problem

Here are common variations and their examples 👇

Variation	Description	Example
1. Two Sum II (sorted array)	Array is sorted — use two pointers	[2,3,4,6], target=6 → [0,2]
2. Two Sum - Multiple pairs	Return all unique pairs that sum to target	[1,2,3,4,5], target=6 → [[1,5],[2,4]]
3. 3Sum	Find triplets that sum to zero	[−1,0,1,2,−1,−4] → [[−1,−1,2],[−1,0,1]]
4. Two Sum Closest	Find two numbers whose sum is closest to target	Used in stock or pricing optimization
5. Two Sum in a stream	Handle continuously incoming numbers	Useful in real-time systems or finance data streams

---

🧠 Example: Two Sum II (Sorted Array) — Two Pointers Approach

Python:

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        curr_sum = nums[left] + nums[right]
        if curr_sum == target:
            return [left, right]
        elif curr_sum < target:
            left += 1
        else:
            right -= 1

Java:

public int[] twoSumSorted(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{};
}

---

🧭 Summary

Approach	Data Structure	Time	Space
Brute Force	None	O(n²)	O(1)
HashMap	HashMap	O(n)	O(n)
Two Pointers (sorted array)	None	O(n)	O(1)

---