Data Structures and Algorithms (DSA)  

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

  1. Pick the first element

  2. Compare it with every other element

  3. 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:

  1. Start with the first number (2)

  2. Calculate required value = 9 − 2 = 7

  3. 7 is not in the map, so store 2

  4. Move to next number (7)

  5. Required value = 9 − 7 = 2

  6. 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

  1. If sum is equal to target → answer found

  2. If sum is smaller than target → move left pointer forward

  3. 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

IndexValueRequiredMap Status
027{2:0}
172Found 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.

Membership not found