Counting Elements - Leetcode Solution

Problem:

Given an integer array arr, count how many elements x there are, such that x + 1 is also in arr.

If there're 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's no 2, 4, 6, or 8 in arr.

Example 3:

Input: arr = [1,3,2,3,5,0] Output: 3 Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

Example 4:

Input: arr = [1,1,2,2] Output: 2 Explanation: Two 1s are counted cause 2 is in arr.

Constraints:

1 <= arr.length <= 1000 0 <= arr[i] <= 1000

Solution:

We can solve this problem using a hashset. We can add all the elements of the array to the hashset. Then we can iterate through the array and check if the current element + 1 is in the hashset. If it is, we increment our count by 1. We also remove the current element from the hashset to avoid counting duplicates. Finally, we return our count.

Here's the Python code:

class Solution: def countElements(self, arr: List[int]) -> int: count = 0 hashset = set(arr) for num in arr: if num + 1 in hashset: count += 1 hashset.remove(num) return count

Time Complexity:

The time complexity of this solution is O(n) because we are iterating through the array only once.

Space Complexity:

The space complexity of this solution is O(n) because we are using a hashset of size n to store the elements of the array.

1