1426. Counting Elements

EasyArrayHash Table

Problem Description

The problem provides an integer array called arr. We are asked to count the number of elements, x, in this array such that there exists another element in the array which is exactly one more than x (that is, x + 1). If there are multiple instances of the same value in arr, each occurrence should be considered separately for our count.

An example to illustrate the problem could be if we have the array [1, 2, 3]. Here, the element 1 has a companion 2, and 2 has a companion 3. Thus, we have two elements (1 and 2) that meet the condition, so our result would be 2.

Intuition

To find an efficient solution to the problem, we realize that checking for the presence of x + 1 for each element x can be made faster by using a set. A set is a data structure that allows for O(1) look-up times on average, meaning we can quickly determine if x + 1 exists in our array.

Here's how we can break down the solution:

Create a Set: Convert the list arr into a set s. This allows for rapid look-ups and also removes any duplicate values, which we don't need to consider since we're counting duplicates separately anyway.
Count with a Condition: We go through each element x in the original array arr and check if x + 1 exists in our set s.
Sum the Counts: By summing the boolean results of the check (since True equates to 1 and False to 0 in Python), we get a count of how many times the condition is met across our array.

The solution's beauty lies in its simplicity and efficiency, transforming the problem into a series of O(1) look-up operations that result in the final count.

Solution Approach

The Reference Solution Approach uses simple yet effective programming techniques and takes advantage of Python's built-in data structures.

Here's a step-by-step explanation of how the code works:

Convert to Set: The first step in the countElements method involves creating a set s from the input list arr.
```
s = set(arr)
```
Sets in Python are implemented as hash tables, which is why we get excellent average-case time complexity for look-up operations.
Iteration and Element Check: Next, we iterate over the elements in the original array arr. For each element x, we check if x + 1 is present in the set s.
```
sum(x + 1 in s for x in arr)
```
The expression x + 1 in s is a boolean check that returns True if the element x + 1 exists in the set s, and False otherwise.
Summing the True Counts: The sum function in Python adds up all the items in an iterable. Since True is counted as 1 and False as 0, this line effectively counts all instances where x + 1 is found in the set:
```
return sum(x + 1 in s for x in arr)
```
Each time the check is True, it adds 1 to our running total. When it's False, it adds nothing. The final result is the number of elements that meet the condition, which the function returns.

The algorithm could be classified as a counting algorithm, which is commonly used to solve problems where we are asked to count occurrences of certain conditions or items that meet specific criteria.

In summary, the solution hinges on the constant-time look-up properties of sets in Python and the use of a generator expression within the sum function to iterate and tally our count efficiently.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let us consider a small example to illustrate the solution approach. Suppose we have an array arr = [3, 1, 2, 3]. We want to count the number of elements in this array for which the element plus one also exists.

First, we convert the input list arr into a set s.
```
s = set(arr)  # Now s is {1, 2, 3}
```
By converting the list into a set, we can check for the existence of x + 1 in constant time.
We now iterate over each element x in the original array arr and use a boolean check to see if x + 1 exists in the set s. For x = 3: x + 1 is 4, which does not exist in set s. For x = 1: x + 1 is 2, which exists in set s. For x = 2: x + 1 is 3, which exists in set s. For the second occurrence of x = 3, the result is the same as the first time: x + 1 is 4, which does not exist in set s.

We sum the boolean results:

return sum(x + 1 in s for x in arr)  # Evaluates to sum([False, True, True, False]) which is 0 + 1 + 1 + 0 = 2

Each True result adds 1 to the count. In this case, there are two instances where x + 1 exists in our set; hence, the sum is 2.

Given this example, the function countElements would return 2, as 1 and 2 have companions 2 and 3, respectively. Each occurrence is treated separately, even though 3 appears twice, since 3 + 1 is not in the array, those occurrences do not contribute to our count.

Solution Implementation

1class Solution:
2    def countElements(self, nums: List[int]) -> int:
3        # Create a set from the list for O(1) lookups
4        unique_elements = set(nums)
5      
6        # Count the elements that have an immediate consecutive successor in the set
7        count = sum(1 for num in nums if num + 1 in unique_elements)
8      
9        # Return the total count of such elements
10        return count
11

1class Solution {
2    public int countElements(int[] arr) {
3        // A set to store the unique elements from the array
4        Set<Integer> uniqueElementsSet = new HashSet<>();
5
6        // Adding each element from the array to the set
7        // Duplicate elements will not be added to a set, ensuring uniqueness
8        for (int num : arr) {
9            uniqueElementsSet.add(num);
10        }
11
12        // Counter to keep track of the number of elements that satisfy the condition
13        int count = 0;
14
15        // Iterating through the array to check if the element's consecutive number is in the set
16        for (int num : arr) {
17            if (uniqueElementsSet.contains(num + 1)) {
18                // Increment the counter if the set contains the consecutive number
19                ++count;
20            }
21        }
22
23        // Returning the count of elements that satisfy the condition
24        return count;
25    }
26}
27

1#include <vector>
2#include <unordered_set>
3using namespace std;
4
5class Solution {
6public:
7    int countElements(vector<int>& arr) {
8        // Create an unordered_set to hold unique elements for fast lookup.
9        unordered_set<int> uniqueElements(arr.begin(), arr.end());
10      
11        int count = 0; // Initialize the counter for the elements that match the criteria.
12
13        // Iterate over the array to count elements such that the element + 1 is also in the array.
14        for (int element : arr) {
15            // If the set contains (element+1), increment the counter.
16            count += uniqueElements.count(element + 1);
17        }
18
19        return count; // Return the total count of elements meeting the criteria.
20    }
21};
22

1/**
2 * Function to count the elements in an array where each element `x` has another element `x+1`.
3 * @param arr - An array of number elements.
4 * @return The count of elements that satisfy the condition.
5 */
6function countElements(arr: number[]): number {
7    // Initialize a new Set to store unique elements.
8    const uniqueElements = new Set<number>();
9
10    // Add each element of the array to the Set to ensure uniqueness.
11    for (const element of arr) {
12        uniqueElements.add(element);
13    }
14
15    // Initialize the answer variable to store the final count.
16    let count: number = 0;
17
18    // Iterate over the array to find elements where `element + 1` exists in the Set.
19    for (const element of arr) {
20        if (uniqueElements.has(element + 1)) {
21            // Increment the count if such an element is found.
22            count++;
23        }
24    }
25  
26    // Return the final count.
27    return count;
28}
29
30// Example usage in TypeScript:
31// const result = countElements([1, 2, 3]); // result should be 2
32

Time and Space Complexity

The provided code snippet defines a function countElements that counts the number of elements in an array where the element plus one is also in the array.

Time Complexity

The time complexity of the function is O(n). This efficiency is due to two separate operations that each run in linear time relative to the number of elements, n, in the input array arr:

s = set(arr): Transforming the list to a set has a time complexity of O(n) because each of the n elements must be processed and inserted into the set.
sum(x + 1 in s for x in arr): The sum function iterates over all elements x in arr once, performing a constant-time check x + 1 in s to see if x + 1 exists in the set. Since set lookups are O(1), and there are n elements, this operation is also O(n).

Therefore, the overall time complexity is the sum of the two operations, which remains O(n).

Space Complexity

The space complexity of the function is O(n). This is determined by the size of the set s that is created from the input array. In the worst case, if all elements in arr are unique, the set will contain n elements, leading to a space complexity of O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls