1. Search with Array

Intuition

For each element x in the array, we need to check whether x + 1 also exists in the array. The straightforward approach is to scan through the entire array for each element to verify if its successor is present. While this works correctly, it requires a linear search for every element.

Algorithm

1. Initialize a counter to 0.
2. For each element x in the array, iterate through the array to check if x + 1 exists.
3. If x + 1 is found, increment the counter.
4. Return the final count.

class Solution:
    def countElements(self, arr: List[int]) -> int:
        count = 0
        for x in arr:
            if x + 1 in arr:
                count += 1
        return count

Time & Space Complexity

• Time complexity: $O(N^2)$
• Space complexity: $O(1)$ constant space

Where $N$ is the length of the input array arr.

---

2. Search with HashSet

Intuition

The brute force approach is slow because checking if x + 1 exists requires scanning the entire array. A hash set provides O(1) lookup time, so we can first store all elements in a set, then check for each element's successor in constant time.

Algorithm

1. Insert all elements from the array into a hash set.
2. Initialize a counter to 0.
3. For each element x in the array, check if x + 1 exists in the hash set.
4. If it does, increment the counter.
5. Return the final count.

class Solution:
    def countElements(self, arr: List[int]) -> int:
        hash_set = set(arr)
        count = 0
        for x in arr:
            if x + 1 in hash_set:
                count += 1
        return count

Time & Space Complexity

• Time complexity: $O(N)$
• Space complexity: $O(N)$

Where $N$ is the length of the input array arr.

---

3. Search with Sorted Array

Intuition

Sorting brings equal elements together and places consecutive values next to each other. After sorting, we can traverse the array once and track "runs" of identical values. When we encounter a new value that is exactly one more than the previous value, all elements in the previous run satisfy the condition.

Algorithm

1. Sort the array.
2. Initialize a counter and a run length tracker (starting at 1).
3. Iterate through the sorted array starting from index 1.
4. If the current element differs from the previous one:
   • If the current element equals the previous element plus 1, add the run length to the counter.
   • Reset the run length to 0.
5. Increment the run length for each element processed.
6. Return the final count.

class Solution:
    def countElements(self, arr: List[int]) -> int:
        arr.sort()
        count = 0
        run_length = 1
        for i in range(1, len(arr)):
            if arr[i - 1] != arr[i]:
                if arr[i - 1] + 1 == arr[i]:
                    count += run_length
                run_length = 0
            run_length += 1
        return count

Time & Space Complexity

• Time complexity: $O(N \log N)$
• Space complexity: varies from $O(N)$ to $O(1)$
  • The overall space complexity is dependent on the space complexity of the sorting algorithm you're using. The space complexity of sorting algorithms built into programming languages are generally anywhere from $O(N)$ to $O(1)$.

Where $N$ is the length of the input array arr.