LeetCode TwoSum Problem Solution In Java Using Hash Map | Easy Level

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

Example:

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

Approach Using a Map (HashMap)

The most efficient way to solve this problem is by using a map to store numbers and their indices while iterating through the array. This allows you to check in constant time whether the complement of the current number (the number needed to reach the target) has already been encountered.

Steps

1. Initialize a map: Create an empty map (hash table) to store numbers and their corresponding indices.
2. Iterate through the array: Loop through each number in the array.
3. Check for complement: For the current number num, compute the complement target - num. Check if this complement is already in the map.
   • If it is, you have found the two numbers that add up to the target. Return their indices.
   • If it is not, store the current number in the map with its index as the value.
4. Continue the loop: If you don't find a match in the current iteration, move to the next number.

Code Implementation:

import java.util.HashMap;

import java.util.Map;

public class TwoSum {

public static void main(String[] args) {

int[] arr = {2,7,4,9,0,1};

int[] res = findTwoSum(arr, 8);

if (res.length==0) {

System.out.println("no result found!");

}

else {

System.out.println("indices found at ["+res[0]+", "+res[1]+"]");

}

}

public static int[] findTwoSum(int[] arr, int target) {

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

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

int comp = target - arr[i];

if (map.containsKey(comp)) {

return new int[] {map.get(comp), i};

}

map.put(arr[i], i);

}

return new int[] {};

}

}

Output:

indices found at [1, 5]

Explanation:

Initialize an empty map: num_map = {}

1. First iteration (index = 0, num = 2):
   • Complement = 9 - 2 = 7
   • 7 is not in the map, so add 2 to the map: num_map = {2: 0}
2. Second iteration (index = 1, num = 7):
   • Complement = 9 - 7 = 2
   • 2 is in the map (num_map = {2: 0}), so the solution is [0, 1].

Time Complexity

• O(n): We iterate through the list only once.
• Space Complexity: O(n) for storing elements in the map.

This approach is more efficient than a brute-force solution with a nested loop,

which would have a time complexity of O(n²).

🚀 New Video Alert! 🚀

Learn how to solve the Two Sum problem on LeetCode using HashMap! Perfect for coding interviews & improving problem-solving skills. Watch now and don't forget to LIKE, SHARE, & SUBSCRIBE for more tutorials!

👉 Watch Here: