Description

Given an integer array arr, count how many elements x there are, such that x + 1 is also in arr. If there are duplicates in arr, count them separately.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= arr.length <= 1000
  • 0 <= arr[i] <= 1000

Solution

This problem can be solved in multiple ways. The easiest intuition is to use sorting followed by checking each elements one after another.

1. Using Sorting

In this approach, we first sort the array in ascending order. Next, we iterate through all elements one by one with two pointers, checking if the next number is just one greater than previous number. If not, increase index position one step. In this case, we use count += right - left. This is because if we have numbers such as [1, 1, 2], then we have to count count = 2 for each 1. If we were not given condition to count them separately, we could simply use count += 1.

 1class Solution {
 2    public int countElements(int[] arr) {
 3        Arrays.sort(arr);
 4        int count = 0;
 5        int left = 0;
 6        int right = 1;
 7        while (right < arr.length) {
 8            // If both equal then increase right
 9            if (arr[left] == arr[right]) {
10                right++;
11            } else if (arr[left] + 1 == arr[right]) {
12                count += right - left; // This is to cover cases like [1 1 2] where we need to count 1 twice
13                left = right;
14                right++;
15            } else {
16                left = right;
17                right++;
18            }
19        }
20        return count;
21    }
22}
  • Time Complexity: O(n log n)
  • Space Complexity: This depends on the sorting algorithm used, it can be O(1) to O(n).

2. Using Array

In this problem, we know that each of the number is between 0 and 1000. So, we can create an array of size 1001 to accommodate all elements of the array based on their index position. This will require creating new array of fixed size. Next, we iterate through each element of the original array arr and check if there is an element at position num + 1 in the newly created array. If it has a value other than default value, that means x + 1 is available for current number x and we increment the count. At the end, we return this count.

 1class Solution {
 2    public int countElements (int[] arr) {
 3        int count = 0;
 4        int[] result = new int[1001];
 5        for (int i = 0; i < arr.length; i++) {
 6            result[arr[i]] = 1;
 7        }
 8
 9        for (int i = 0; i < arr.length; i++) {
10            if (result[arr[i] + 1] == 1)
11                count++;
12        }
13        return count;
14    }
15}
  • Time Complexity: O(n)
  • Space Complexity: Realistically looking, we creating array of size 1001 which is fixed. so, it has space complexity of O(1).

3. Using Hashing

Third approach is to store all elements in a HashSet or HashMap. Next, iterate through each element x of the input array arr and check if the x + 1 exists in HashMap or HashSet. If it exists, increment the count else move to next element in the array.

 1class Solution {
 2    public int countElements(int[] arr) {
 3        int count = 0;
 4        Set<Integer> set = new HashSet<>();
 5        for (int num: arr) {
 6            set.add(num);
 7        }
 8
 9        for (int num: arr) {
10            if (set.contains(num + 1))
11                count++;
12        }
13        return count;
14    }
15}
  • Time Complexity: O(n)
  • Space Complexity: O(n)