Counting Elements - Solution & Explanation
Problem Statement
Given an integer array arr, count how many elements x there are, such that x + 1 is also in arr. If there are duplicates in arr, count them separately.
Example 1:
Input: arr = [1,2,3] Output: 2 Explanation: 1 and 2 are counted cause 2 and 3 are in arr.
Example 2:
Input: arr = [1,1,3,3,5,5,7,7] Output: 0 Explanation: No numbers are counted, cause there is no 2, 4, 6, or 8 in arr.
Constraints:
1 <= arr.length <= 10000 <= arr[i] <= 1000
Approach Overview
Problem Overview: You are given an integer array arr. Count how many elements x have another element x + 1 also present in the array. The element x is counted for each occurrence, even if duplicates exist.
Approach 1: Brute Force Check (O(n^2) time, O(1) space)
Iterate through every element x in the array and scan the entire array again to check if x + 1 exists. For each element, run a second loop comparing values. If a match is found, increment the count. This approach uses no additional data structures, but the nested iteration makes it quadratic. It works for small inputs but quickly becomes slow as n grows.
Approach 2: Sorting + Linear Scan (O(n log n) time, O(1) extra space)
Sort the array first, then scan it from left to right. For each element, check if the next element equals current + 1. Because duplicates can exist, you may need to track frequencies or handle repeated values carefully. Sorting groups numbers together and allows faster comparisons than brute force, but the sorting step dominates the runtime. This approach relies on ordering rather than extra memory.
Approach 3: Hash Set Counting (O(n) time, O(n) space)
Insert all elements into a hash set for constant-time membership checks. Then iterate through the original array and check whether x + 1 exists in the set. If it does, increment the counter. Each lookup is O(1) on average, so the entire algorithm runs in linear time. This method uses a hash table to eliminate repeated scans of the array.
The key insight is that you only need to know whether the successor value exists, not its position. A set or frequency map makes this lookup constant time. This pattern appears frequently in problems involving presence checks within an array.
Recommended for interviews: The hash set approach is the expected solution. It demonstrates that you recognize when a presence check can be optimized with a hash table. Mentioning the brute force method first shows baseline reasoning, but implementing the O(n) set-based solution shows strong problem-solving instincts and familiarity with common array lookup patterns.
Solution
We can use a hash table or array cnt to record the frequency of each number in the array arr. Then, we traverse each number x in cnt. If x+1 also exists in cnt, we add cnt[x] to the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array arr.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
PHP
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Double Loop | O(n^2) | O(1) | Useful for understanding the basic requirement or when constraints are extremely small |
| Sorting + Linear Scan | O(n log n) | O(1) | When modifying the array is allowed and you prefer avoiding extra hash memory |
| Hash Set Counting | O(n) | O(n) | Best general solution with fast membership checks |
Video Solution
LeetCode 30 day Challenge | Day 7 | Counting Elements | LeetCode #1426 • Knowledge Center • 10,237 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Counting Elements easy or hard?
Counting Elements Python/Java solution
How to solve Counting Elements in O(n)?
What is the best approach for Counting Elements?
Is Counting Elements asked at Google/Amazon/Meta?
What data structure is used in Counting Elements?
What is the time complexity of Counting Elements?
Ready to solve this problem?
Practice Counting Elements with our built-in code editor and test cases.
Practice on FleetCode