Find Pair With Given Sum in an Array

Statement#

We’re given an array of integers and a value. Determine if there are any two integers in the array whose sum is equal to the given value. Return true if the sum exists; otherwise, return false.

Example#

Consider this array and the target sums:

Sample input#

This challenge covers both sorted and unsorted arrays.

[5, 7, 1, 2, 8, 4, 3] 
val = 3

Expected output#

True

Try it yourself#

The test cases include both sorted and unsorted arrays.

Solution 1#

In this solution, we’ll use the following algorithm to find a pair that adds to the target (say val).

• Scan the whole array once and store visited elements in a hash set.
• During the scan, for every element e in the array, we check if val - e is present in the hash set. In other words, we check if val - e was already visited.
  • If val - e is found in the hash set, it means there is a pair (e, val - e) in the array whose sum is equal to the given val, and the function returns true.
  • If we exhaust all elements in the array and don’t find any such pair, the function returns false.

Let’s visually run this algorithm:

Time complexity#

The time complexity of this solution is $O(n)$.

Space complexity#

The space complexity of this solution is $O(n)$.

Solution 2#

Note: This solution works only for the sorted array.

To understand the algorithm for this solution, let’s look at the pseudo-code below:

// assume 0 is the first index in array
// and n is the total number of elements in array
left = 0
right = n - 1
while left is less than right
    sum = array[left] + array[right]
    if sum == val return true
    if sum is less than val
        // sum is smaller than value
        // means pair can only exist to the
        // right of left element, so left element
        // should be moved one step next
        left = left + 1
    else
        // sum is greater than value
        // means pair can only exist to the
        // left of right element, so right element
        // should be moved one step previous
        right = right - 1

Let’s see a visual representation of the algorithm:

Time complexity#

The time complexity of this solution is $O(nlogn)$.

Space complexity#

The space complexity of this solution is $O(1)$.