💬 Discord
Sign In
NeetCode #16LC-1426EasyArrays & HashingNC Algo100
← Back to All Problems

#16 · #1426 · Counting Elements(数元素)

📌 Problem Statement & Constraints

Given an integer array arr, count how many elements x exist such that x + 1 is also present in arr. If duplicates of x exist, count each of them. Constraints: 1 <= arr.length <= 1000, 0 <= arr[i] <= 1000.

💡 Core Algorithmic Approaches

  1. The question is a membership test, so a hash set of the array gives O(1) lookups.
  2. Iterate the original array (not the set), because duplicates must each be counted.
  3. For each x, add 1 to the answer if x + 1 is in the set.
  4. Using the set as the iteration source would undercount duplicates -- a subtle but common slip.

💻 Benchmark Python3 Implementation

class Solution:
    def countElements(self, arr: List[int]) -> int:
        s = set(arr)
        return sum(1 for x in arr if x + 1 in s)   # iterate arr, not s

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to build the set, one pass to count.
💾 Space Complexity
O(n) for the set. A sort-based solution would be O(n log n) time with O(1) extra space.

⚠️ Interview Pitfalls & Follow-ups

  • Iterating the set instead of the array: [1, 1, 2] should count both 1s, giving 2; iterating the set yields only 1.
  • Checking x - 1: the problem asks about x + 1.
  • Forgetting that arr[i] can be 0: 0 + 1 = 1 is a valid lookup, no special case needed.