Code Logo

Counting Elements

Published at24 Jul 2026
Created by
Easy 3 views
Like0

Given an integer array, count how many numbers x have x + 1 also present in the array. Each occurrence counts separately — if a number appears multiple times, each appearance where its successor exists adds 1 to the total.

A brute force approach would check each element against every other element in O(n²) time. Using a hash set reduces this to O(n) by storing all numbers for O(1) lookups. Simply iterate the array, and for each element, check if element + 1 is in the set. Count the number of elements that satisfy this condition.

This problem is a warm-up to using hash sets for existence queries. The key insight is that we only need to check forward (x + 1), not backward. Each element is evaluated independently, and duplicates in the array count separately.

Edge cases include an empty array (return 0), an array with a single element (return 0 since x+1 cannot exist), and an array where every element has its successor (e.g., [1,2,3] counts 2 for 1→2 and 2→3).

Using a hash set instead of a hash map is sufficient here because we only need to know if x+1 exists, not how many times it appears. Each occurrence of x contributes independently to the count, so we iterate the original array rather than the set. This approach works for up to 10^5 elements comfortably.

Example Input & Output

Example 1
Input
[1,1,2,2]
Output
2
Explanation

First 1 counts (2 exists), second 1 also counts.

Example 2
Input
[1,1,2]
Output
2
Explanation

Both 1s count since 2 exists.

Example 3
Input
[1,1,3,3,5,5,7,7]
Output
0
Explanation

No number has its successor.

Example 4
Input
[]
Output
0
Explanation

Empty.

Example 5
Input
[1,2,3]
Output
2
Explanation

1+1=2 exists, 2+1=3 exists. 3+1=4 does not.

Algorithm Flow

Recommendation Algorithm Flow for Counting Elements

Solution Approach

Count how many elements in an array have a successor (element + 1) also present in the array. Use a hash set to store all elements for O(1) lookups. For each element, check if element + 1 exists in the set. Count the number of elements where this condition holds.

function countElements(arr) {
  var set = {}, count = 0;
  for (var i = 0; i < arr.length; i++) set[arr[i]] = true;
  for (var i = 0; i < arr.length; i++) {
    if (set[arr[i] + 1]) count++;
  }
  return count;
}

The set provides instant membership testing. Each element is checked once for whether its successor exists, independent of duplicate values.

Time complexity is O(n), space complexity is O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int n : nums) s.add(n);
        int count = 0;
        for (int n : nums) {
            if (s.contains(n + 1)) count++;
        }
        return count;
    }
}