How to use Sorting + Two Pointers In Javascript
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));
Output
true
Time Complexity: O(nlogn) – due to sorting.
Space Complexity: O(1) – no extra space used apart from a few variables.
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
Table of Content
- Brute Force Approach
- Using Sorting + Two Pointers
- Using Hash Map