Java  

What is the Two Sum Problem in DSA.

🧩 What is the Two Sum Problem? 

The Two Sum Problem is a classic Data Structures and Algorithms question you’ll see in coding interviews.

  • A list (array) of numbers.
  • A target number.

Find two different numbers in the array that add up exactly to the target number, and return their positions (indices).

Example:

Array:  [2, 7, 11, 15]  
Target: 9  
Answer: [0, 1]  // Because 2 + 7 = 9

In this example:

  • 0 is the position of 2 in the array.
  • 1 is the position of 7 in the array.

📜 Problem Statement in Java

When solving the problem in Java, we usually write it as:

public int[] twoSum(int[] nums, int target)

Where:

  • nums: the given array of numbers.
  • target: the sum we are trying to find.
  • Output: an array with two numbers, which are the indices of the elements that add up to target.

🐌 Brute Force Approach

What is Brute Force?

Brute force means trying every possible combination until you find the answer. It’s like checking every pair of shoes in a shop until you find the perfect match.

How It Works for Two Sum:

  1. Start at the first number in the array.
  2. Pair it with every other number that comes after it.
  3. Check if their sum equals the target.
  4. If yes - return their positions (indices).
  5. If no - move to the next number and repeat.

Why It’s Simple but Slow:

  • If you have a small array, this is fine.
  • If you have a large array (like 10,000 numbers), it will take too long because you’re checking every possible pair.

Time and Space Complexity:

  • Time Complexity: O(n²): If you double the size of the array, the time it takes grows a lot.
  • Space Complexity: O(1): No extra storage is needed.

Example Brute Force:

public int[] twoSumBruteForce(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[] {}; // If no solution found
}

⚡ Optimal Solution Using Hash Map

What is a Hash Map?

A hash map is like a smart dictionary where:

  • You have a key (like a word).
  • You have a value (like the meaning of the word).

You can look up any key instantly, without searching through everything.

How It Works for Two Sum:

  • Start with an empty hash map.
  • Go through the array one number at a time.
  • For the current number, find out what number would complete the target:
complement = target - currentNumber

  • Check if this complement is already in the hash map:

    • If yes: we have found our answer (return the stored index and the current index).
    • If no: store the current number in the hash map with its index.

Why It’s Fast:

  • You only pass through the array once.
  • Each lookup in the hash map takes constant time (O(1)).

Time and Space Complexity:

  • Time Complexity: O(n) Much faster than O(n²).
  • Space Complexity: O(n) Uses extra memory to store seen numbers.

Example Optimal Solution:

import java.util.*;

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[] {}; // If no solution found
}

🧠 Why Interviewers Ask the Two Sum Question

  • Tests your basics: Can you loop through arrays?
  • Checks your problem-solving: Can you think of faster ways?
  • Introduces optimization: Can you improve from O(n²) to O(n)?
  • Leads to harder problems: Two Sum is the first step to learning other “pair sum” problems.

📚 Summary

The brute force approach checks all possible pairs and is easy to understand, but it’s slow for large arrays. The optimal solution uses a hash map to solve the problem in a single pass, making it much faster. By learning this problem, you not only understand arrays and hash maps better but also prepare yourself for more advanced problems in coding interviews.

Membership not found