title: Best way to find the number of pairs in an array whose difference is k
body: <p>I was solving the problem on hackerrank. I had two approaches in my mind :</p>
  
  <p>input : unsorted array(a) and k</p>
  
  <p><strong>First Approach :</strong></p>
  
  <p>1) Sort the array </p>
  
  <p>2) for each array element a[i] ,find the element a[i]+K using binary search.If found increament the count and break the inner loop.</p>
  
  <p><strong>Second Approach :</strong></p>
  
  <p>1) Sort the array </p>
  
  <p>2)  for each array element a[i] ,find the element a[i]+K using linearsearch.If found increament the count and break the inner loop.</p>
  
  <p>I found the First approach to be better as it will solve the problem in n(logn). But when multiple test cases are on the solutions the approach 2 takes lesser time . Can some one please explain why ? </p>
  
  <p>Below are the code for the two approaches :</p>
  
  <p><strong>First Approach Code :</strong> </p>
  
  <pre><code>static int pairs(int[] a,int k) {
    /* Complete this function */
      int temp;
      int len=a.length;
      int count=0;
      int beg;
      int mid;
      int end;
      int midVal;
      Arrays.sort(a);
      for(int i=0;i&lt;len-1;i++){
      temp=a[i]+k;
      beg=i+1;  
      end=len-1;
          for(int l=beg;l&lt;len;l++){
              mid=(beg+end)/2;
              midVal=a[mid];
              if(midVal==temp){
                  count++;
                  break;
              }
              else if(midVal&gt;temp){
                  end=mid-1;
              }
              else{
                  beg=mid+1;
              }
          }
  
      }
      return count;
  }
  </code></pre>
  
  <p><strong>Second Approach Code :</strong></p>
  
  <pre><code>static int pairs(int[] a,int k) {
    /* Complete this function */
      int temp;
      int len=a.length;
      int count=0;
      Arrays.sort(a);
      for(int i=0;i&lt;len;i++){
      temp=a[i];
          for(int j=i+1;j&lt;len;j++){
              if(temp-a[j]==-k){
                  count++;
                  break;
              }
          }
      }
      return count;
  }
  </code></pre>