Problem Description

The "Counting Elements" problem asks you to process an array of integers, called arr. For every element x in arr, you need to check if x + 1 also exists in the array. If so, you count x as a valid element. Your goal is to return the total number of such valid elements in the array.

• You must count each occurrence of x separately, even if there are duplicates.
• Elements can be reused as both x and x + 1 in different checks.
• There is always at least one valid solution for the given constraints.

Example: If arr = [1,2,3], then both 1 (since 2 exists) and 2 (since 3 exists) are counted, so the answer is 2.

Thought Process

The first thing to notice is that for each number x in the array, we need to check if x + 1 is present somewhere in the array. A straightforward way is to use two nested loops: for each element, loop through the array again to see if x + 1 is present. However, this approach is slow for large arrays.

To optimize, we realize that if we can check for the existence of x + 1 in constant time, we can process the array much faster. This leads us to use a set or hash map, which allows for O(1) lookups. By storing all elements in a set first, we can quickly check if x + 1 exists for any x.

This is a classic example of trading extra memory (for the set) to gain speed in lookups, turning a brute-force O(n^2) approach into an efficient O(n) solution.

Solution Approach

Here’s how to solve the problem step by step:

1. Store all unique elements in a set: This allows us to check if x + 1 exists in constant time for any x.
2. Iterate through the array: For each element x, check if x + 1 is present in the set.
3. Count valid elements: If x + 1 is found, increment a counter. Since duplicates are allowed, we check each occurrence separately.
4. Return the count: After processing all elements, return the total count.

We use a set for O(1) lookups, which makes the algorithm efficient even for large arrays.

Example Walkthrough

Let's walk through the process with an example: arr = [1, 1, 2, 3].

• Step 1: Create a set from the array: {1, 2, 3}
• Step 2: Iterate through each element:
  • First 1: Check if 2 is in the set. Yes! Count = 1.
  • Second 1: Again, 2 is in the set. Count = 2.
  • 2: Check if 3 is in the set. Yes! Count = 3.
  • 3: Check if 4 is in the set. No. Count remains 3.
• Step 3: The answer is 3.

This approach ensures that every occurrence is counted if its x + 1 exists.

Time and Space Complexity

• Brute-force approach: O(n^2) time, since for each element you scan the entire array again. Space is O(1) extra.
• Optimized approach: O(n) time, because:
  • Building the set takes O(n) time.
  • Iterating through the array and checking set membership is O(1) per element, so another O(n).

  Space complexity is O(n) due to the set storing all unique elements.

Summary

By leveraging a set for fast lookups, we efficiently count all elements x in the array such that x + 1 also appears. This method transforms a potentially slow brute-force solution into a quick and elegant algorithm, suitable for large inputs and repeated values.

Code Implementation

class Solution:
    def countElements(self, arr):
        s = set(arr)
        count = 0
        for x in arr:
            if x + 1 in s:
                count += 1
        return count
      

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int countElements(vector<int>& arr) {
        unordered_set<int> s(arr.begin(), arr.end());
        int count = 0;
        for (int x : arr) {
            if (s.count(x + 1)) {
                count++;
            }
        }
        return count;
    }
};
      

import java.util.HashSet;

class Solution {
    public int countElements(int[] arr) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : arr) {
            set.add(num);
        }
        int count = 0;
        for (int num : arr) {
            if (set.contains(num + 1)) {
                count++;
            }
        }
        return count;
    }
}
      

/**
 * @param {number[]} arr
 * @return {number}
 */
var countElements = function(arr) {
    const s = new Set(arr);
    let count = 0;
    for (let x of arr) {
        if (s.has(x + 1)) {
            count++;
        }
    }
    return count;
};