Two-pointer Approach

• The problem is just a variant of 2-sum.
Update: Fixed a bug that can cause integer subtraction overflow.
Update: The code runs in `O(n log n)` time, using `O(1)` space.

``````public int findPairs(int[] nums, int k) {
int ans = 0;
Arrays.sort(nums);
for (int i = 0, j = 0; i < nums.length; i++) {
for (j = Math.max(j, i + 1); j < nums.length && (long) nums[j] - nums[i] < k; j++) ;
if (j < nums.length && (long) nums[j] - nums[i] == k) ans++;
while (i + 1 < nums.length && nums[i] == nums[i + 1]) i++;
}
return ans;
}
``````

• great! here is my two-pointers on array solution:

``````import java.util.Arrays;

public class Solution {
public int findPairs(int[] nums, int k) {
Arrays.sort(nums);

int start = 0, end = 1, result = 0;
while (start < nums.length && end < nums.length) {
if (start == end || nums[start] + k > nums[end]) {
end++;
} else if (nums[start] + k < nums[end]) {
start++;
} else {
start++;
result++;
// start
//  |
// [1, 1, ...., 8, 8]
//              |
//             end
while (start < nums.length && nums[start] == nums[start - 1]) start++;
end = Math.max(end + 1, start + 1);
}
}
return result;
}
}
``````

• Thanks for share;
but code format is also important; your code is short, but it's hard to read.
moreover, it doesn't improve performance in any way, it cannot cheat compiler....

• @mycoy I was never selling myself by saying "my code is very short." I didn't claim this algorithm improve the performance either. What do you mean by "cheating the compiler"?

The code runs in `O(n log n)` time but occupies `O(1)` space. It is an in-place solution. In fact, though the solution has an `O(n log n)` runtime, it still performs well compared to many linear-time solutions using `HashMap` since

• insert/delete/lookup takes `O(1)` time only in an average case.
• the constant in `O(1)` is large.
• the overhead becomes much worse when a `HashMap` occupies more space, and this is exactly the case in LeetCode.

• Single layer of loop:

``````        if (k < 0) return 0;
Arrays.sort(nums);
int ans = 0;
for (int i = 0, j = 1; j < nums.length;) {
if (j <= i || nums[i] + k > nums[j]) {
j++;
} else if (i > 0 && nums[i] == nums[i - 1] || nums[i] + k < nums[j]) {
i++;
} else {
ans++;
i++;
}
}
return ans;
``````

• @lixx2100
the inner loops (for & while) can be optimized into a binary search (looking for nums[i]+k), since already sorted (from N to lgN reduction, total of NlgN)

• @shawn5 The inner loops takes amortized `O(1)` time. That is, except the presorting, the algorithm runs in linear time.

• Time complexity: O(k * n) or n * logn

``````public int findPairs(int[] nums, int k) {
int n = nums.length;
if(n < 2) return 0;
Arrays.sort(nums);
int s = 0, e = 1, res = 0;
while(s < e && e < n){
if(nums[e] - nums[s] < k) e++;
else{
if(nums[e] - nums[s] == k){
if(s == 0 || nums[s] != nums[s - 1]) res++;
}
s++;
if(s == e) e++;
}
}
return res;
}``````

• @liupangzi Brilliant !!!

• If we take Arrays.sort() into consideration, is the space complexity still O(1)?

• @indiroia Heap-sort can take `O(1)` space.

• ``````public int findPairs(int[] nums, int k) {
Arrays.sort(nums);

int left=0, right=1, count=0;
while(right<nums.length){
int diff = Math.abs(nums[right]-nums[left]);
if(diff==k){
count++;
// skip all duplicates at right pointer
while(++right<nums.length&&nums[right]==nums[right-1]);
}else if(diff<k){
right++;
}else{
//skip all duplicates at left pointer
while(++left<nums.length&&nums[left]==nums[left-1]);
right = left+1;
}
}

return count;
}``````

• @stevenli, Inspired by your solution, I wrote a different approach where we move either of the pointers just once. I don't like to move pointers with different steps in every iteration.

What do you think?

``````public int FindPairs(int[] nums, int k) {
Array.Sort(nums);
int diffCount = 0;
if(nums.Length == 0 || nums.Length == 1)
{
return diffCount;
}
int left = 0;
int right = 1;
while(right < nums.Length)
{
int diff = nums[right] - nums[left];
if(diff == k)
{
if(left == right - 1 || nums[right] != nums[right - 1])
{
diffCount++;
}
right++;
}
else if(diff > k)
{
left++;
if(right <= left)
{
right++;
}
}
else
{
right++;
}
}
return diffCount;
}``````

• straightforward solution with 2 pointer

``````class Solution {
public:
int findPairs(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
int ret = 0;

for(int i=0,j=1;i<nums.size() && j<nums.size();j=max(j,i+1))
{
if(nums[j]-nums[i]==k)
{
ret++;
while(i<nums.size()-1 && nums[i]==nums[i+1]) i++;
i++;
while(j<nums.size()-1 && nums[j] == nums[j+1]) j++;
j++;
}
else if(nums[j]-nums[i]>k)
{
while(i<nums.size()-1 && nums[i]==nums[i+1]) i++;
i++;
}

else
{
while(j<nums.size()-1 && nums[j] == nums[j+1]) j++;
j++;
}

}
return ret;

}
};``````

• Why the running time is O(N log N), could someone explain it?

• @Wanhui In the for loop, the running time is O(n), and Arrays.sort() takes O(nlogn), so the overall time complexity is O(nlogn).

• This post is deleted!

• @mycoy Totally agree with you!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.