Find all the pairs with given sum in a sorted array

How to find pair of elements (a,b) in a sorted array and given sum x where x=a+b


Category: Data Structure And Algorithms Tags: C#

Find all the pairs with given sum in a sorted array - Code Files

Problem statement

    Find all the pairs with sum x in a sorted array. Suppose an array is {1,2,3,4,5,6,7,8} and x=10. Then program output should be {2,8}, {3,7}, {4,6} So (2+8) = (3+7) = (4+6) = 10 

Solution

Method 1: Traverse array from both start and end

    A very important information is given that array is sorted so from left to right elements will be in increasing order and from right to left in decreasing order.

Suppose in case of array {1,2,3,4,5,6,7,8}, we keep two pointers on index i=0 and j=7 so sum of their elements 1 and 8 is 9 which is less than desired sum 10. In that case we can increase index i by 1 hoping next value will be bigger and we might achieve desired sum. So now i=2 and j=7 and sum of elements are 2+8=10 and this is our first pair. Look at the code below.

    static List<(int, int)> FindAllPairs(int[] arr, int desiredSum)
    {
        List<(int, int)> pairs = new List<(int, int)>();
        int i = 0;
        int j = arr.Length - 1;

        while (i < j)
        {
            int sum = arr[i] + arr[j];
            if (sum == desiredSum)
            {
                pairs.Add((arr[i], arr[j]));
                i++;
                j--;
            }
            else if (sum > desiredSum)
            {
                j--;
            }
            else
            {
                i++;
            }
        }

        return pairs;
    }

Let’s run the code above.

    static void Main(string[] args)
    {
        int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };
        int desiredSum = 10;

        var allPairs = FindAllPairs(arr, desiredSum);
        Console.WriteLine("All matching pairs are:");
        foreach (var pair in allPairs)
        {
            Console.WriteLine($"{pair.Item1}, {pair.Item2}");
        }
    }

Output

All matching pairs are:

2, 8

3, 7

4, 6

Method 2: Using a Hashset

    As explained in method 1 that value of elements increases while traversing from left to right, we can start with minimum element(index=0) and try to find another element which sum can match with desired sum. But to search for another element in sorted array may take O(log n) time so we could make use of a Hashset to find it in O(1) time.

Starting with index i=0(value is 1) we need another element which has value 9 to match desired sum. So we store key=1 in Hashset. Moves on and when i=1(value is 2) we know that we need another element with value 8 so we look into Hashset if any element with value 8 was encountered previously if yes then we have a pair else we move on. While traversing when we reach index i=5(value is 6) we look for element having value 4 and since we must have encountered element 4 previously we must have that in Hashset and that becomes our first pair.

    static List<(int, int)> FindAllPairsUsingHash(int[] arr, int desiredSum)
    {
        List<(int, int)> pairs = new List<(int, int)>();
        HashSet<int> hashSet = new HashSet<int>();

        for (int i = 0; i < arr.Length; i++)
        {
            int element = arr[i];
            int requiredElement = desiredSum - element;

            if (hashSet.Contains(requiredElement))
            {
                pairs.Add((requiredElement, element));
            }

            if (!hashSet.Contains(element))
            {
                hashSet.Add(element);
            }
        }
        return pairs;
    }

Let’s run the code above.

    static void Main(string[] args)
    {
        int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };
        int desiredSum = 10;

        var allPairs = FindAllPairsUsingHash(arr, desiredSum);
        Console.WriteLine("All matching pairs are:");
        foreach (var pair in allPairs)
        {
            Console.WriteLine($"{pair.Item1}, {pair.Item2}");
        }
    }

Output

All matching pairs are:

4, 6

3, 7

2, 8


Like 0 People
Last modified about 28 days ago
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 144
Questions: 15
Given Best Solutions: 15 *

Comments:

No Comments Yet

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x