Leetcode Counting Elements problem

Problem:

Given an integer array arr, count element x such that x + 1 is also in arr.

If there’re duplicates in arr, count them separately.

Example 1:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

Method 1: Time complexity O(nlogn)
1.sort the array. [log(n) time]
2. create one more array which stores the x+1 values in it. [n time]
3.Binary search in arr with x+1 val array if found count++ [log n time]

Code

public int countElements(int[] arr) {
   int n = arr.length;
   int count = 0;
   int[] plusOne = new int[n];
 //1.Sorting array
   Arrays.sort(arr);
 //2.creating x+1 array
   for(int i=0;i<n;i++){
     plusOne[i] = arr[i]+1;
 } 
 
 for(int i=0;i<n;i++){
   int key = plusOne[i];
 //3.searching the x+1 value present or not
   int index = Arrays.binarySearch(arr,key);
 // System.out.println(“index”+index);
   if(index>=0){
     count++;
   }
 
 }
 
   return count;
 }

Method 2: Time complexity O(n)
1.creating set and adding elements into it [n time]
2.scan through arr[i]+1 and check if set contains then count++[n time]
Explanation
As contains() method of HashSet takes O(1) time hence it is more optimal than method 1

Code

public int countElements(int[] arr) {
    int n = arr.length;
    int count = 0;
    int[] plusOne = new int[n];
 //1.creating hashset and adding vals into it
    HashSet<Integer> h = new HashSet<>();
    for(int i=0;i<n;i++){
       h.add(arr[i]);
    }
 //2. checking x+1 value is present into hashset
    for(int i=0;i<n;i++){
       if(h.contains(arr[i]+1))
          count++;
    }
   return count;
 }