Introduction

Example – A = [2, 4, 9, 1, 10, 5] , Sum = 6

Output – (2,4) or (1,5) as 2+4 = 6 and 1+5 = 6

Approach

  1.  Sorting – O(nlogn) – Sort the array. Maintain a low pointer at start and high pointer at end. Traverse and move pointers accordingly.

Video Demonstration

Run Time Complexities

Time – O(nlogn)

Space – O(1)

Code

C++

#include <iostream>
#include <algorithm>
 
// Function to find a pair in an array with a given sum using sorting
void findPair(int arr[], int n, int sum)
{
    // sort the array in ascending order
    std::sort(arr, arr + n);
 
    // maintain two indices pointing to endpoints of the array
    int low = 0;
    int high = n - 1;
 
    // reduce the search space `arr[low…high]` at each iteration of the loop
 
    // loop till the search space is exhausted
    while (low < high)
    {
        // sum found
        if (arr[low] + arr[high] == sum)
        {
            std::cout << "Pair found";
            return;
        }
 
        // increment `low` index if the total is less than the desired sum;
        // decrement `high` index if the total is more than the desired sum
        (arr[low] + arr[high] < sum)? low++: high--;
    }
 
    // we reach here if the pair is not found
    std::cout << "Pair not found";
}
 
int main()
{
    int arr[] = { 8, 7, 2, 5, 3, 1};
    int sum = 10;
 
    int n = sizeof(arr)/sizeof(arr[0]);
 
    findPair(arr, n, sum);
 
    return 0;
}

Java

 

import java.util.Arrays;
 
class Main
{
    // Function to find a pair in an array with a given sum using sorting
    public static void findPair(int[] A, int sum)
    {
        // sort the array in ascending order
        Arrays.sort(A);
 
        // maintain two indices pointing to endpoints of the array
        int low = 0;
        int high = A.length - 1;
 
        // reduce the search space `A[low…high]` at each iteration of the loop
 
        // loop till the search space is exhausted
        while (low < high)
        {
            // sum found
            if (A[low] + A[high] == sum)
            {
                System.out.println("Pair found");
                return;
            }
 
            // increment `low` index if the total is less than the desired sum;
            // decrement `high` index if the total is more than the desired sum
            if (A[low] + A[high] < sum) {
                low++;
            } else{
                high--;
            }
        }
 
        // we reach here if the pair is not found
        System.out.println("Pair not found");
    }
 
    public static void main (String[] args)
    {
        int[] A = { 8, 7, 2, 5, 3, 1 };
        int sum = 10;
 
        findPair(A, sum);
    }
}

Python

# Function to find a pair in an array with a given sum using sorting
def findPair(A, sum):
 
    # sort the list in ascending order
    A.sort()
 
    # maintain two indices pointing to endpoints of the list
    (low, high) = (0, len(A) - 1)
 
    # reduce the search space `A[low…high]` at each iteration of the loop
 
    # loop till the search space is exhausted
    while low < high:
 
        if A[low] + A[high] == sum:        # sum found
            print("Pair found")
            return
 
        # increment `low` index if the total is less than the desired sum;
        # decrement `high` index if the total is more than the desired sum
        if A[low] + A[high] < sum:
            low = low + 1
        else:
            high = high - 1
 
    # No pair with the given sum exists
    print("Pair not found")
 
 
if __name__ == '__main__':
 
    A = [8, 7, 2, 5, 3, 1]
    sum = 10
 
    findPair(A, sum)

You can use our online compiler to type and compile your code.

Want to optimize the solution.  Check out O(n) approach from here.

Checkout our next problem.

LEAVE A REPLY