Pairs HackerRank Problem
Task:- Given an array ‘arr’ and an integer ‘k’. Find the number of pairs whose difference is equal to value k.
For eg:- arr = [ 4, 6, 8, 10, 7] and k = 2.
The pairs which satisfy the conditions are (4, 6), (6, 8), (8, 10).
So the answer is 3.
Note that (6, 4), (8, 6) is the same as (4, 6) and (6, 8) and we do not count them as different pairs.
Brute Force Approach:- Check for each pair possible whether the difference between them is k or (-k). If it is increment the count.
To check all possible pairs, we can simply use two for loops. Let’s say outer for loop uses ‘i’ and inner for loop uses ‘j’ variable. i ranges from 0 to (n-1) and the inner for loop starts from (i+1) and proceeds till the last index i.e- (n-1) where n is the length of array.
The time complexity of this approach is O(N²) as for N elements, we traverse the array linearly ( O(N) ). The space complexity is constant i.e- O(1) as we just create one variable to keep the count.
Brute Force Code:-
Efficient Approach:- The problem with the above logic is that we are searching (element + k) and (element — k) in the remaining array. This searching costs linear time but we can make use of sets to keep track of visited elements to minimise this searching time as sets uses hashing and costs constant time( O(1) ) for searching.
We can traverse through the array and for each element, we check whether (element +k), (element-k) is present in the ‘visited’ set. If it is present we increment the count. Then before going to the next element, we add the current element to the set.
In this way, we keep track of elements we already visited and hence can search for elements with difference k in constant time.
The overall time complexity is linear i.e- O(N) for linearly traversing the array. The space complexity is also linear( O(N) ) as we use a set that can have at most N elements.
Efficient Code:-
