1. Two Sum - Explanation

Description

Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.

You may assume that every input has exactly one pair of indices i and j that satisfy the condition.

Return the answer with the smaller index first.

Example 1:

Input: 
nums = [3,4,5,6], target = 7

Output: [0,1]

Explanation: nums[0] + nums[1] == 7, so we return [0, 1].

Example 2:

Input: nums = [4,5,6], target = 10

Output: [0,2]

Example 3:

Input: nums = [5,5], target = 10

Output: [0,1]

Constraints:

2 <= nums.length <= 1000
-10,000,000 <= nums[i] <= 10,000,000
-10,000,000 <= target <= 10,000,000
Only one valid answer exists.

Topics

Array Hash Table

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Hint 1

A brute force solution would be to check every pair of numbers in the array. This would be an O(n^2) solution. Can you think of a better way? Maybe in terms of mathematical equation?

Hint 2

Given, We need to find indices i and j such that i != j and nums[i] + nums[j] == target. Can you rearrange the equation and try to fix any index to iterate on?

Hint 3

we can iterate through nums with index i. Let difference = target - nums[i] and check if difference exists in the hash map as we iterate through the array, else store the current element in the hashmap with its index and continue. We use a hashmap for O(1) lookups.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash Maps - Using dictionaries to store values and their indices for O(1) lookup of complements
Two Pointers technique - Understanding how sorting enables the two-pointer approach for finding pairs
Array traversal - Iterating through arrays while tracking indices and values

1. Brute Force

Intuition

We can check every pair of different elements in the array and return the first pair that sums up to the target. This is the most intuitive approach but it's not the most efficient.

Algorithm

Iterate through the array with two nested loops using indices i and j to check every pair of different elements.
If the sum of the pair equals the target, return the indices of the pair.
If no such pair is found, return an empty array.
There is guaranteed to be exactly one solution, so we will never return an empty array.

Example - Dry Run

Input: nums = [2, 7, 11, 15], target = 9

┌─────┬─────┬─────┬─────┐
│  2  │  7  │ 11  │ 15  │
└─────┴─────┴─────┴─────┘
   0     1     2     3    ← indices

We check every pair of elements using two nested loops.

Step 1: i = 0, j = 1

   i     j
   ↓     ↓
┌─────┬─────┬─────┬─────┐
│  2  │  7  │ 11  │ 15  │
└─────┴─────┴─────┴─────┘

Check: nums[0] + nums[1] = 2 + 7 = 9 == target ✓

Match found! Return [0, 1]

Visualization of all pairs (if no early match):

┌──────────┬─────────────┬────────────┐
│   Pair   │ Calculation │   Result   │
├──────────┼─────────────┼────────────┤
│  (0, 1)  │   2 +  7    │   9  ✓     │ ← Found!
│  (0, 2)  │   2 + 11    │  13        │
│  (0, 3)  │   2 + 15    │  17        │
│  (1, 2)  │   7 + 11    │  18        │
│  (1, 3)  │   7 + 15    │  22        │
│  (2, 3)  │  11 + 15    │  26        │
└──────────┴─────────────┴────────────┘

Result: [0, 1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    twoSum(nums, target) {
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] === target) {
                    return [i, j];
                }
            }
        }
        return [];
    }
}

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        for (int i = 0; i < nums.Length; i++) {
            for (int j = i + 1; j < nums.Length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        for (i in nums.indices) {
            for (j in i + 1 until nums.size) {
                if (nums[i] + nums[j] == target) {
                    return intArrayOf(i, j)
                }
            }
        }
        return intArrayOf()
    }
}

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for i in 0..<nums.count {
            for j in (i + 1)..<nums.count {
                if nums[i] + nums[j] == target {
                    return [i, j]
                }
            }
        }
        return []
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Sorting

Intuition

We can sort the array and use two pointers to find the two numbers that sum up to the target. This is more efficient than the brute force approach. This approach is similar to the one used in Two Sum II.

Algorithm

Create a copy of the array and sort it in ascending order.
Initialize two pointers, one at the beginning (i) and one at the end (j) of the array.
Iterate through the array with the two pointers and check if the sum of the two numbers is equal to the target.
If the sum is equal to the target, return the indices of the two numbers.
If the sum is less than the target, move the left pointer i to the right, which will increase the sum.
If the sum is greater than the target, move the right pointer j to the left, which will decrease the sum.
There is guaranteed to be exactly one solution, so we will never return an empty array.

Example - Dry Run

Input: nums = [2, 7, 11, 15], target = 9

┌─────┬─────┬─────┬─────┐
│  2  │  7  │ 11  │ 15  │
└─────┴─────┴─────┴─────┘
   0     1     2     3    ← indices

Initial State: Create array with (value, original_index) pairs

A = [(2, 0), (7, 1), (11, 2), (15, 3)]

After Sorting: (already sorted in this case)

        i                       j
        ↓                       ↓
┌───────────┬───────────┬───────────┬───────────┐
│  (2, 0)   │  (7, 1)   │ (11, 2)   │ (15, 3)   │
└───────────┴───────────┴───────────┴───────────┘
   val=2       val=7      val=11      val=15

Step 1: i = 0, j = 3

        i                       j
        ↓                       ↓
┌───────────┬───────────┬───────────┬───────────┐
│  (2, 0)   │  (7, 1)   │ (11, 2)   │ (15, 3)   │
└───────────┴───────────┴───────────┴───────────┘

Sum = 2 + 15 = 17 > 9 (target)
Action: Move j left (decrease sum) ←

Step 2: i = 0, j = 2

        i               j
        ↓               ↓
┌───────────┬───────────┬───────────┬───────────┐
│  (2, 0)   │  (7, 1)   │ (11, 2)   │ (15, 3)   │
└───────────┴───────────┴───────────┴───────────┘

Sum = 2 + 11 = 13 > 9 (target)
Action: Move j left (decrease sum) ←

Step 3: i = 0, j = 1

        i       j
        ↓       ↓
┌───────────┬───────────┬───────────┬───────────┐
│  (2, 0)   │  (7, 1)   │ (11, 2)   │ (15, 3)   │
└───────────┴───────────┴───────────┴───────────┘

Sum = 2 + 7 = 9 == target ✓

Match found! Original indices are 0 and 1.

Result: [0, 1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        A = []
        for i, num in enumerate(nums):
            A.append([num, i])

        A.sort()
        i, j = 0, len(nums) - 1
        while i < j:
            cur = A[i][0] + A[j][0]
            if cur == target:
                return [min(A[i][1], A[j][1]),
                        max(A[i][1], A[j][1])]
            elif cur < target:
                i += 1
            else:
                j -= 1
        return []

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int, int>> A;
        for (int i = 0; i < nums.size(); i++) {
            A.push_back({nums[i], i});
        }

        sort(A.begin(), A.end());

        int i = 0, j = nums.size() - 1;
        while (i < j) {
            int cur = A[i].first + A[j].first;
            if (cur == target) {
                return {min(A[i].second, A[j].second),
                        max(A[i].second, A[j].second)};
            } else if (cur < target) {
                i++;
            } else {
                j--;
            }
        }
        return {};
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    twoSum(nums, target) {
        let A = [];
        for (let i = 0; i < nums.length; i++) {
            A.push([nums[i], i]);
        }

        A.sort((a, b) => a[0] - b[0]);

        let i = 0,
            j = nums.length - 1;
        while (i < j) {
            let cur = A[i][0] + A[j][0];
            if (cur === target) {
                return [Math.min(A[i][1], A[j][1]), Math.max(A[i][1], A[j][1])];
            } else if (cur < target) {
                i++;
            } else {
                j--;
            }
        }
        return [];
    }
}

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        List<int[]> A = new List<int[]>();
        for (int idx = 0; idx < nums.Length; idx++) {
            A.Add(new int[]{nums[idx], idx});
        }

        A.Sort((a, b) => a[0].CompareTo(b[0]));

        int i = 0, j = nums.Length - 1;
        while (i < j) {
            int cur = A[i][0] + A[j][0];
            if (cur == target) {
                return new int[]{
                    Math.Min(A[i][1], A[j][1]),
                    Math.Max(A[i][1], A[j][1])
                };
            } else if (cur < target) {
                i++;
            } else {
                j--;
            }
        }
        return new int[0];
    }
}

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val A = nums.mapIndexed { index, num -> num to index }.toMutableList()
        A.sortBy { it.first }

        var i = 0
        var j = nums.size - 1
        while (i < j) {
            val cur = A[i].first + A[j].first
            if (cur == target) {
                return intArrayOf(
                    minOf(A[i].second, A[j].second),
                    maxOf(A[i].second, A[j].second)
                )
            } else if (cur < target) {
                i++
            } else {
                j--
            }
        }
        return intArrayOf()
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Hash Map (Two Pass)

Intuition

We can use a hash map to store the value and index of each element in the array. Then, we can iterate through the array and check if the complement of the current element exists in the hash map. The complement must be at a different index, because we can't use the same element twice.

By using a hashmap, we can achieve a time complexity of O(n) because the insertion and lookup time of a hashmap is O(1).

Algorithm

Create a hash map to store the value and index of each element in the array.
Iterate through the array and compute the complement of the current element, which is target - nums[i].
Check if the complement exists in the hash map.
If it does, return the indices of the current element and its complement.
If no such pair is found, return an empty array.

Example - Dry Run

Input: nums = [2, 7, 11, 15], target = 9

┌─────┬─────┬─────┬─────┐
│  2  │  7  │ 11  │ 15  │
└─────┴─────┴─────┴─────┘
   0     1     2     3    ← indices

Pass 1: Build the HashMap

Iteration 0: indices[2]  = 0
Iteration 1: indices[7]  = 1
Iteration 2: indices[11] = 2
Iteration 3: indices[15] = 3

HashMap after Pass 1:

┌───────┬───────┐
│ Value │ Index │
├───────┼───────┤
│   2   │   0   │
│   7   │   1   │
│  11   │   2   │
│  15   │   3   │
└───────┴───────┘

Pass 2: Find the complement

Step 1: i = 0, nums[0] = 2

   i
   ↓
┌─────┬─────┬─────┬─────┐
│  2  │  7  │ 11  │ 15  │
└─────┴─────┴─────┴─────┘

diff = target - nums[0] = 9 - 2 = 7

Check: Is 7 in HashMap?      → YES, at index 1
Check: Is index 1 != index 0? → YES ✓

Match found! Return [0, 1]

Result: [0, 1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        indices = {}  # val -> index

        for i, n in enumerate(nums):
            indices[n] = i

        for i, n in enumerate(nums):
            diff = target - n
            if diff in indices and indices[diff] != i:
                return [i, indices[diff]]
        return []

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indices = new HashMap<>();  // val -> index

        for (int i = 0; i < nums.length; i++) {
            indices.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (indices.containsKey(diff) && indices.get(diff) != i) {
                return new int[]{i, indices.get(diff)};
            }
        }

        return new int[0];
    }
}

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> indices;  // val -> index

        for (int i = 0; i < nums.size(); i++) {
            indices[nums[i]] = i;
        }

        for (int i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];
            if (indices.count(diff) && indices[diff] != i) {
                return {i, indices[diff]};
            }
        }

        return {};
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    twoSum(nums, target) {
        const indices = {}; // val -> index

        for (let i = 0; i < nums.length; i++) {
            indices[nums[i]] = i;
        }

        for (let i = 0; i < nums.length; i++) {
            let diff = target - nums[i];
            if (indices[diff] !== undefined && indices[diff] !== i) {
                return [i, indices[diff]];
            }
        }

        return [];
    }
}

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        // val -> index
        Dictionary<int, int> indices = new Dictionary<int, int>();

        for (int i = 0; i < nums.Length; i++) {
            indices[nums[i]] = i;
        }

        for (int i = 0; i < nums.Length; i++) {
            int diff = target - nums[i];
            if (indices.ContainsKey(diff) && indices[diff] != i) {
                return new int[]{i, indices[diff]};
            }
        }

        return new int[0];
    }
}

func twoSum(nums []int, target int) []int {
    indices := make(map[int]int)

    for i, n := range nums {
        indices[n] = i
    }

    for i, n := range nums {
        diff := target - n
        if j, found := indices[diff]; found && j != i {
            return []int{i, j}
        }
    }
    return []int{}
}

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val indices = HashMap<Int, Int>()

        for ((i, n) in nums.withIndex()) {
            indices[n] = i
        }

        for ((i, n) in nums.withIndex()) {
            val diff = target - n
            if (indices.containsKey(diff) && indices[diff] != i) {
                return intArrayOf(i, indices[diff]!!)
            }
        }
        return intArrayOf()
    }
}

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var indices = [Int: Int]() // val -> index

        for (i, n) in nums.enumerated() {
            indices[n] = i
        }

        for (i, n) in nums.enumerated() {
            let diff = target - n
            if let j = indices[diff], j != i {
                return [i, j]
            }
        }

        return []
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Hash Map (One Pass)

Intuition

We can solve the problem in a single pass by iterating through the array and checking if the complement of the current element exists in the hash map.

If it does, we return the indices of the current element and its complement. If not, we store the current element in the hash map. This guarantees that we will never use the same element twice, but we still check every element in the array.

Algorithm

Create a hash map to store the value and index of each element in the array.
Iterate through the array using index i and compute the complement of the current element, which is target - nums[i].
Check if the complement exists in the hash map.
If it does, return the indices of the current element and its complement.
If no such pair is found, return an empty array.

Example - Dry Run

Input: nums = [2, 7, 11, 15], target = 9

┌─────┬─────┬─────┬─────┐
│  2  │  7  │ 11  │ 15  │
└─────┴─────┴─────┴─────┘
   0     1     2     3    ← indices

We iterate through the array once, checking for complement and building the HashMap simultaneously.

Step 1: i = 0, nums[0] = 2

   i
   ↓
┌─────┬─────┬─────┬─────┐
│  2  │  7  │ 11  │ 15  │
└─────┴─────┴─────┴─────┘

diff = target - nums[0] = 9 - 2 = 7

HashMap (before):
┌───────┬───────┐
│  Key  │ Value │
├───────┼───────┤
│   -   │   -   │
└───────┴───────┘

Check: Is 7 in HashMap? → NO
Action: Add 2 → 0 to HashMap

HashMap (after):
┌───────┬───────┐
│  Key  │ Value │
├───────┼───────┤
│   2   │   0   │
└───────┴───────┘

Step 2: i = 1, nums[1] = 7

         i
         ↓
┌─────┬─────┬─────┬─────┐
│  2  │  7  │ 11  │ 15  │
└─────┴─────┴─────┴─────┘

diff = target - nums[1] = 9 - 7 = 2

HashMap:
┌───────┬───────┐
│  Key  │ Value │
├───────┼───────┤
│   2   │   0   │
└───────┴───────┘

Check: Is 2 in HashMap? → YES, at index 0 ✓

Match found! Return [0, 1]

Visual Summary:

┌──────┬─────────┬──────┬─────────────────┬──────────────────┐
│ Step │ nums[i] │ diff │ HashMap Before  │ Action           │
├──────┼─────────┼──────┼─────────────────┼──────────────────┤
│  0   │    2    │   7  │ {}              │ Add {2: 0}       │
│  1   │    7    │   2  │ {2: 0}          │ Found! Return ✓  │
└──────┴─────────┴──────┴─────────────────┴──────────────────┘

Result: [0, 1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}  # val -> index

        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> prevMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int diff = target - num;

            if (prevMap.containsKey(diff)) {
                return new int[] { prevMap.get(diff), i };
            }

            prevMap.put(num, i);
        }

        return new int[] {};
    }
}

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int, int> prevMap;

        for (int i = 0; i < n; i++) {
            int diff = target - nums[i];
            if (prevMap.find(diff) != prevMap.end()) {
                return {prevMap[diff], i};
            }
            prevMap.insert({nums[i], i});
        }
        return {};
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    twoSum(nums, target) {
        const prevMap = new Map();

        for (let i = 0; i < nums.length; i++) {
            const diff = target - nums[i];
            if (prevMap.has(diff)) {
                return [prevMap.get(diff), i];
            }

            prevMap.set(nums[i], i);
        }

        return [];
    }
}

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> prevMap = new Dictionary<int, int>();

        for (int i = 0; i < nums.Length; i++) {
            var diff = target - nums[i];
            if (prevMap.ContainsKey(diff)) {
                return new int[] {prevMap[diff], i};
            }
            prevMap[nums[i]] = i;
        }
        return null;
    }
}

func twoSum(nums []int, target int) []int {
    prevMap := make(map[int]int)

    for i, n := range nums {
        diff := target - n
        if j, found := prevMap[diff]; found {
            return []int{j, i}
        }
        prevMap[n] = i
    }
    return []int{}
}

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val prevMap = HashMap<Int, Int>()

        for ((i, n) in nums.withIndex()) {
            val diff = target - n
            if (prevMap.containsKey(diff)) {
                return intArrayOf(prevMap[diff]!!, i)
            }
            prevMap[n] = i
        }
        return intArrayOf()
    }
}

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var prevMap = [Int: Int]() // val -> index

        for (i, n) in nums.enumerated() {
            let diff = target - n
            if let index = prevMap[diff] {
                return [index, i]
            }
            prevMap[n] = i
        }

        return []
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Using the Same Element Twice

You cannot use the same element twice to form a pair. When using a hash map, ensure you check that the found index differs from the current index, or use one-pass where you only look at previously seen elements.

# Wrong: might return [i, i] when nums[i] * 2 == target
if diff in indices:
    return [i, indices[diff]]
# Correct: ensure different indices
if diff in indices and indices[diff] != i:
    return [i, indices[diff]]

Returning Values Instead of Indices

The problem asks for indices, not the values themselves. A common mistake is returning the two numbers that sum to the target rather than their positions in the array.

Handling Duplicate Values

When building a hash map with values as keys, duplicate values overwrite earlier indices. In the two-pass approach, this still works because you check indices[diff] != i. In the one-pass approach, you check for the complement before inserting the current element.

Wrong Complement Calculation

The complement should be target - nums[i], not nums[i] - target. Getting this backwards will search for the wrong value.