Given an array of integers and a value. Find all the pairs that sums up to the value in O(n) time with only one pass over the array. Can you do it efficiently without any space constraint?
For example, Given A=[3, 0, -2, 1, 3, 6, 8] and sum = 6 then output pairs are: {(3, 3), (0, 6), (-2, 8)}.
O(n) time with O(n) space solution
Use a hashmap to store the value at each position of A[]. While populating the hashmap for each position i, check whether the (sum-A[i]) is contained in the hashmap. If it was contained then we found a pair. Otherwise continue searching.
O(nlgn) time with O(1) space solution
Sort the array in O(nlgn) time. Now, keep two pointers, one at the beginning and the other at the end of the sorted array. If diff=A[j]-A[i] is equal to sum then (i,j) is a pair. Otherwise if sum>diff then search for a lower element on right (i.e. decrement j). Else, search for a higher element on the left (i.e. increment i).
Read full article from Pair of array elements that add up to a given sum - Algorithms and Problem SolvingAlgorithms and Problem Solving
No comments:
Post a Comment