Input: nums = [-1, 3, 4, 2], target = 3
Output: [0, 2]

In Plain English

New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.

Intuition

A brute force approach is to iterate through every possible pair in the array to see if their sum is equal to the target. This is the same as the brute force solution described in the Pair Sum - Sorted problem, which has a time complexity of $O(n^2)$, where $n$ is the length of the array. We could also sort the array and then perform the two-pointer algorithm used in Pair Sum - Sorted, which would take $O(nlog(n))$ time due to sorting. Let’s see if we can find an even faster solution.

Complement
We're asked to find a pair (x, y) such that x + y == target. In this equation, there are two unknowns: x and y. An important observation is that if we know one of these numbers, we can easily calculate what the other number should be.

For each number x in nums, we need to find another number y such that x + y = target, or in other words, y = target - x. We can call this number the complement of x.

Keep in mind, we need to return the indexes of the pair of numbers, not the pair itself. So, we’ll need a way to find a number's complement as well as its index.

One way we could do this is to loop through the array to find each number’s complement and corresponding index. But this takes $O(n^2)$ time since we’d need to do a linear traversal to search for each number’s complement. Instead, we’d like an efficient way to determine the index of any number in the array without needing to search the array. Is there a data structure that can help with this?

Hash map
A hash map works great because we can store and look up values in $O(1)$ time. Each number and its index can be stored in the hash map as key-value pairs:

This allows us to retrieve the index of any number’s complement efficiently. Notice that duplicate numbers don’t need to be considered here since only one valid pair needs to be found.

The most intuitive way to incorporate a hash map is to:

1. In the first pass, populate the hash map with each number and its corresponding index.

2. In the second pass, scan through the array to check if each number's complement exists in the hash map. If it does, we can return the indexes of that number and its complement.

Below is the code snippet for this two-pass approach:

from typing import List
        
def pair_sum_unsorted_two_pass(nums: List[int], target: int) -> List[int]:
    num_map = {}
    # First pass: Populate the hash map with each number and its index.
    for i, num in enumerate(nums):
        num_map[num] = i
    # Second pass: Check for each number's complement in the hash map.
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map and num_map[complement] != i:
            return [i, num_map[complement]]
    return []

#include <vector>
using namespace std;

vector<int> pairSumUnsortedTwoPass(vector<int>& nums, int target) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {      // every later partner
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }
    return {};
}

// This method lives inside a class, e.g. class Solution { ... }
public int[] pairSumUnsortedTwoPass(int[] nums, int target) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {      // every later partner
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{};
}

This algorithm requires two passes. Is it possible to do this in only one? A one-pass solution implies that we would need to populate the hash map while searching for complements. Is this possible? Consider the example below:

Start at index 0. Its complement would be 3 - (-1) = 4. Does our hash map have 4 in it? No, it's empty at the moment. So, let's add -1 and its index to the hash map:

Next, let’s look at index 1. Its complement (0) does not exist in the hash map. So, just add 3 and its index to the hash map:

At index 2, we notice 4's complement (-1) exists in the hash map. This means we found a pair that sums to the target:

Now, we can return the indexes of the two values. Fetch the index of 4 from the input array and the index of its complement from the hash map:

Implementation

from typing import List
   
def pair_sum_unsorted(nums: List[int], target: int) -> List[int]:
    hashmap = {}
    for i, x in enumerate(nums):
        if target - x in hashmap:
            return [hashmap[target - x], i]
        hashmap[x] = i
    return []

#include <vector>
#include <unordered_map>
using namespace std;

vector<int> pairSumUnsorted(vector<int>& nums, int target) {
    unordered_map<long long, int> seen; // value -> index (64-bit key avoids overflow)
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        long long complement = (long long)target - nums[i];
        if (seen.count(complement)) {
            return {seen[complement], i};  // partner found earlier
        }
        seen[nums[i]] = i;             // remember this number's index
    }
    return {};                         // no pair adds up to target
}

import java.util.*;

// This method lives inside a class, e.g. class Solution { ... }
public int[] pairSumUnsorted(int[] nums, int target) {
    Map<Long, Integer> seen = new HashMap<>();     // value -> index (64-bit key avoids overflow)
    for (int i = 0; i < nums.length; i++) {
        long complement = (long) target - nums[i];
        if (seen.containsKey(complement)) {
            return new int[]{seen.get(complement), i}; // partner found
        }
        seen.put((long) nums[i], i);   // remember this number's index
    }
    return new int[]{};                // no pair adds up to target
}

Complexity Analysis

Time complexity: The time complexity of pair_sum_unsorted is $O(n)$ because we iterate through each element in the nums array once and perform constant-time hash map operations during each iteration.

Space complexity: The space complexity is $O(n)$ since the hash map can grow up to $n$ in size.

Dry Runs

Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.

The same steps in each language

Interview Tip

Tip: Iterate through solutions.
Don’t always jump straight to the most optimal or clever solution, as this won't give the interviewer much insight into your problem-solving process. Consider multiple approaches, starting with the more straightforward ones, and gradually refine them. This way, you demonstrate your thought process and how you arrive at a more optimal solution.