Problem

You are given an array of n integers and a target sum T. The goal is to determine whether or not there are two numbers x, y in A with x+y=T.

OR

Given an array of integers, find two numbers such that they add up to a specific target number.

Variant: Return the indices instead of the elements in array.

Example

Example 1:

1
2
3
4

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

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Solution

There are three approaches to solve this problem - 1) brute force, 2) sort the array and use binary and search, and 3) Using the hashtable.  Please scroll down, if you are only interested in the best approach i.e. approach 3 using hashtables.

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 : Brute Force Method

The first approach is to use brute force which gives time complexity of O(n^2) and space complexity of O(n). We basically just have to loop through the array and for each number we add it to each of other numbers and see if they sum up to 5. If so, we print out the pair. Here is the code for brute force approach:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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 indices
                }
            }
        }
        return new int[]{-1, -1}; // Return invalid pair if no solution
    }
}
1
2
3
4
5
6
7

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 [-1, -1]  # Return invalid pair if no solution

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Use Sorting and Binary Search

A better way would be to sort the array. This takes O(n log n) Then for each x in array A, use binary search to look for T-x. This will take O(nlogn). So, overall search is  O(n log n)

Complexity

  • ⏰ Time complexity: O(n log n) for sorting and O (n log n) ⇨ O(nlogn)
  • 🧺 Space complexity: O(1)

Pseudocode

Hers is how the pseudo code will look:

1
2
3
4
5
6
7
8

arr = {}; //some array
sortedArr = sort(arr);
for (i = 0; i < arr.length - 1; i++) {
    x = arr[i];
    bool found = binarySearch(sortedArr, T - x); //Search for T-x in sorted Arrary
    if (found)
        print "pair", x, T - x;
}

Problem with above approach is, what if x = T/2, then we will find the element, even though it will find the same element again.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[][] indexedNums = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            indexedNums[i][0] = nums[i]; // Store value
            indexedNums[i][1] = i; // Store index
        }
        Arrays.sort(indexedNums, (a, b) -> Integer.compare(a[0], b[0])); // Sort by value

        for (int i = 0; i < nums.length; i++) {
            int complement = target - indexedNums[i][0];
            int idx = binarySearch(indexedNums, i + 1, nums.length - 1, complement);
            if (idx != -1) {
                return new int[]{indexedNums[i][1], indexedNums[idx][1]};
            }
        }
        return new int[]{-1, -1}; // No solution
    }

    private int binarySearch(int[][] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid][0] == target) return mid;
            if (nums[mid][0] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1; // Not found
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        indexed_nums = [(val, idx) for idx, val in enumerate(nums)]  # Pair values with indices
        indexed_nums.sort()  # Sort by value

        def binary_search(nums: List[tuple], left: int, target: int) -> int:
            right = len(nums) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid][0] == target:
                    return mid
                elif nums[mid][0] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return -1

        for i, (val, idx) in enumerate(indexed_nums):
            complement = target - val
            idx_in_sorted = binary_search(indexed_nums, i + 1, complement)
            if idx_in_sorted != -1:
                return [idx, indexed_nums[idx_in_sorted][1]]
        return [-1, -1]  # No solution

Method 3 - Using Sorting and 2 Pointer Approach

Assuming array sorted in ascending order. Now we take first and last element, and sum them up. If sum is equal to T, we have found the pair, but if sum is greater than T, we reduce right pointer by 1, or increment left pointer otherwise.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

private static int[] twoSum(int[] nums, int target) {
	Arrays.sort(nums);
	int left = 0;
	int right = nums.length - 1;
	while(left < right) {
		if(nums[left] + nums[right] == target) {
			return new int[] {nums[left], nums[right]};
		} else if (nums[left] + nums[right] < target) {
			left++;
		} else {
			right--;
		}
	}
	return new int[] {};
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[][] indexedNums = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            indexedNums[i][0] = nums[i];
            indexedNums[i][1] = i;
        }
        Arrays.sort(indexedNums, (a, b) -> Integer.compare(a[0], b[0]));

        int l = 0, r = nums.length - 1;
        while (l < r) {
            int sum = indexedNums[l][0] + indexedNums[r][0];
            if (sum == target) {
                return new int[]{indexedNums[l][1], indexedNums[r][1]};
            } else if (sum < target) {
                l++;
            } else {
                r--;
            }
        }
        return new int[]{-1, -1};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        indexed_nums = [(val, idx) for idx, val in enumerate(nums)]
        indexed_nums.sort()  # Sort based on values

        l, r = 0, len(indexed_nums) - 1
        while l < r:
            sum_lr = indexed_nums[l][0] + indexed_nums[r][0]
            if sum_lr == target:
                return [indexed_nums[l][1], indexed_nums[r][1]]
            elif sum_lr < target:
                l += 1
            else:
                r -= 1
        return [-1, -1]  # No solution

Complexity

  • ⏰ Time complexity: O(n log n) (From sorting it takes O(nlogn) time and for 2 pointer technique takes O(n) time)
  • 🧺 Space complexity: O(1)

Method 4 - Use Hash Table 🏆

I have already mentioned in problem in the application of hash table here. The best way would be to insert every element into a hash table (without sorting). This takes O(n) as constant time insertion. Then for every x, we can just look up its complement, T-x, which is O(1). Overall it takes will be O(n).

Pseudocode

Here is how the pseudocode will look.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Let arr be the given array.
And T be the given sum

hash = {}

for (i = 0 i < arr.length - 1; i++) { 
	// key is the element and value is its index.
	num = arr[i]
	complement = T - num
    if complement in hash and hash[complement] < i: 
	    print("Pair:", i, ",", hash[complement], "has sum", T)
	hash[num] = i
}

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        index_map: dict[int, int] = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in index_map:
                return [index_map[complement], i]
            index_map[num] = i
        return [-1, -1]  # No solution

Dry Run

For example, if we hash the example array we’ll have this hash table:

1
2
3
4
5
6
7
8

Key   Value
5        5 - 5 = 0
3        5 - 3 = 2
7        5 - 7 = -2
0        5 - 0 = 5
1        5 - 1 = 4
4        5 - 4 = 1
2        5 - 3 = 2

Please let us know if you know any other approach. Thanks.