LeetCode 1426 - Counting Elements

LeetCode Problem 1426

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

The problem asks us to count the number of elements in an array arr for which the value plus one also exists in the array. In other words, for every element x in the array, we check whether x + 1 is also present. If it is, we include x in our count. If duplicates exist, each occurrence is counted separately.

The input arr is a list of integers, each in the range 0 to 1000, and the length of the array is guaranteed to be at least 1 and at most 1000. This range is small enough to allow direct membership checking using a hash set without performance concerns.

Important edge cases include arrays with all identical elements, arrays with gaps (e.g., [1,3,5]), arrays where all elements form consecutive sequences, and arrays with the smallest or largest possible integers. The constraints guarantee that the array is non-empty and the values are non-negative, so we do not need to handle negative numbers or empty input.

Approaches

The brute-force approach is straightforward: for each element in the array, iterate over the entire array again to check if x + 1 exists. While this works correctly, it has a time complexity of O(n²) and becomes inefficient for large arrays.

The optimal approach uses a hash set to store all unique elements of the array. Then, for each element x in the array, we simply check if x + 1 exists in the set. This reduces the membership check from O(n) to O(1) per element, making the total time complexity O(n). The key insight is that looking up an element in a hash set is constant time, so we avoid nested loops.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	For each element, scan the entire array for x+1
Optimal	O(n)	O(n)	Use a hash set for constant-time membership check

Algorithm Walkthrough

1. Initialize an empty hash set and populate it with all elements of the array. This ensures we can check membership in constant time.
2. Initialize a counter to zero to track the number of valid elements.
3. Iterate through each element x in the array.
4. For each x, check whether x + 1 exists in the hash set.
5. If x + 1 is present, increment the counter.
6. After the loop finishes, return the counter as the result.

Why it works: The hash set guarantees constant-time lookups. By iterating over each element and checking for x + 1 in the set, we accurately count each valid element once per occurrence. The count correctly handles duplicates because we iterate over the original array, not the set.

Python Solution

from typing import List

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

In this implementation, we first convert the array into a set to allow constant-time membership checks. We initialize count to zero and iterate through the original array. For each element, we check whether x + 1 exists in the set and increment the counter if it does. Finally, we return the count.

Go Solution

func countElements(arr []int) int {
    elementSet := make(map[int]struct{})
    for _, val := range arr {
        elementSet[val] = struct{}{}
    }

    count := 0
    for _, val := range arr {
        if _, exists := elementSet[val+1]; exists {
            count++
        }
    }
    return count
}

In Go, we use a map[int]struct{} to represent the hash set. We populate the map with all elements of the array and then iterate through the array to check for the presence of x + 1. The empty struct takes zero bytes, which is the Go convention for sets. The rest of the logic mirrors the Python implementation.

Worked Examples

Example 1: arr = [1,2,3]

Element x	Check x+1 in set	Count
1	2 exists	1
2	3 exists	2
3	4 does not exist	2

Output: 2

Example 2: arr = [1,1,3,3,5,5,7,7]

Element x	Check x+1 in set	Count
1	2 does not exist	0
1	2 does not exist	0
3	4 does not exist	0
3	4 does not exist	0
5	6 does not exist	0
5	6 does not exist	0
7	8 does not exist	0
7	8 does not exist	0

Output: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Converting the array to a set takes O(n), iterating through the array also takes O(n)
Space	O(n)	The hash set stores all unique elements, which in the worst case is all n elements

The algorithm is efficient due to the hash set's constant-time lookup. Even with the maximum constraint of 1000 elements, this solution is highly performant.

Test Cases

# Provided examples
assert Solution().countElements([1,2,3]) == 2  # basic consecutive numbers
assert Solution().countElements([1,1,3,3,5,5,7,7]) == 0  # no consecutive numbers

# Edge and boundary cases
assert Solution().countElements([0]) == 0  # single element, nothing can follow
assert Solution().countElements([0,1,2,3,4]) == 4  # full consecutive sequence
assert Solution().countElements([1,2,2,3]) == 3  # duplicates handled correctly
assert Solution().countElements([1000,999,998]) == 2  # largest numbers
assert Solution().countElements([1]*1000) == 0  # all identical numbers
assert Solution().countElements(list(range(1001))) == 1000  # maximum length with full sequence

Test	Why
[1,2,3]	Basic consecutive sequence, validates standard counting
[1,1,3,3,5,5,7,7]	No consecutive numbers, ensures zero-count case
[0]	Single-element edge case
[0,1,2,3,4]	Full consecutive sequence, checks cumulative counting
[1,2,2,3]	Duplicate elements, ensures each occurrence counted
[1000,999,998]	Maximum values, checks boundary correctness
[1]*1000	All identical elements, tests counting logic with duplicates
list(range(1001))	Maximum array size, validates performance and correctness

Edge Cases

One critical edge case is when the array contains only a single element. Since there is no element x + 1 to compare with, the function must return zero. The implementation handles this naturally by the iteration check.

Another important edge case is when all elements are identical. If the repeated number does not have its successor in the array, the count should remain zero. The use of a set ensures that the check for x + 1 does not accidentally count missing numbers.

A third edge case occurs when the array contains the maximum allowed value, 1000. Since 1001 is outside the allowed element range, the function must correctly not count 1000. This is handled automatically because 1001 is not in the set.

This implementation handles all these edge cases naturally, providing robust and correct behavior.