In this tutorial, I will demonstrate how to solve the Two Sum problem in Java. This is one of the most popular array-based coding interview questions and helps you understand array traversal, HashMap, and efficient element lookup.
The Two Sum problem asks you to find two numbers in an array whose sum equals a given target. Instead of returning only the numbers, the standard version of this problem requires returning their indexes.
For example, consider the array [2, 7, 11, 15] with a target of 9. The numbers 2 and 7 add up to 9, so the expected result is [0, 1], representing their indexes.
You can solve this problem using nested loops, but that approach takes quadratic time. A more efficient solution uses HashMap to find matching numbers in linear time.
In this tutorial, you will learn the Two Sum problem using HashMap, a brute-force alternative, a step-by-step dry run, time and space complexity analysis, and important edge cases.
1. Problem Statement
Given an array of integers and a target value, find the indexes of two different elements whose sum equals the target.
Requirements:
- Return the indexes of the two elements.
- Do not use the same array element twice.
- The two elements must add up to the target.
- If no valid pair exists, return an empty array.
Some interview versions guarantee exactly one valid solution. The implementations in this tutorial also handle cases where no solution exists.
Example 1
Input: nums = [2, 7, 11, 15] target = 9 Output: [0, 1]
Explanation:
nums[0] = 2 nums[1] = 7 2 + 7 = 9
Since the sum matches the target, the answer is [0, 1].
Example 2
Input: nums = [3, 2, 4] target = 6 Output: [1, 2]
The numbers at indexes 1 and 2 are 2 and 4, and their sum is 6.
Example 3
Input: nums = [3, 3] target = 6 Output: [0, 1]
Both values are equal, but they occupy different indexes, so they form a valid pair.
2. Method 1: Solve Two Sum Using HashMap
The HashMap approach is the recommended solution for the Two Sum problem.
A HashMap stores key-value pairs. In this algorithm, each previously visited number is stored as a key, and its array index is stored as the value.
For every current number, the algorithm calculates the value needed to reach the target.
This required value is called the complement.
Understanding the Complement
The mathematical relationship is:
firstNumber + secondNumber = target secondNumber = target - firstNumber
Therefore:
complement = target - currentNumber
For example, if the target is 9 and the current number is 7:
complement = 9 - 7 complement = 2
The algorithm checks whether 2 has already appeared in the array.
If it has, the matching pair has been found.
How the HashMap Algorithm Works
- Create an empty HashMap to store numbers and their indexes.
- Iterate through the array.
- Calculate the complement for the current number.
- Check whether the complement exists in the HashMap.
- If it exists, return the stored index and the current index.
- Otherwise, store the current number and its index.
- If the loop finishes without finding a pair, return an empty array.
Java Program Using HashMap
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class TwoSumUsingHashMap {
/**
* Finds the indexes of two numbers
* whose sum equals the target.
*
* @param nums input integer array
* @param target required sum
* @return array containing two indexes,
* or an empty array if no pair exists
*/
public static int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return new int[0];
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// Calculate complement using long to avoid overflow
long complement = (long) target - nums[i];
// Check whether complement is in the int range
if (complement >= Integer.MIN_VALUE
&& complement <= Integer.MAX_VALUE) {
Integer previousIndex =
map.get((int) complement);
if (previousIndex != null) {
return new int[]{previousIndex, i};
}
}
// Store current number and its index
map.put(nums[i], i);
}
// No pair found
return new int[0];
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
System.out.println("Array: " + Arrays.toString(nums));
System.out.println("Target: " + target);
System.out.println("Result Indexes: "
+ Arrays.toString(result));
if (result.length == 2) {
System.out.println("Matching Numbers: "
+ nums[result[0]] + " and " + nums[result[1]]);
} else {
System.out.println("No valid pair found");
}
}
}Output
Array: [2, 7, 11, 15] Target: 9 Result Indexes: [0, 1] Matching Numbers: 2 and 7
This solution processes the array only once and uses HashMap to find previously visited elements efficiently.
3. Step-by-Step Explanation of the HashMap Solution
Step 1: Validate the Input
if (nums == null || nums.length < 2) {
return new int[0];
}At least two elements are required to form a pair.
If the array is null or contains fewer than two elements, the method returns an empty array.
Step 2: Create a HashMap
Map<Integer, Integer> map = new HashMap<>();The HashMap stores previously visited numbers as keys and their indexes as values.
For example, after processing the number 2 at index 0, the map contains:
Key = 2 Value = 0
Step 3: Traverse the Array
for (int i = 0; i < nums.length; i++) {The loop visits each array element from left to right.
Step 4: Calculate the Complement
long complement = (long) target - nums[i];The complement is the number required to reach the target.
For example, if the target is 9 and the current number is 7, the complement is 2.
The program uses a long for the calculation to prevent integer overflow when subtracting extreme int values.
Step 5: Search for the Complement
Integer previousIndex =
map.get((int) complement);Once the complement has been verified to be within the int range, the program searches the HashMap for it.
If the complement was previously stored, get() returns its index.
Otherwise, it returns null.
Step 6: Return the Matching Indexes
if (previousIndex != null) {
return new int[]{previousIndex, i};
}If a complement is found, the program returns two indexes:
- The index of the previously visited complement.
- The index of the current number.
The program returns immediately because it has found a valid pair.
Step 7: Store the Current Number
map.put(nums[i], i);If the complement was not found, the program stores the current number and its index.
This allows future elements to match with it.
Important: The program checks for the complement before inserting the current element. This prevents the algorithm from using the same array element twice.
4. Dry Run: Two Sum Using HashMap
Consider the following input:
Array: [2, 7, 11, 15] Target: 9
The algorithm begins with an empty HashMap.
| Iteration | Index | Number | Complement | Map Before Lookup | Action |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 7 | {} | Store 2 at index 0 |
| 2 | 1 | 7 | 2 | {2=0} | Pair found: [0, 1] |
Iteration 1
The current number is 2.
The complement is:
9 - 2 = 7
The HashMap is empty, so 7 is not found.
The program stores the number 2 with index 0.
Iteration 2
The current number is 7.
The complement is:
9 - 7 = 2
The HashMap already contains 2 at index 0.
The algorithm returns indexes 0 and 1.
Final result:
[0, 1]
5. Method 2: Two Sum Using Brute Force
The brute-force approach uses two nested loops to examine every possible pair of elements.
For each element, the algorithm compares it with the elements that appear after it.
If the sum equals the target, the method returns the two indexes.
Java Program Using Nested Loops
import java.util.Arrays;
public class TwoSumBruteForce {
public static int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return new int[0];
}
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
// Use long to prevent integer overflow
long sum = (long) nums[i] + nums[j];
if (sum == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
public static void main(String[] args) {
int[] nums = {3, 2, 4};
int target = 6;
int[] result = twoSum(nums, target);
System.out.println("Array: " + Arrays.toString(nums));
System.out.println("Target: " + target);
System.out.println("Result Indexes: "
+ Arrays.toString(result));
}
}Output
Array: [3, 2, 4] Target: 6 Result Indexes: [1, 2]
How Brute Force Works
- Select the first element using the outer loop.
- Compare it with every subsequent element using the inner loop.
- Calculate the sum of the selected pair.
- If the sum equals the target, return both indexes.
- Continue until a pair is found or all pairs have been checked.
This approach is easy to understand, but it performs unnecessary comparisons for large arrays.
6. Method 3: Two Sum Using Two Pointers on a Sorted Array
If the input array is already sorted in ascending order, you can solve the Two Sum problem using two pointers.
One pointer starts at the beginning of the array, while the other starts at the end.
The algorithm compares the sum of the two values with the target.
- If the sum equals the target, return the indexes.
- If the sum is smaller, move the left pointer forward.
- If the sum is larger, move the right pointer backward.
This approach requires constant auxiliary space and linear time when the input array is already sorted.
Java Program Using Two Pointers
import java.util.Arrays;
public class TwoSumSortedArray {
public static int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length < 2) {
return new int[0];
}
int left = 0;
int right = nums.length - 1;
while (left < right) {
long sum = (long) nums[left] + nums[right];
if (sum == target) {
return new int[]{left, right};
}
if (sum < target) {
left++;
} else {
right--;
}
}
return new int[0];
}
public static void main(String[] args) {
int[] nums = {1, 2, 4, 6, 8, 10};
int target = 12;
int[] result = twoSum(nums, target);
System.out.println("Sorted Array: "
+ Arrays.toString(nums));
System.out.println("Target: " + target);
System.out.println("Result Indexes: "
+ Arrays.toString(result));
}
}Output
Sorted Array: [1, 2, 4, 6, 8, 10] Target: 12 Result Indexes: [1, 5]
The elements at indexes 1 and 5 are 2 and 10, and their sum is 12.
Important: This method assumes the array is already sorted. Sorting an unsorted input array would change its indexes, so you cannot directly return indexes from a newly sorted array when the problem requires positions from the original input.
7. Time and Space Complexity
Let's compare the three approaches.
| Approach | Time Complexity | Auxiliary Space | Requirement |
|---|---|---|---|
| HashMap | O(n) expected | O(n) | Works with unsorted arrays |
| Brute Force | O(n²) | O(1) | Works with unsorted arrays |
| Two Pointers | O(n) | O(1) | Requires sorted array |
Here, n represents the number of elements in the array.
HashMap Approach: O(n) Expected Time
The HashMap solution processes each element once.
HashMap lookup and insertion typically take constant time on average.
Therefore, the expected time complexity is O(n).
The map may store up to n elements, so its auxiliary space complexity is O(n).
Brute Force: O(n²) Time
The brute-force approach checks possible pairs using nested loops.
In the worst case, it examines approximately:
n × (n - 1) / 2
pairs.
Therefore, its worst-case time complexity is O(n²).
Two Pointers: O(n) Time
The two-pointer approach moves the left and right pointers toward each other.
Each pointer moves only in one direction, so the algorithm requires at most linear traversal.
It uses constant auxiliary space but requires a sorted input array.
8. Handling Important Edge Cases
Case 1: Empty Array
Input: nums = [] target = 9 Output: []
The program returns an empty array because no pair can be formed.
Case 2: Single Element
Input: nums = [5] target = 10 Output: []
The same array element cannot be used twice.
Case 3: Duplicate Values
Input: nums = [3, 3] target = 6 Output: [0, 1]
The two values are equal but occupy different indexes, so they form a valid pair.
Case 4: Negative Numbers
Input: nums = [-3, 4, 3, 90] target = 0 Output: [0, 2]
The values -3 and 3 add up to zero.
Case 5: No Valid Pair
Input: nums = [1, 2, 3] target = 10 Output: []
The program returns an empty array because no two distinct elements sum to 10.
Case 6: Multiple Valid Pairs
Input: nums = [1, 4, 2, 3] target = 5 Possible Outputs: [0, 1] [2, 3]
Both pairs are mathematically valid.
The HashMap implementation returns the first pair it discovers during its left-to-right traversal. For this input, it returns [0, 1].
Case 7: Integer Overflow
Java int arithmetic has a limited range.
If you add or subtract large integer values without considering overflow, you may get an incorrect result.
The examples use long arithmetic when calculating sums or complements.
This ensures that the mathematical comparison is performed correctly for int inputs.
9. Common Mistakes to Avoid
Mistake 1: Using the Same Element Twice
If the target is 10 and the array contains a single value of 5, you cannot use that element twice to form the sum.
The HashMap solution avoids this mistake by checking for the complement before inserting the current element.
Mistake 2: Returning Values Instead of Indexes
The standard Two Sum problem asks for indexes.
For example:
Input: [2, 7, 11, 15] Target: 9 Correct: [0, 1] Not the required format: [2, 7]
Mistake 3: Using Nested Loops for Large Arrays
The brute-force approach is easy to understand but takes O(n²) time in the worst case.
For large unsorted arrays, HashMap is generally more efficient.
Mistake 4: Sorting the Input Without Preserving Original Indexes
Sorting changes the positions of array elements.
If the problem requires original indexes, do not sort the array and return the new positions.
Use HashMap or preserve original indexes explicitly if you choose a sorting-based solution.
Mistake 5: Ignoring Integer Overflow
The expression target - nums[i] can overflow when both values are int.
Calculating the complement as a long and checking its range prevents incorrect matches.
10. Frequently Asked Questions
Q1. What is the Two Sum problem in Java?
The Two Sum problem asks you to find two different array elements whose sum equals a given target and return their indexes.
Q2. What is the best approach to solve Two Sum in Java?
The HashMap approach is generally the preferred solution for unsorted arrays because it runs in expected O(n) time.
Q3. Why is HashMap used in the Two Sum problem?
HashMap allows efficient lookup of previously visited numbers. It helps the algorithm find the complement needed to reach the target without searching the earlier elements again.
Q4. What is a complement in Two Sum?
The complement is the number needed to reach the target when added to the current number.
complement = target - currentNumber
Q5. Can I use the same array element twice?
No. The standard Two Sum problem requires two distinct indexes.
Q6. What is the time complexity of Two Sum using HashMap?
The expected time complexity is O(n), where n is the number of elements.
Q7. What is the space complexity of Two Sum using HashMap?
The auxiliary space complexity is O(n) because the HashMap may store up to n elements.
Q8. Can Two Sum be solved without HashMap?
Yes. You can use brute force with nested loops or the two-pointer technique when the input is already sorted.
Q9. What happens if no pair exists?
The implementations in this tutorial return an empty array.
Q10. Can Two Sum handle negative numbers and duplicates?
Yes. Both negative numbers and duplicate values are supported. The algorithm checks indexes to ensure two different elements are used.
11. Conclusion
In this tutorial, you learned how to solve the Two Sum problem in Java using three different approaches.
- HashMap: Finds a matching pair in expected
O(n)time using a complement lookup. - Brute Force: Checks every possible pair using nested loops.
- Two Pointers: Finds a matching pair in
O(n)time when the input array is sorted.
For Java coding interviews, I recommend learning the HashMap approach first. It is efficient and demonstrates an important algorithmic pattern: using a lookup structure to avoid repeated comparisons.
Once you understand this technique, practice related problems such as Three Sum, Four Sum, finding pairs with a given difference, and finding subarrays with a target sum.
12. Official Java Documentation
For additional information about the Java APIs used in this tutorial, refer to the official Oracle documentation:
- Java HashMap Class — Documentation for storing and looking up key-value pairs.
- Java Map Interface — Documentation for
get(),put(), andcontainsKey(). - Java Arrays Class — Documentation for
Arrays.toString(). - Java Integer Class — Documentation for
Integer.MIN_VALUEandInteger.MAX_VALUE.
Continue Learning with Java Guides
Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.
By Ramesh Fadatare - Udemy Instructor Partner
Comments
Post a Comment
Leave Comment