1426. Counting Elements
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 sets
. 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 arrayarr
and check ifx + 1
exists in our sets
. -
Sum the Counts: By summing the boolean results of the check (since
True
equates to1
andFalse
to0
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 sets
from the input listarr
.1s = 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 elementx
, we check ifx + 1
is present in the sets
.1sum(x + 1 in s for x in arr)
The expression
x + 1 in s
is a boolean check that returnsTrue
if the elementx + 1
exists in the sets
, andFalse
otherwise. -
Summing the True Counts: The
sum
function in Python adds up all the items in an iterable. SinceTrue
is counted as1
andFalse
as0
, this line effectively counts all instances wherex + 1
is found in the set:1return sum(x + 1 in s for x in arr)
Each time the check is
True
, it adds1
to our running total. When it'sFalse
, 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 EvaluatorExample 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 sets
.1s = 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 arrayarr
and use a boolean check to see ifx + 1
exists in the sets
. Forx = 3
:x + 1
is4
, which does not exist in sets
. Forx = 1
:x + 1
is2
, which exists in sets
. Forx = 2
:x + 1
is3
, which exists in sets
. For the second occurrence ofx = 3
, the result is the same as the first time:x + 1
is4
, which does not exist in sets
. -
We sum the boolean results:
1return 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 adds1
to the count. In this case, there are two instances wherex + 1
exists in our set; hence, the sum is2
.
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 ofO(n)
because each of then
elements must be processed and inserted into the set. -
sum(x + 1 in s for x in arr)
: The sum function iterates over all elementsx
inarr
once, performing a constant-time checkx + 1 in s
to see ifx + 1
exists in the set. Since set lookups areO(1)
, and there aren
elements, this operation is alsoO(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.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.