Pair with given sum in an array

In this problem, we have to find a pair of number in an unsorted array which adds up to the given target value and return the index of both the numbers.

Problem

Find the pair of number in an unsorted array which adds up to the given target value and return index of both the numbers.

Example -

Input: array=[8, 7, 2, 5, 3, 1] target=12
Output: [1, 3]

Input: array=[1, 2, 3, 4, 5] target=9
Output: [3, 5]

Brute-force approach

We can solve this problem using nested loops but the time complexity will be O(n^2), which is not an optimized solution.

Python

def find_pair(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

nums = [8, 7, 2, 5, 3, 1]
target = 12

print(find_pair(nums, target))

JavaScript

function findPair(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (j = i + 1; j <= nums.length; j++) {
      if (nums[i] + nums[j] == target) {
        return [i, j];
      }
    }
  }
  return null;
}

nums = [8, 7, 2, 5, 3, 1];
target = 12;

console.log(findPair(nums, target));

Output

[1, 3]

Optimized solution (using HashMap)

We can use some data structure to store previous results which are already traversed and compare it to get the desired result. The data structure should be HashMap or any other which stores data in a similar way.

Fot this solution time complexity will be O(n).

Python

def find_pair(nums, target):
    hash_map = {}
    for i in range(len(nums)):
        if target - nums[i] in hash_map:
            return [hash_map[target - nums[i]], i]
        hash_map[nums[i]] = i
    return None

nums = [8, 7, 2, 5, 3, 1]
target = 12

print(find_pair(nums, target))

JavaScript

function findPair(nums, target) {
  const hashMap = {};
  for (i = 0; i < nums.length; i++) {
    if (target - nums[i] in hashMap) {
      return [hashMap[target - nums[i]], i];
    }
    hashMap[nums[i]] = i;
  }
  return null;
}

nums = [8, 7, 2, 5, 3, 1];
target = 12;

console.log(findPair(nums, target));

Output

[1, 3]