Problem

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.

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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 <= 1000
  • 0 <= arr[i] <= 1000

Solution

Method 1 – Hash Set Lookup

Intuition

The key idea is to efficiently check for each element x in the array if x + 1 exists in the array. Using a hash set allows for constant time lookups, making the solution efficient even with duplicates.

Approach

  1. Add all elements of arr to a hash set for O(1) lookups.
  2. Iterate through each element x in arr:
    • If x + 1 is in the set, increment the answer.
  3. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int countElements(vector<int>& arr) {
        unordered_set<int> s(arr.begin(), arr.end());
        int ans = 0;
        for (int x : arr) {
            if (s.count(x + 1)) ++ans;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func countElements(arr []int) int {
    s := make(map[int]struct{})
    for _, x := range arr {
        s[x] = struct{}{}
    }
    ans := 0
    for _, x := range arr {
        if _, ok := s[x+1]; ok {
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int countElements(int[] arr) {
        Set<Integer> s = new HashSet<>();
        for (int x : arr) s.add(x);
        int ans = 0;
        for (int x : arr) {
            if (s.contains(x + 1)) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun countElements(arr: IntArray): Int {
        val s = arr.toSet()
        var ans = 0
        for (x in arr) {
            if (x + 1 in s) ans++
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def countElements(self, arr: list[int]) -> int:
        s = set(arr)
        ans = 0
        for x in arr:
            if x + 1 in s:
                ans += 1
        return ans
1
2
3
4
5
6

impl Solution {
    pub fn count_elements(arr: Vec<i32>) -> i32 {
        let s: std::collections::HashSet<_> = arr.iter().cloned().collect();
        arr.iter().filter(|&&x| s.contains(&(x + 1))).count() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    countElements(arr: number[]): number {
        const s = new Set(arr);
        let ans = 0;
        for (const x of arr) {
            if (s.has(x + 1)) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of arr, as each lookup and insertion is O(1).
  • 🧺 Space complexity: O(n), for the hash set storing all unique elements.