Counting Elements - Video Solutions

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.