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.

Pair with given sum in an array

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]

Recommended Posts