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] <= 1000Problem 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.
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.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
PHP
| 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 |
Noob Software Engineer vs O(n) Swaggy Engineer on Counting Elements, Leetcode 1426 • Greg Hogg • 324,369 views views
Watch 9 more video solutions →Practice Counting Elements with our built-in code editor and test cases.
Practice on FleetCode