Domain 1EasyCORE

Counting Elements

The problem requires counting elements in an array such that for each element `x`, there exists another element `x + 1` in the same array. The count should include duplicates separately. The input is a list of integers, and the output is an integer representing the count of such elements.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1426. Counting Elements

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 59.1%


Problem Breakdown

The problem requires counting elements in an array such that for each element x, there exists another element x + 1 in the same array. The count should include duplicates separately. The input is a list of integers, and the output is an integer representing the count of such elements.

Inputs:

  • An integer array arr.

Outputs:

  • An integer count of elements x where x + 1 is also in arr.

Implicit Constraints/Edge Cases:

  • The array can contain duplicates, which should be counted separately.
  • The array length is between 1 and 1000.
  • Each element in the array is between 0 and 1000.

Intuition

A brute-force approach would involve checking for each element x if x + 1 exists in the array. This would result in a time complexity of O(n^2) because for each element, we might need to scan the entire array again to check for the presence of x + 1.

The key insight is to use a data structure that allows for fast lookups. A hash set (or dictionary) can be used to store all elements of the array, enabling O(1) average time complexity for checking if an element exists.

Approach

  1. Initialize a Counter: Use a dictionary to count occurrences of each element in the array.
  2. Count Elements with Successors: Iterate through the keys of the dictionary and check if x + 1 is also a key in the dictionary. If it is, add the count of x to the result.

Algorithm Steps:

  • Create an empty dictionary element_count.
  • Populate element_count by iterating over each element in arr and incrementing its count.
  • Initialize a variable result to 0.
  • For each key x in element_count, check if x + 1 is also a key in element_count. If true, add the count of x to result.
  • Return result.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array. This is because we iterate over the array twice: once to populate the dictionary and once to check for successors.
  • Space Complexity: O(n) in the worst case, where all elements are unique and stored in the dictionary.

Solution

def countElements(arr):
    element_count = {}
    
    # Populate the dictionary with counts of each element
    for num in arr:
        if num in element_count:
            element_count[num] += 1
        else:
            element_count[num] = 1
    
    result = 0
    
    # Check for elements that have a successor
    for x in element_count:
        if x + 1 in element_count:
            result += element_count[x]
    
    return result

Edge Cases Handled

  • Empty Array: The function will return 0 as there are no elements to check.
  • All Elements Unique: Each element is counted separately if its successor exists.
  • All Elements Duplicates: Duplicates are counted based on their occurrences.
  • No Successors Found: The function returns 0 if no element has a successor in the array.