ntree.ai
ntree.aiTwo Sum

Solutions

1. Brute Force

O(n²) time | O(1) space

Intuition

We can check every possible pair of numbers in the array and return the one that sums up to the target.

To get all the possible pairs we will use two nested loops over the whole array.

Algorithm

  1. Iterate through the outer loop from the first element to the last element with i index.
  2. For each outer loop iteration, iterate through the inner loop from the element at i + 1 to the last element with j index.
  3. Check if the sum of an element at index i and an element at index j is equal to the target, return the indexes if it is.
target = 10
11
2
15
7
8
1
012345
i j
11 + 2 = 13, 13 ≠ 10
1 / 9

A naive approach would iterate both loops from the first element to the last one. However, we only need to check unordered pairs (combinations) since [i, j] gives the same sum as [j, i]. So we do not check indexes before i as they have already been paired with all the other indexes in the previous iterations. Also, from the problem description we can't use the same index twice, so we skip i itself and start from i + 1.

Code

Code
Python
def twoSum(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]
    raise ValueError('no answer')
/**
 * @param {number[]} nums
 * @param {number} target
 * @returns {number[]}
 */
var twoSum = function (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]
    }
  }
  throw new Error('no answer')
}
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 };
            }
        }
        throw new IllegalArgumentException("no answer");
    }
}

2. Sorting and Two Pointers

O(nlogn) time | O(n) space

Intuition

If we sort the array first, we can use one loop with two indexes starting at each side of the array instead of checking every possible pair.

If the sum of the elements at those indexes is greater than the target, we can skip the right element completely as all other pairs with the right element will make the sum only greater. In the same way we can skip the left element if the sum is less than the target.

Algorithm

  1. Create a new sorted array with the same elements, keeping the original index of each element.
  2. Set the left index to the first element and the right index to the last element.
  3. Iterate through the loop while left is less than right checking the sum of two elements on left and right indexes.
    • If the sum is equal to the target, return the original indexes.
    • If the sum is less than the target, move left index to the right left = left + 1.
    • If the sum is greater than the target, move right index to the left right = right - 1.
target = 10
11
2
15
7
8
1
012345
15
0
left
21
1
73
2
84
3
110
4
152
5
right
1 + 15 = 16, 16 > 10
1 / 5

Code

Code
Python
def twoSum(nums: list[int], target: int) -> list[int]:
    pairs = sorted((n, i) for i, n in enumerate(nums))
    left, right = 0, len(nums) - 1
    while left < right:
        total = pairs[left][0] + pairs[right][0]
        if total == target:
            return [pairs[left][1], pairs[right][1]]
        if total < target:
            left += 1
        else:
            right -= 1
    raise ValueError('no answer')
/**
 * @param {number[]} nums
 * @param {number} target
 * @returns {number[]}
 */
var twoSum = function (nums, target) {
    const pairs = nums.map((n, i) => [n, i]).sort((a, b) => a[0] - b[0]);
    let left = 0, right = nums.length - 1;
    while (left < right) {
        const total = pairs[left][0] + pairs[right][0];
        if (total === target) return [pairs[left][1], pairs[right][1]];
        if (total < target) left++;
        else right--;
    }
    throw new Error('no answer');
}
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[][] pairs = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            pairs[i][0] = nums[i];
            pairs[i][1] = i;
        }
        java.util.Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int total = pairs[left][0] + pairs[right][0];
            if (total == target) return new int[] { pairs[left][1], pairs[right][1] };
            if (total < target) left++;
            else right--;
        }
        throw new IllegalArgumentException("no answer");
    }
}

3. Hash Table

O(n) time | O(n) space

Intuition

We can iterate through the array with one loop. At each iteration we check if for that element there is a pair in the array that sums up to the target.

To check if the pair exists in the array in O(1) time we will use a hash table.

Algorithm

  1. Create an empty hash table.
  2. Iterate through the loop from the first element to the last element with i index.
  3. Check if the needed pair target - nums[i] exists in the hash table, return the indexes if it does.
  4. Add the element to the hash table, nums[i] as a key and i as a value.
target = 10
11
2
15
7
8
1
012345
i
10 − 11 = -1, -1 is not in the hash table
1 / 6

A naive approach would use two passes, adding all the elements to a hash table first and then starting another loop to find the pair. However, adding elements to the hash table on the fly while iterating still guarantees we check all the possible pair combinations.

Code

Code
Python
def twoSum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i
    raise ValueError('no answer')
/**
 * @param {number[]} nums
 * @param {number} target
 * @returns {number[]}
 */
var twoSum = function (nums, target) {
  const seen = new Map()
  for (let i = 0; i < nums.length; i++) {
    if (seen.has(target - nums[i])) return [seen.get(target - nums[i]), i]
    seen.set(nums[i], i)
  }
  throw new Error('no answer')
}
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer j = seen.get(target - nums[i]);
            if (j != null) return new int[] { j, i };
            seen.put(nums[i], i);
        }
        throw new IllegalArgumentException("no answer");
    }
}
def twoSum(nums: list[int], target: int) -> list[int]:
    pass
 

Press Visualise to step through your code.