Two Sum Problem | HashMap | Two sum Interviewbit | leetcode two sum

Introduction:
The “Two Sum” problem is a popular coding interview question where you are given an array of integers and a target sum. The task is to find two numbers in the array that add up to the target sum and return their indices. One efficient approach to solving this problem involves using a HashMap to store the elements of the array along with their indices. In this blog post, we will discuss how to solve the Two Sum problem using HashMap in the Java programming language.

Problem Statement:

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

Approach using HashMap:

1. Create an empty HashMap to store the elements and their indices.
2. Loop through each element num and index i in the array nums.
3. Calculate the difference diff between the target and the current element num.
4. Check if the diff is present in the HashMap. If yes, return the indices [hashMap.get(diff), i].
5. Otherwise, put the current element num and its index i in the HashMap.

Java Code Implementation:

import java.util.*;

public class TwoSumHashMap {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (hashMap.containsKey(diff)) {
                return new int[]{hashMap.get(diff), i};
            }
            hashMap.put(nums[i], i);
        }
        throw new IllegalArgumentException("No solution found.");
    }

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

Explanation:

In this example, the array nums contains elements [2, 7, 11, 15] and the target sum is 9. The solution method twoSum uses a HashMap to store the elements encountered so far and their indices. During the loop, when i is 0, the current element is 2, and the difference diff is 7. Since 7 is not present in the HashMap, we add 2 to the HashMap with its index 0.

When i is 1, the current element is 7, and the difference diff is 2. Now, since 2 is present in the HashMap, we know that the pair [2, 7] adds up to the target 9, and we return the indices [0, 1].

Conclusion:

Using a HashMap to solve the Two Sum problem provides an efficient solution with a time complexity of O(n), where n is the number of elements in the input array. This approach showcases the power of data structures in solving common coding interview questions.