Pairs having Similar Elements

Question

Given an array, A, having N integers A1, A2,..., An.Two elements of the array Ai and Aj are called similar iff Ai =Aj +1 or Aj= Ai +1 Also, the similarity follows transitivity. If Ai and Aj are similar and Aj and Ak are similar, then Ai and Ak are also similar. Below is my code with More Time Complexity, How can we decrease it?

def SimilarElementsPairs (A,N):
  # Write your code here
  count=0
  map1=[]
  for i in range(0,N):
      for j in range(0,N):
          if((A[i]==A[j]+1) or (A[j]==A[i]+1)):
                  count+=1
                  map1.append((i,j))
          for k in range(0,N):
              if((((A[i]==A[j]+1) or (A[j]==A[i]+1)) and ((A[k]==A[j]+1) or (A[j]==A[k]+1))))  :
                  count+=1
                  map1.append((i,k))
              if((((A[i]==A[j]+1) or (A[j]==A[i]+1)) and ((A[j]==A[k]+1) or (A[k]==A[j]+1)))):
                  count+=1
                  #map1.append((i,k))
              if((((A[i]==A[j]+1) or (A[j]==A[i]+1)) and ((A[k]==A[i]+1) or (A[i]==A[k]+1)))):
                  count+=1
                  map1.append((j,k))
  list1 = set(map(lambda x: tuple(sorted(x)),map1))
  list2=[]
  for x,y in list1:
      if abs(x-y)>0:
          list2.append((x,y))
  return len(list2)

N = input()
A = map(int, raw_input().split())
out_ = SimilarElementsPairs(A,N)
print out_

Answer 1

Main Logic

static long SimilarElementsPairs(int[] arr, int n){
        Arrays.sort(arr);
        long sCount=1;               //to know the count of total elements
        long dCount=1;               //to know if any pair is found
        long ans=0;

        for (int i=1; i<n; i++){
            if (arr[i]==arr[i-1]+1)
            {
                sCount++;
                dCount++;
            }
            else if(arr[i]==arr[i-1])
            {
                sCount++;
            }
            else
            {
                if (sCount>=2 && dCount>=2)
                {
                    ans+=((sCount)*(sCount-1))/2;
                }
                sCount=1;
                dCount=1;
            }
        }
        if (sCount>=2 && dCount>=2){
            ans+=((sCount)*(sCount-1))/2;
        }

        return ans;
}

So @Mohammad_Zeineldeen method is almost correct but we need to look for the same elements in the problem and therefore what I have done in the above method is a similar approach to his answer but I have also kept the number of same elements.

Another method which can work for is using HashMap to keep the total count of an element and when a pair(a[i] & a[i-1]) is found then add that total count of a[i-1] + NC2(Combination) where N is total Count of a[i-1].

Ex: In 7 7 8 -> when index arrives at 8 then it will check for pair element and will found one as (a[i]-a[i-1]==1) and as there are two 7 so pairs which will be formed are : (7,8) and (7,8) keep in mind that they are not same as their index are different and another pair which will be formed will be (7,7) by transitivity which is also equal to NC2(i.e 2C2 -> 1), hence and for this will be 3.