Check if Pair with Given Sum Exists in Array in JavaScript

Two Sum is a classic algorithmic problem where you're given an array of integers and a target sum. The task is to determine whether any two numbers in the array add up to the target sum.

Given an array A[] of n numbers and another number x, the task is to check whether or not there exist two elements in A[] whose sum is exactly x. 

Examples: 

Input: arr[] = [0, -1, 2, -3, 1], x= -2
Output: Yes
Explanation: If we calculate the sum of the output,1 + (-3) = -2

Input: arr[] = [1, -2, 1, 0, 5], x = 0
Output: No

Brute Force Approach

The brute force approach involves checking every possible pair of elements in the array to see if their sum equals the target. This approach has a time complexity of O(n^2).

Example: Implementation of brute force approach to check whether a pair with a given sum exists in an array.

function hasTwoSum(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 true;
            }
        }
    }
    return false;
}

// Test
let nums = [2, 7, 11, 15];
let target = 9;
console.log(hasTwoSum(nums, target)); 

true

Time Complexity: O(n^2) - due to nested loops.

Space Complexity: O(1) - no extra space used.

Using Sorting + Two Pointers

Sort the array first, then use two pointers to traverse from the start and end simultaneously. Adjust the pointers based on whether the sum of the current pair is less than or greater than the target.

Example: Implementation of two pointer approach to check whether a pair with a given sum exists in an array.

function hasTwoSum(nums, target) {
    nums.sort((a, b) => a - b);
    let left = 0;
    let right = nums.length - 1;
    while (left < right) {
        let sum = nums[left] + nums[right];
        if (sum === target) {
            return true;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}

// Test
let nums = [3, 5, 2, 8, 4];
let target = 10;
console.log(hasTwoSum(nums, target));

true

Time Complexity: O(nlogn) - due to sorting.

Space Complexity: O(1) - no extra space used apart from a few variables.

Using Hash Map

You can optimize the solution using a hash map (JavaScript object) to store the elements and their indices. While iterating through the array, check if the difference between the target and the current element exists in the hash map.

Example: Implementation of hashmap approach to check whether a pair with a given sum exists in an array.

function hasTwoSum(nums, target) {
    let numMap = {};
    for (let i = 0; i < nums.length; i++) {
        let required = target - nums[i];
        if (numMap[required]) {
            return true;
        }
        numMap[nums[i]] = true;
    }
    return false;
}

// Test
let nums = [4, 9, 3, 2, 7];
let target = 11;
console.log(hasTwoSum(nums, target)); 

true

Time Complexity: O(n) - single pass through the array.

Space Complexity: O(n) - hashmap to store elements.

lunatic1

Follow

Improve

Article Tags :

• JavaScript
• Web Technologies
• JavaScript-Program