Find a pair in given array with sum = x

Given an array of elements and a value 'x', find two elements from the array whose sum is equal to 'x'.

In technical interviews, you have to gradually improve and come up with a better approach than the initial one. This is why it is sometimes important to know multiple approaches to solving a problem and their pros and cons.

If the given array is sorted:

1. Initialize 2 variables l = 0 and r = arr.length - 1
2. while l < r:
3.      if arr[l] + arr[r] == x:
4.          return "pair found"
5.      else if arr[l] + arr[r] < x:
6.          l = l + 1 // goto the next large value in the array which may make the pair sum = x
7.      else if arr[l] + arr[r] < x:
8.          r = r - 1 // goto the next smaller value in the array which may make the pair sum = x
9. return "No pair with sum x found"

Example:

Example:
let arr = [2, 6, 10, 15, 18, 20, 23, 25] and x = 28

1.  l = 0, r = 7
    arr[l] + arr[r] = 27 < x 
    l = l + 1 = 1

2.  l = 1, r = 7    
    arr[l] + arr[r] = 31 > x 
    r = r - 1 = 6
    
3.  l = 1, r = 6
    arr[l] + arr[r] = 29 > x 
    r = r - 1 = 5

4.  l = 1, r = 5
    arr[l] + arr[r] = 26 < x 
    l = l + 1 = 2

5.  l = 2, r = 5
    arr[l] + arr[r] = 30 > x 
    r = r - 1 = 4
    
6.  l = 2, r = 4
    arr[l] + arr[r] = 28 = x 
    "Pair Found"

Code:

def find_pair_sorted(arr, x):
    # initialize variables to the start and end of the array
    l = 0
    r = len(arr) - 1

    while l < r:
        pair_sum = arr[l] + arr[r]

        # if pair is found
        if pair_sum == x:
            return arr[l], arr[r]
        # if the pair sum is less than x go to the next bigger value from left
        elif pair_sum < x:
            l += 1
        # if the pair sum is more than x go to the next lesser value from right
        else:
            r -= 1

    # If pair not found
    return "Not found"


arr = [2, 6, 10, 15, 18, 20, 23, 25]
print('Sorted array:', arr)
print('Pair with sum 28 in sorted array:', find_pair_sorted(arr, 28))

"""
Outputs:
Sorted array: [2, 6, 10, 15, 18, 20, 23, 25]
Pair with sum 28 in sorted array: (10, 18)
"""

Time Complexity:

O(n) where n is the number of elements in the array.

Space Complexity:

O(1) (constant) as no extra space is used.

If the given array is unsorted:

Method 1:

1. Sort the given array
2. Apply the find_pair_sorted(arr, x) procedure to get the pair

Time Complexity:

The time complexity of this method depends on the sorting algorithm used. If the sorting algorithm is Quick Sort, in worst case time complexity would be O(n²). If merge sort is used, the time complexity will be O(n log n).

Space Complexity:

It again depends on the sorting algorithm used. If the sorting algorithm is Quick Sort, in worst case time complexity would be O(log n). If merge sort is used, the time complexity will be O(n).

Method 2:

// set is a data structure which stores unique values only
// we can search an element in the set in O(1) i.e. constant time

1. initialize an empty set
2. for each value in arr
3.      if (x - value) is present in set
4.          return "Pair found"
5.      else 
6.          add value to the set
7. return "Pair not found"

The algorithm is a simple math equation.
if p + q = x
then p = x - q
It checks if x - value is present in the set. If it is then value, x - value are the two numbers in the array with sum = x.

Example:

let arr = [1, 4, 45, 6, 10, 8] and X = 16
initially set = {}

1.  16 - 1 = 15 
    15 is not in set -> set.add(1)
set = {1}

2.  16 - 4 = 12 
    12 is not in set -> set.add(4)
set = {1, 4}

3.  16 - 45 = 29 
    29 is not in set -> set.add(45)
set = {1, 4, 45}

4.  16 - 6 = 10
    10 is not in set -> set.add(6)
set = {1, 4, 45, 6}

5.  16 - 10 = 6
    6 is present in set -> "Pair Found"

Code:

def find_pair_unsorted(arr, x):
    elem_set = set({})

    # To store the indexes of both the elements
    pair = [-1, -1]

    for value in arr:
        # if x - value has already been discovered in the array
        # Pair found, return the values
        if (x-value) in elem_set:
            return x-value, value
        
        # else add the current value in the elem_set
        else:
            elem_set.add(value)

    return "Not found"

arr = [1, 4, 45, 6, 10, 8]
print('Unsorted array:', arr)
print('Pair with sum 16 in unsorted array:', find_pair_unsorted(arr, 16))
"""
Outputs:
Unsorted array: [1, 4, 45, 6, 10, 8]
Pair with sum 16 in unsorted array: (6, 10)
"""

Time Complexity:

The time complexity of the worst case is linear O(n).

Space Complexity:

It uses a space of O(n) for storing the elements in the set data structure.

As an exercise try finding all the pairs with sum = x rather than just 1 pair. 

What do you think will be its time complexity. Let me know in the comments below what you think it might be. ;)

--
Have any questions or suggestions? Post in the comments below!!

By,

Anubhav Shrimal