Approach 1 : Brute force
We can start with first element of array and subtract it with every other number from array and check the diff. Repeat this for rest all elements. Complexity O(N^2)
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" exists in set. Complexity O(N)
Approach 4: Increment or decrement indexes based on difference:
Use two indices out of which one starts at beginning and one starts at first index plus one. As the array is sorted, you just want to check if current diff is less than or greater than k (key), based on the result increment or decrement indices. If we found match update both indices. Complexity O(N)
Below solution implements approach 4. This solution will not display duplicate pairs if we have duplicate numbers.
class Solution { public static void findPairHavingDiff(int[] numbers, int k){ if(numbers.length > 0){ int start = 0; int end = 1; while(end < numbers.length){ int diff = numbers[end] - numbers[start] ; if(diff == k) { System.out.println("Found Pair : " + numbers[start] + " & " + numbers[end]); start++; end++; } else if(diff < k) end++; else if(diff > k) start++; } } else System.out.println("None found"); } public static void main(String[] args) { int[] input = {-1, 2, 3, 4, 5, 6, 7, 8, 10 }; findPairHavingDiff(input, 9); } } //Output of the above solution is Found Pair : -1 & 8
No comments:
Post a Comment