Count all distinct pairs with difference equal to k (Two sum II Leetcode)

Given an integer array and a positive integer k, count all distinct pairs with differences equal to k. 

Examples:

Input: arr[] = {1, 5, 3, 4, 2}, k = 3
Output: 2
There are 2 pairs with difference 3, the pairs are {1, 4} and {5, 2} 

Input: arr[] = {8, 12, 16, 4, 0, 20}, k = 4
Output: 5
There are 5 pairs with difference 4, the pairs are {0, 4}, {4, 8}, 
{8, 12}, {12, 16} and {16, 20}

This is popular question in GeeksForGeeks-Count Pairs, LeetCode - K-diff pairs A collection of hundreds of interview questions and solutions are available in our blog at Interview Question

Solutions:

1. Using two nested Loop
1. Use two loops to iterate through the array and check for every pair if they have the difference, if so, add them to the list
2. Complexity: O(n^2)
2. Using two pointers
1. Iterate through the elements of the array and for every element,  create two pointers: start and end, where start points to the current element and end points to the last element of the array
2. If the element at start index and end index satisfy the difference, we found the pair
3. If the elements at start and end index do not satisfy the difference, the pair of the element at start index might be earlier in the array, so advance the end index by 1 (i.e. end - 1). Do this till start<end (i.e. we check distinct elements).
4. Worst case complexity: O(n^2), best case: O(n*logn)

Solution