Two-pointer Approach


  • 17
    L

    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;
    }
    

  • 20

    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;
        }
    }
    

  • 8
    M

    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....


  • 3
    L

    @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.

  • 13
    I

    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;
    

  • -1
    S

    @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)


  • 2
    L

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


  • 3

    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; 
    }

  • 0

    @liupangzi Brilliant !!!


  • 1

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


  • 0
    L

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


  • 3
    S
    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;
    }

  • 0
    A

    @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;
    }

  • 0
    S

    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;
            
        }
    };

  • 0
    W

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


  • 1

    @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).


  • 0
    L
    This post is deleted!

Log in to reply
 

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