# Two Sum Problem: How to Solve It Efficiently with a HashMap in Java

> Learn to solve the Two Sum problem in O(n) time using a Java HashMap. Discover an efficient algorithm for finding two numbers that add up to a target value.

- Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews)
- Tags: how-to-guide
- Published: 2026-03-04

---

**You can solve the Two Sum problem in O(n) time by iterating once through the array and storing each number in a HashMap, checking if the complement (target - current number) already exists in the map before inserting the current index.**

The Two Sum problem is a fundamental algorithmic challenge that appears in coding interviews at major tech companies. According to the kdn251/interviews repository, an optimal Java solution leverages a HashMap to achieve linear time complexity. This approach trades O(n) extra space for a significant speedup over the brute-force method.

## Understanding the Two Sum Problem

The Two Sum problem requires finding two indices in an integer array whose values sum to a specific target. Given an array `nums` and an integer `target`, you must return the indices of the two numbers such that they add up to `target`.

Each input guarantees exactly one solution, and you cannot use the same element twice. For example, given `nums = [2, 7, 11, 15]` and `target = 9`, the correct output is `[0, 1]` because `nums[0] + nums[1] = 2 + 7 = 9`.

## Why the HashMap Approach Beats the Naïve Solution

A brute-force solution checks every pair of numbers using nested loops, resulting in **O(n²)** time complexity and **O(1)** space. The optimal approach uses a **HashMap** to store values and indices during a single pass:

1. **Compute the complement**: For each `nums[i]`, calculate `target - nums[i]`.
2. **Check the map**: If the complement exists as a key in the HashMap, you have found the matching pair.
3. **Store current value**: If not found, insert `nums[i]` with its index `i` into the map.

Because HashMap operations (`containsKey`, `get`, `put`) run in **amortized O(1)** time, the entire algorithm achieves **O(n) time** and **O(n) space** complexity.

## Implementation in the kdn251/interviews Repository

The kdn251/interviews repository provides a clean implementation across multiple packages. The core logic resides in files such as [`leetcode/hash-table/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/leetcode/hash-table/TwoSum.java), [`company/uber/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/company/uber/TwoSum.java), and [`company/facebook/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/company/facebook/TwoSum.java).

In [`leetcode/hash-table/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/leetcode/hash-table/TwoSum.java), the `twoSum` method creates a `HashMap<Integer, Integer>` where the **key** stores the array value and the **value** stores its index. The method iterates through the input array once:

```java
public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];
    HashMap<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i])) {
            result[1] = i;
            result[0] = map.get(target - nums[i]);
            return result;
        }
        map.put(nums[i], i);
    }
    return result;
}

```

The algorithm returns immediately upon finding the complement, ensuring minimal computation. The repository duplicates this implementation in company-specific packages (e.g., [`company/linkedin/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/company/linkedin/TwoSum.java), [`company/amazon/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/company/amazon/TwoSum.java), [`company/airbnb/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/company/airbnb/TwoSum.java)) to demonstrate its universal applicability across interview contexts.

## Practical Java Code Examples

### Basic Usage

The following example demonstrates instantiating the solver and finding indices for a standard input:

```java
public class Demo {
    public static void main(String[] args) {
        TwoSum solver = new TwoSum();
        int[] nums = {2, 7, 11, 15};
        int target = 9;

        int[] indices = solver.twoSum(nums, target);
        System.out.printf("Indices: [%d, %d]%n", indices[0], indices[1]);
        // Output: Indices: [0, 1]
    }
}

```

### Handling Large Inputs

The HashMap solution maintains O(n) performance even with 100,000 elements:

```java
int[] largeArray = new int[100_000];
for (int i = 0; i < largeArray.length; i++) {
    largeArray[i] = i * 2;
}
int target = 199_998;
int[] result = new TwoSum().twoSum(largeArray, target);
// Returns [99998, 99999] in linear time

```

### JUnit Test Validation

You can verify the implementation using standard unit tests:

```java
import static org.junit.Assert.*;
import org.junit.Test;

public class TwoSumTest {
    @Test
    public void testExample() {
        int[] nums = {2, 7, 11, 15};
        int[] expected = {0, 1};
        assertArrayEquals(expected, new TwoSum().twoSum(nums, 9));
    }

    @Test
    public void testNegativeNumbers() {
        int[] nums = {-3, 4, 3, 90};
        int[] expected = {0, 2};
        assertArrayEquals(expected, new TwoSum().twoSum(nums, 0));
    }
}

```

## Summary

- The **Two Sum problem** requires finding two indices whose values sum to a target.
- The **HashMap approach** achieves **O(n) time** by storing values during a single iteration and checking for the complement.
- The **kdn251/interviews** repository implements this solution in [`leetcode/hash-table/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/leetcode/hash-table/TwoSum.java) and multiple company-specific packages.
- HashMap operations provide **amortized O(1)** lookups, making this the standard optimal solution for interviews.
- The implementation handles edge cases including negative numbers and large arrays efficiently.

## Frequently Asked Questions

### What is the time complexity of the Two Sum HashMap solution?

The HashMap solution runs in **O(n)** time where n is the length of the input array. Each iteration performs constant-time HashMap operations (`containsKey`, `get`, and `put`), resulting in a single linear pass through the data.

### Can I solve Two Sum without extra space?

Yes, but with a trade-off. You can sort the array first and use two pointers to find the pair in **O(n log n)** time with **O(1)** extra space. However, sorting destroys the original indices, so you must track positions separately if the problem requires returning original indices.

### What if the array contains duplicate values?

The HashMap solution handles duplicates correctly because it stores the most recent index for each value. If the complement is found in the map, the algorithm returns immediately before overwriting the index, ensuring you never use the same element twice.

### Where can I find the source code in the kdn251/interviews repository?

The primary implementation is located at [`leetcode/hash-table/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/leetcode/hash-table/TwoSum.java). Additional variants appear in [`company/uber/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/company/uber/TwoSum.java), [`company/linkedin/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/company/linkedin/TwoSum.java), [`company/facebook/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/company/facebook/TwoSum.java), [`company/amazon/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/company/amazon/TwoSum.java), and [`company/airbnb/TwoSum.java`](https://github.com/kdn251/interviews/blob/main/company/airbnb/TwoSum.java), all demonstrating the same core algorithm.