Counting Elements

How it works

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.

Steps

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.

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.

Things to watch for

Checking for x - 1 Instead of x + 1

The problem asks to count elements x where x + 1 exists in the array. A common mistake is checking for x - 1 instead, which counts elements that have a predecessor rather than a successor.

Counting Unique Values Instead of All Occurrences

The problem asks to count every element x where x + 1 exists, including duplicates. Using a set for counting instead of iterating through the original array will miss duplicate elements.

from typing import List

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

class Solution {
public:
    int countElements(vector<int>& arr) {
        std::sort(arr.begin(), arr.end());
        int count = 0;
        int runLength = 1;
        for (int i = 1; i < arr.size(); i++) {
            if (arr[i - 1] != arr[i]) {
                if (arr[i - 1] + 1 == arr[i]) {
                    count += runLength;
                }
                runLength = 0;
            }
            runLength++;
        }
        return count;
    }
};