Tuesday, October 27, 2015

Find out all pair of element having sum as ‘k' in given sorted array

We have given a sorted array of integer. Need to find out all pair of element having sum as ‘k'.

Approach 1 : Brute force
We can start with first element of array and add it with every other number from array and check the sum. Repeat this for rest all elements. Complexity O(N^2)
This brute force approach can be slightly improved by adding the elements from the current index + 1 to the index where sum is greater than k (key).

Approach 2 : Binary Search
As the array elements are sorted we can use binary search to search the matching element. E.g. take first element from array, and search for element equals to "k + first element".
This we can repeat for all the elements in the array. Complexity O(NlogN)

Approach 3 : Use Set/HashMap
If we are allowed to use additional space we can add elements HashSet or HashMap as key one by one and check before adding if element equal to "k + element to be added in set" exists in set. Complexity O(N)

Approach 4: Increment or decrement indexes based on sum:
Use two indices out of which one starts at beginning and one starts at end. As the array is sorted, you just want to check if current sum is less than or greater than k (key), based on the result increment or decrement end index. If we found match update both indices. Complexity O(N)

Below solution implements approach 4. This approach does not display duplicate pairs if we have duplicate elements.

class Solution {
    public static void findPair(int[] numbers, int k){
        if(numbers.length > 0){
            //get first & last index from the sorted array
            int start = 0;
            int end = numbers.length - 1;
            while(start < end){
                int sum = numbers[start] + numbers[end];
                if(sum == k) {
                    System.out.println("Found Pair : " + numbers[start] + " & " + numbers[end]);
                    start++;
                    end--;
                }
                else if(sum < k) start++;
                else if(sum > k) end--;
            }
        }
        else System.out.println("None found");
    }

    public static void main(String[] args) {
        int[] input = {0, 2, 3, 5, 6, 8, 12, 15, 18 };
        findPair(input, 18);
    }
}

//Output of the above solution is
Found Pair : 0 & 18
Found Pair : 3 & 15
Found Pair : 6 & 12

No comments:

Post a Comment