Given an array, find two values in the array which sum upto a value K

Given an array, and a value K as input, we have to find a pair of elements such that their sum is K.

There are multiple ways of solving this problem. We will discuss some of them in this post. Let us implement the function which prints the two values such that array[i] + array[j] = K if there is such a pair exists. If not print “No such pair”.

Method#1: Brute-Force approach

Check each possible pair of values from this array to see if their sum is K. The Java function for this algorithm is given below.

 public static void printTwoValues(int[] array, int sum)
    {
        int i,j;
        for( i = 0; i < array.length - 1; i++ )
        {
            for( j = i+1; j < array.length; j++ )
            {
                if( array[i] + array[j] == sum )
                {
                    System.out.println("The two values are (" + i +", " + j + ")");
                    return;
                }
            }
        }
        System.out.println("No such pair exists!");
    }

This algorithm runs in O(n²) time complexity and O(1) space complexity.

Method#2: Sorting Approach

This method will modify the sequence of elements in the array as we sort the array first.

Take two indices one pointing to the beginning and the other pointing to the end of the array. Calculate the sum of these two values and check if it is the given value K. If it is, print the two values and return.

Otherwise check if their sum is greater then given value K, then we need to decrement the second pointer as we are exceeding the target value.

Similarly if the sum is lesser than given value K, we need to increment the first pointer hoping that we move closer to the required sum.

public static void printTwoValues(int[] array, int sum)
    {
        Arrays.sort(array);
        int i = 0;
        int j = array.length-1;
        while( i < j)
        {
            if( array[i] + array[j] == sum)
            {
                System.out.println("The two values are (" + array[i] +", " + array[j] + ")");
                return;
            }
            else if( array[i] + array[j] < sum )
            {
                i++;
            }
            else
            {
                j--;
            }
        }
        System.out.println("No such pair exists!");
    }

This algorithm runs in O(n log n) time complexity as we are sorting the array first and O(1) space complexity.

Method#3: Hash set approach

This method uses an implementation of the set data structure to store the values. As we run through the array, we search the set for (sum-array[i]). If it is found, we are done. Otherwise we insert array[i] into the set.

public static void printTwoValues(int[] array, int sum)
    {
        HashSet<Integer> hSet = new HashSet<Integer>();
        int i;
        for( i = 0; i < array.length; i++ )
        {
            if( hSet.contains(sum-array[i]) )
            {
                System.out.println("The two values are (" + array[i] +", " + (sum-array[i]) + ")");
                return;
            }
            else
                hSet.add(array[i]);
        }
        System.out.println("No such pair exists!");
    }

This algorithm takes O(n) time but uses O(n) extra space for the set data structure.

Variations of the problem:

However if the problem is to find the two indices i,j such that array[i] + array[j] = K, the first and third approaches can easily be modified to solve this problem. But the second approach which uses sorting can not be used because the order of the elements gets changed.
If the problem is to find all pairs whose sum is K, and the array
may contain duplicates, first approach does not change. But the sorting approach will not work.

We will discuss these problems in the upcoming posts.

Leave a Reply Cancel reply