C++ MULTIPLE APPROACHES : MAPS / TWO POINTER
Hi , This problem is pretty straightforward . Let me explain the problem first. \n##### EXPLANATION : \nThe problem says that we are provided with an array of i
Hi , This problem is pretty straightforward . Let me explain the problem first. \n##### EXPLANATION : \nThe problem says that we are provided with an array of integers and we have to find out the ***Count of unique pairs*** in the array such that the ***absolute difference of elements of the pair is ==k.***\nMathematically , find the **count of unique pairs ( nums[i], nums[j] )** such that ,\n* *0 <= i < j < nums.length*\n* *|nums[i] - nums[j]| == k*\n\n##### SOLUTION : \nIt is pretty clear that in order to obtain the answer , we have to find all pairs the array which have an absolute difference of \'k\' and then eliminate those which are not unique.\n\nThere are multiple ways to achieve that. \n\n#### 1. USING MAPS : \nWe are aware of the fact that for a pair to be counted as an answer , **both the elements ( x and x+k ) , need to be in the array**. \nSo we simply **create a map and store the frequency** of each element in the map. \nNow we traverse the map and for **each element \'x\'** , we **check if \'x+k\' exists in the map** . If it does , then it means **a unique pair can be formed** and hence, we **increment the answer**. \n##### EDGE CASE : \nThe only edge case is the situation where**k=0**. If k=0 , instead of finding \'x+k\' , we **check if the frequency of \'x\'>1**. If it is , then we**increment the answer** . \nElse , we don\'t **increment the answer , as the frequency of x=1 and hence it can\'t form a pair with itself**.\n\n##### CODE : \n```\nclass Solution {\npublic:\n    int findPairs(vector<int>& nums, int k) {\n        unordered_map<int,int> a;\n        for(int i:nums)\n            a[i]++;\n        int ans=0;\n        for(auto x:a)\n        {\n            if(k==0)\n            {    \n                if(x.second>1)\n                ans++;\n            }\n             else if(a.find(x.first+k)!=a.end())\n                ans++;\n        }\n        \n        return ans;\n    }\n};\n```\n**TIME COMPLEXITY : O(N)**\n**SPACE COMPLEXITY : O(N)**\n\n\n#### 2. USING TWO POINTERS : \nWe are aware of the fact that for a pair to be counted as an answer , **both the elements ( x and x+k ) , need to be in the array.** \nIn this approach , **first we sort the array** and maintain 2 pointers. \n* *1st Pointer --> 1st Element of the Pair*\n* *2nd Pointer --> 2nd Element of the Pair*\n\nWe set the 1st pointer at the 0th index and 2nd pointer at the 1st index. Then , \n1. Move the 2nd pointer until **2nd pointer - 1st pointer >=k** . \n2. If the **2nd pointer - 1st pointer ==k** , then **increment the answer and move the 2nd pointer to the next greater element.**   \n3. Move the **1st pointer to the next greater element**. \n\nFollow the above procedure until **the 2nd pointer reaches the end of the array**.\n\n##### CODE : \n```\nclass Solution {\npublic:\n    int findPairs(vector<int>& nums, int k) {\n        sort(nums.begin(),nums.end());\n        int ans=0,i=0,j=1;\n        for(i,j;i<nums.size() and j<nums.size();)\n        {\n            if(i==j or nums[j]-nums[i]<k)\n                j++;\n            else \n            {\n                if(nums[j]-nums[i]==k)\n                {\n                    ans++;\n                    j++;\n                    for(;j<nums.size();j++)\n                        if(nums[j]!=nums[j-1])\n                            break;\n                    if(j==nums.size())\n                    return ans;\n                    j--;                  \n                }\n                i++;\n                while(i<j and nums[i]==nums[i-1])\n                    i++;\n            }\n        }\n        return ans;\n    }\n};\n```\n**TIME COMPLEXITY : O(NlogN)**\n**SPACE COMPLEXITY : O(1)**\n\n**NOTE : The 2nd approach doesn\'t need to deal with the EDGE CASE mentioned in the 1st approach as , in the 2nd approach after finding a pair , we immediately move to the next greater element.**\n\nIf you found this post helpful , do upvote. \n
['C', 'C++']