Two Sum Problem | leetcode solution | 2022

Two Sum Problem – LeetCode Solution Explained (Java | HashMap Approach)

4

The Two Sum problem is one of the most popular coding interview questions and is commonly asked in technical interviews by companies like **Google, Amazon, and Microsoft.

It tests your understanding of arrays, hash maps, and algorithm optimization.

In this guide, we will explain:

1. Problem statement

2. Examples

3. Optimized Java solutions

4. Time complexity

5. Interview tips

---

Problem Statement

The problem comes from LeetCode.

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

Rules:

1. Each input has exactly one valid solution

2. You cannot use the same element twice

3. Return indices in any order

---

Example 1

Input

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

Output

[0,1]

Explanation

nums[0] + nums[1] = 2 + 7 = 9

---

Example 2

Input

nums = [3,2,4]
target = 6

Output

[1,2]

---

Example 3

Input

nums = [3,3]
target = 6

Output

[0,1]

---

Constraints

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

Only one valid answer exists.

---

Approach – Using HashMap (Optimal Solution)

The most efficient way to solve this problem is by using a HashMap.

Idea

For each element:

1. Calculate the difference

difference = target - current number

2. Check if the difference exists in the HashMap

3. If yes → return the indices

4. If not → store the current number in the map

This reduces the time complexity significantly.

---

Java Solution (Optimized)

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < nums.length; i++) {

            int diff = target - nums[i];

            if(map.containsKey(diff)) {
                return new int[]{map.get(diff), i};
            }

            map.put(nums[i], i);
        }

        return new int[]{};
    }
}

---

Alternative Solution (Single Loop Optimization)

Another variation stores the required value instead of the current number.

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer, Integer> tracker = new HashMap<>();

        for(int i = 0; i < nums.length; i++) {

            if(tracker.containsKey(nums[i])) {
                return new int[]{tracker.get(nums[i]), i};
            }

            tracker.put(target - nums[i], i);
        }

        return new int[0];
    }
}

---

Time Complexity

Approach	Time Complexity	Space Complexity
Brute Force	O(n²)	O(1)
HashMap Approach	O(n)	O(n)

The HashMap solution is optimal for large datasets.

---

Why This Problem Is Important

The Two Sum problem helps developers understand:

1. Efficient lookup using HashMap

2. Time complexity optimization

3. Array traversal strategies

4. Interview coding patterns

Many advanced problems like:

1. 3Sum

2. 4Sum

3. Subarray Sum

are extensions of this concept.

---

Interview Tips for Two Sum

When solving in interviews:

1. Start with brute-force explanation

2. Then suggest HashMap optimization

3. Explain time complexity clearly

4. Walk through a sample input

This shows strong problem-solving skills.

---

Practice the Problem

You can try this problem directly on:

Official problem page:

https://leetcode.com/problems/two-sum/

Practicing coding problems regularly improves your technical interview success rate.