1. K-diff Pairs in an Array

Problem Statement

Given an integer array nums and an integer k, return the number of unique k-diff pairs in the array.

A k-diff pair is a pair (nums[i], nums[j]) such that |nums[i] - nums[j]| == k.

Pattern Used

Two Pointers / Hashing

Approach (High-level)

• Brute Force (commented):

  Check all pairs and store unique valid pairs

• Two Pointer (used):

  Sort the array, use two pointers to find pairs with difference k, and ensure uniqueness

Time & Space Complexity

• Brute Force: O(n²) time, O(n) space
• Two Pointer: O(n log n) time, O(1) space

LeetCode

• 532. K-diff Pairs in an Array
• https://leetcode.com/problems/k-diff-pairs-in-an-array/

//Two pointer approch:-
class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());  
        set<pair<int, int>> ans;
        int i = 0, j = 1;   
        while (j < nums.size()) {
            int diff = nums[j] - nums[i];
            
            if (diff == k) {
                ans.insert({nums[i], nums[j]});
                ++i, ++j;
            }
            else if (diff > k) {
                ++i;
            }
            else {
                ++j;
            }
            if (i == j) {
                ++j;
            }
        }       
        return ans.size();
    }
};

//Binary Search approch:-
class Solution {
public:

    int bs(vector<int>& nums, int start,int x){
        int end=nums.size()-1;
         while(start<=end){
            int mid = start+(end-start)/2;
            if(nums[mid]==x){
               return mid;
            }else if(x>nums[mid]){
                start=mid+1;
            }else{
                end=mid-1;
            }
        }
        return -1;
    }
    int findPairs(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        set<pair<int,int>> ans;
        int n = nums.size(); 
        
        for(int i=0;i<n;i++){
            if(bs(nums,i+1,nums[i]+k)!=-1){
                ans.insert({nums[i],nums[i]+k});
            }
        }
        
        return ans.size();
        
    }
};

2. Find K Closest Elements

Problem Statement

Given a sorted integer array arr and two integers k and x, return the k elements that are closest to x.