Interview Question

Interview Hyderābād (India)

Given array of n integers and given a number X, find all

  the unique pairs of elemens (a,b), whoose some is equal to X.
data structures

Interview Answer

2 Answers


Let arr be the given array. And K be the give sum for i=0 to arr.length - 1 do hash(arr[i]) = i // key is the element and value is its index. end-for for i=0 to arr.length - 1 do if hash(K - arr[i]) != i // if K - ele exists and is different we found a pair print "pair i , hash(K - arr[i]) has sum K" end-if end-for

Interview Candidate on Jan 18, 2012

Using hashmap is great to get O(N) time complexity with O(n) space cost, however, if no additional memory is recommended, sort the list (O(nLogn)) and using a simple algorithm (O(n)) to find all pairs demoed in this video:

Anonymous on Mar 19, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.