Data Structures & Algorithms (HashMap): Two Sum

January 15, 2026

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

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Explanation: Because nums[1] + nums[2] == 6, we return [1, 2].

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 6, we return [0, 1].

Playground: Leetcode 1

General Observations

We need to return the indices of two distinct elements whose sum equals that target. Before diving into the solution, let's consider a few things about the input array.

Q1. Is it guaranteed that there will be exactly one solution?

A. Yes, you can assume there is only one solution.

Note

Why this question is relevant?

If it is guaranteed that there will be exactly one solution, we can immediately return when we find a pair. If there are multiple solutions, the problem might ask us to return all pairs, the first pair closest to the left, or the pair with the smallest index, etc.

Q2. Will the input array be always sorted?

A. No, the input array is not necessarily sorted.

Note

Why this question is relevant?

If the input array is sorted, we can use two pointers to find the pair in O(n) time. However, can cannot use two pointers technique if the input array is not sorted.

Also, we cannot sort the array since sorting the array will change the order of the elements, which will break the problem statement. For example, if the input array is [3, 2, 4] and the target is 6, the output should be [1, 2] but if we sort the array to [2, 3, 4], the output will be [0, 1].

Brute Force Approach (Nested Loops)

Use a nested loop to iterate over all possible pairs and return the first whose sum = target.

Algorithm

1. Run an outer loop to iterate over each integer in the range [0, n-1):
    2. Run an inner loop to iterate over every possible complement integerin the range [i+1, n):
        3. If the sum of two integers is equal to `target`, return the indices of the two integers.
4. If no pair is found, return an empty array.

Implementation

Sample inputs
1public int[] twoSum(int[] nums, int target) {
2 for (int i = 0; i < nums.length; i++) {
3 for (int j = i + 1; j < nums.length; j++) {
4 if (nums[i] + nums[j] == target) {
5 return new int[]{i, j};
6 }
7 }
8 }
9 return new int[]{};
10}
Ready

Press Play or Step to dry-run the nested loops. The highlighted line is the one currently executing.

Target9
2
7
11
15
0
1
2
3
nums[i]+nums[j]9
placeholder
i= —
j= —
sum= —
answer= ?
Pairs checked
None yet
0/4

Time Complexity

In the worst case scenario, the algorithm will explore all n^2 pairs before finding one at [n-2, n-1] indices. Hence, overall time complexity = O(n^2).

Space Complexity

We are not using any extra space. Hence, overall space complexity = O(1).

Optimized Approach (HashMap)

For each integer nums[i], we're really looking for its complement, i.e., target - nums[i]. If we can check quickly whether that complement was seen before, we can avoid the inner loop.

We can iterate over the input array once and use an HashMap (gives average O(1) lookup) to store every component's <value, index>.

Algorithm

1. Run a loop to iterate over each integer in the range [0, n):
    2. Compute the complement of the current integer, i.e., `target - nums[i]`.
    3. Check if the complement is already in the HashMap.
    4. If it is, return the indices of the two integers.
    5. Otherwise, store the current value and index in the HashMap.
6. If no pair is found, return an empty array.
Note

Why check before insert?

To avoid matching the current element with itself and to handle duplicates correctly. For example, if the input array is [3, 3, 4] and the target is 6, the output should be [0, 1] but if we store the current value and index in the HashMap before checking, the output will be [0, 0].

Implementation

Sample inputs
1public int[] twoSum(int[] nums, int target) {
2 Map<Integer, Integer> map = new HashMap<>();
3 for (int i = 0; i < nums.length; i++) {
4 if (map.containsKey(target - nums[i]))
5 return new int[]{i, map.get(target - nums[i])};
6 map.put(nums[i], i);
7 }
8 return new int[]{};
9}
Ready

Press Play or Step to dry-run the HashMap pass. The highlighted line is the one currently executing.

Target9
2
7
11
15
0
1
2
3
need9−nums[i]=?
placeholder
i= —
complement= —
answer= ?
HashMap · value → index
map is empty
0/7

Time Complexity

We iterate through the array once, and each HashMap operation (containsKey, put, get) is O(1) on average. Hence, overall time complexity = O(n).

Space Complexity

In the worst case, all elements are stored in the HashMap. Hence, overall space complexity = O(n).