Two Sum Problem in DSA (Array + HashMap Approach)

Introduction

The Two Sum Problem is one of the most commonly asked DSA interview questions, especially for beginners. It is often used by interviewers to check your understanding of arrays, searching, and hashing.

In simple words, this problem asks you to find two numbers in an array whose sum is equal to a given target value.

This article explains the Two Sum problem in easy and clear language, with proper examples and code that is easy to understand.

What is the Two Sum Problem?

You are given:

An array of integers
A target value

Your task is to find two different elements in the array such that their sum is equal to the target.

Example

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

Explanation

The numbers at index 0 and index 1 are 2 and 7.

2 + 7 = 9, which matches the target value.

Brute Force Approach (Basic but Slow)

In the brute-force method, we check every possible pair in the array.

Steps

Pick the first element
Compare it with every other element
Check if their sum equals the target

Drawbacks

Too many comparisons
Time Complexity becomes O(n²)

This approach is easy to understand but not efficient for large arrays.

Optimized Approach Using HashMap

To improve performance, we use a HashMap.

Idea Behind HashMap Approach

Store each number and its index in a map
For each number, check if the required value (target − current number) already exists
If yes, we have found the answer

This reduces unnecessary comparisons.

Step-by-Step Explanation

Let’s understand with an example:

nums = [2, 7, 11, 15]
target = 9

Steps:

Start with the first number (2)
Calculate required value = 9 − 2 = 7
7 is not in the map, so store 2
Move to next number (7)
Required value = 9 − 7 = 2
2 is already in the map → Answer found

Code Implementation

C++ Code

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;

    for (int i = 0; i < nums.size(); i++) {
        int required = target - nums[i];
        if (map.find(required) != map.end()) {
            return {map[required], i};
        }
        map[nums[i]] = i;
    }
    return {};
}

Java Code

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

    for (int i = 0; i < nums.length; i++) {
        int required = target - nums[i];
        if (map.containsKey(required)) {
            return new int[] { map.get(required), i };
        }
        map.put(nums[i], i);
    }
    return new int[] {};
}

Python Code

def twoSum(nums, target):
    seen = {}

    for i, num in enumerate(nums):
        required = target - num
        if required in seen:
            return [seen[required], i]
        seen[num] = i

Time and Space Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Using HashMap allows us to solve the problem in one pass.

Common Interview Questions Related to Two Sum

Can we solve it without extra space?
What if the array is sorted?
What if multiple pairs exist?

Interviewers often ask follow-up questions based on this problem.

Edge Cases in Two Sum Problem

When solving the Two Sum problem, it is important to think about special situations that can cause wrong answers if not handled properly.

Some common edge cases are:

The array is empty or has only one element (no pair possible)
No two numbers add up to the target value
The same number appears multiple times in the array
The target value is zero or a negative number

Always make sure your solution handles these cases safely.

Two Sum Problem Without Using HashMap

The Two Sum problem can also be solved without using extra space.

In this approach, we use two loops and check every possible pair.

How it works

Pick one element from the array
Compare it with all remaining elements
If their sum equals the target, return the answer

Drawback

Time Complexity becomes O(n²)
Not suitable for large input sizes

This approach is useful only for learning basics or when the input size is very small.

Two Sum in Sorted Array (Two Pointer Approach)

If the given array is already sorted, we can solve the Two Sum problem using the Two Pointer technique.

Idea

Place one pointer at the start of the array
Place another pointer at the end of the array
Move pointers based on the sum

Steps

If sum is equal to target → answer found
If sum is smaller than target → move left pointer forward
If sum is greater than target → move right pointer backward

Time Complexity

O(n)

Space Complexity

O(1)

This is an efficient approach for sorted arrays.

Dry Run Using HashMap (Step-by-Step)

Let us clearly understand how the HashMap solution works.

Example: nums = [2, 7, 11, 15], target = 9

Index	Value	Required	Map Status
0	2	7	{2:0}
1	7	2	Found in map

The required value is found in the map, so we return the indices.

What Should Be Returned in Two Sum Problem?

Different problem statements may ask for different outputs.

Some ask for indices of the two numbers
Some ask for the actual values

Always read the problem carefully before writing code.

Common Variations of Two Sum Asked in Interviews

Interviewers often extend the Two Sum problem to test deeper understanding.

Some popular variations are:

Two Sum with multiple answers
Two Sum closest to target
Two Sum in a sorted array
Two Sum in a Binary Search Tree

Understanding the basic Two Sum logic helps solve these variations easily.

Summary

The Two Sum Problem is a foundational DSA question that teaches how to optimize a simple solution using hashing. While the brute-force approach checks all pairs, the HashMap method reduces the time complexity to linear time. By understanding edge cases, alternative approaches, and common interview variations, you can confidently solve this problem in real interviews. Mastering Two Sum also prepares you for many advanced array and hashing problems.