Problem Breakdown

Given an integer array arr, you need to determine how many elements x exist such that x + 1 is also present in arr. If there are duplicates of x, each occurrence should be counted separately.

Example 1:

Input: arr = [1, 2, 3]

Output: 2

Explanation: Both 1 and 2 are counted because 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 because there are no 2, 4, 6, or 8 in arr.

Example 3:

Input: arr = [1, 3, 2, 3, 5, 0]

Output: 3

Explanation: 0, 1, and 2 are counted because 1, 2, and 3 are in arr.

Example 4:

Input: arr = [1, 1, 2, 2]

Output: 2

Explanation: Both 1s are counted because 2 is in arr.

Approach

To solve this problem efficiently:

1. Use a HashSet: Store all unique elements of arr in a HashSet. This allows for O(1) average-time complexity checks to see if x + 1 exists in the array.
2. Iterate Through the Array: For each element x in arr, check if x + 1 is present in the HashSet. If it is, increment the count.

This approach ensures that we traverse the array once and perform constant-time checks for each element, leading to an overall time complexity of O(n), where n is the length of the array.

Java Solution

import java.util.HashSet;

public class Solution {
    public int countElements(int[] arr) {
        HashSet<Integer> set = new HashSet<>();
        int count = 0;

        // Add all elements to the HashSet
        for (int num : arr) {
            set.add(num);
        }

        // Count elements x such that x + 1 is also in the set
        for (int num : arr) {
            if (set.contains(num + 1)) {
                count++;
            }
        }

        return count;
    }
}

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the array. We traverse the array twice: once to populate the HashSet and once to count the elements.
• Space Complexity: O(n), due to the storage required for the HashSet.