Counting Elements
Description
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 because 2 and 3 are in arr. (1+1=2 exists, 2+1=3 exists, 3+1=4 does not exist)
Example 2:
Input: arr = [1, 1, 3, 3, 5, 5, 7, 7]
Output: 0
Explanation: No numbers are counted because there is no 2, 4, 6, or 8 in arr. Each element needs its successor to be present.
Example 3:
Input: arr = [1, 1, 2, 2]
Output: 2
Explanation: Both 1s are counted because 2 is in arr. The 2s are not counted because 3 is not in arr.
Constraints
1 <= arr.length <= 10000 <= arr[i] <= 1000
Complexity
Show Complexity
- Time:
O(n) - Space:
O(n)
Hints
Show Hints
- Pattern
- Hash set for O(1) lookup
- Approach
- Create a set of all elements. For each element x in array, if x+1 is in set, increment count.
- Complexity
- Store all elements in a set, then iterate and count
Solutions
Show PY Solution
def solution(arr: list[int]) -> int:
m = {}
for i in range(len(arr)):
v = arr[i]
if v in m:
m[v] += 1
else:
m[v] = 1
result = 0
for v, c in m.items():
if v + 1 in m:
result += c
return result