Counting Elements

Counting Elements

What is this problem about?

The Counting Elements interview question asks you to count how many elements $x$ exist in an array such that $x + 1$ is also present in the same array. If there are duplicates of $x$, each instance is counted separately as long as $x + 1$ exists at least once.

Why is this asked in interviews?

This is an "Easy" Array interview pattern used by companies like DRW to test a candidate's familiarity with Hash Sets and basic lookup optimizations. It evaluates whether you can avoid O(n^2) nested loops by using O(1) average time lookups. It’s a basic test of algorithmic efficiency and data structure selection.

Algorithmic pattern used

The problem uses a Hash Set for O(1) Lookups.

1. Traverse the array once and add all elements to a Hash Set.
2. Traverse the array a second time.
3. For each element x, check if set.contains(x + 1).
4. If yes, increment your counter.

Example explanation

Array: [1, 2, 3, 1, 1]

1. Set: {1, 2, 3}.
2. Check elements:
   • 1: 1+1=2 is in set. Count = 1.
   • 2: 2+1=3 is in set. Count = 2.
   • 3: 3+1=4 is not in set.
   • 1: 1+1=2 is in set. Count = 3.
   • 1: 1+1=2 is in set. Count = 4. Total: 4.

Common mistakes candidates make

• Double Counting the Set: Adding counts from the Set instead of the original array. If the array is [1, 1, 2], the answer is 2 (two 1s have a 2), but if you iterate through the set, you'd only find one 1.
• Nested Loops: Using O(n^2) search, which is inefficient for large arrays.
• Off-by-one: Checking for x-1 instead of x+1 (depending on the problem phrasing).

Interview preparation tip

Always clarify if duplicates should be counted individually. In "Counting Elements," they usually are, which means you iterate over the original array for the count but use the set for the existence check.