Problem Description

You are given an integer array arr. Your task is to count how many elements x exist in the array such that x + 1 is also present in the array.

The key points to understand:

• For each element x in the array, check if x + 1 also exists in the array
• If x + 1 exists, then x should be counted
• If there are duplicate values of x in the array, each duplicate should be counted separately

For example:

• If arr = [1, 2, 3], then elements 1 and 2 would be counted (since 2 and 3 exist respectively), giving a result of 2
• If arr = [1, 1, 3, 3, 5, 5, 7, 7], only the two 3s would be counted (since 4 exists in neither case), giving a result of 2
• If arr = [1, 1, 2], both occurrences of 1 would be counted (since 2 exists), giving a result of 2

The solution uses a Counter to track the frequency of each number, then sums up the counts of all numbers x where x + 1 is also present in the array.

Intuition

The main challenge is efficiently checking if x + 1 exists for each element x in the array, while also handling duplicates correctly.

A naive approach would be to iterate through each element and then scan the entire array again to check if x + 1 exists. This would be inefficient with O(n²) time complexity.

The key insight is that we need two pieces of information:

1. Which unique numbers exist in the array
2. How many times each number appears (to handle duplicates)

This naturally leads us to think about using a frequency map or counter. By counting the frequency of each number first, we can:

• Check if x + 1 exists in constant time O(1) by looking it up in our frequency map
• Know exactly how many times each number x appears, so we can add the correct count to our answer

Once we have the frequency map, we simply iterate through each unique number x in the map. If x + 1 exists in the map (meaning cnt[x + 1] > 0), then all occurrences of x satisfy our condition, so we add cnt[x] to our answer.

For example, if we have [1, 1, 2, 3]:

• cnt = {1: 2, 2: 1, 3: 1}
• For x = 1: Since 2 exists, we count both occurrences of 1, adding 2 to our answer
• For x = 2: Since 3 exists, we count the single occurrence of 2, adding 1 to our answer
• For x = 3: Since 4 doesn't exist, we don't count it

This gives us an efficient O(n) solution using O(n) extra space for the frequency map.

Solution Approach

The solution implements the counting approach using Python's Counter class from the collections module.

Step 1: Count frequencies

cnt = Counter(arr)

This creates a dictionary-like object where keys are the unique numbers from arr and values are their frequencies. For example, if arr = [1, 1, 2, 3], then cnt = {1: 2, 2: 1, 3: 1}.

Step 2: Iterate and sum valid counts

return sum(v for x, v in cnt.items() if cnt[x + 1])

This line does several things:

• cnt.items() iterates through all (number, frequency) pairs in the counter
• For each pair (x, v) where x is the number and v is its frequency
• if cnt[x + 1] checks if x + 1 exists in the counter (in Python, this evaluates to True if cnt[x + 1] > 0, and False if x + 1 is not in cnt or has count 0)
• If the condition is true, v (the frequency of x) is included in the sum
• The sum() function adds up all the valid frequencies

Why this works:

• When x + 1 exists in the array, all occurrences of x meet our criteria
• By summing the frequencies (v) of all such valid numbers x, we get the total count of elements that have their successor in the array

Time Complexity: O(n) where n is the length of the array - we iterate through the array once to build the counter, then iterate through the unique elements once.

Space Complexity: O(n) for storing the counter, which in the worst case contains all unique elements from the array.

Example Walkthrough

Let's walk through the solution with arr = [1, 2, 1, 3, 5, 6, 5].

Step 1: Build the frequency counter

First, we create a Counter from the array:

cnt = Counter([1, 2, 1, 3, 5, 6, 5])
cnt = {1: 2, 2: 1, 3: 1, 5: 2, 6: 1}

Step 2: Check each unique number

Now we iterate through each (number, frequency) pair and check if number + 1 exists:

• x = 1, v = 2: Check if 1 + 1 = 2 exists in cnt

  • cnt[2] = 1 (exists), so we count all 2 occurrences of 1
  • Add 2 to our sum

• x = 2, v = 1: Check if 2 + 1 = 3 exists in cnt

  • cnt[3] = 1 (exists), so we count the 1 occurrence of 2
  • Add 1 to our sum

• x = 3, v = 1: Check if 3 + 1 = 4 exists in cnt

  • cnt[4] doesn't exist, so we don't count 3
  • Add 0 to our sum

• x = 5, v = 2: Check if 5 + 1 = 6 exists in cnt

  • cnt[6] = 1 (exists), so we count all 2 occurrences of 5
  • Add 2 to our sum

• x = 6, v = 1: Check if 6 + 1 = 7 exists in cnt

  • cnt[7] doesn't exist, so we don't count 6
  • Add 0 to our sum

Step 3: Calculate final result

Total sum = 2 + 1 + 0 + 2 + 0 = 5

Therefore, 5 elements in the array have their successor (x + 1) also present in the array.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array arr. This is because:

• Creating the Counter object requires iterating through all n elements of the array once, which takes O(n) time
• The Counter object will have at most n key-value pairs (in the worst case where all elements are unique)
• Iterating through the Counter items and checking if cnt[x + 1] exists takes O(1) time per item due to hash table lookup, resulting in O(n) total time for the iteration

The space complexity is O(n), where n is the length of the array arr. This is because:

• The Counter object stores at most n key-value pairs, requiring O(n) space in the worst case when all elements in the array are distinct
• The sum operation uses constant extra space beyond the Counter object

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Counting Unique Elements Instead of All Occurrences

The Mistake: A common error is counting each unique element only once, rather than counting all occurrences when x + 1 exists.

Incorrect Implementation:

def countElements(self, arr: List[int]) -> int:
    unique_elements = set(arr)
    count = 0
    for x in unique_elements:
        if x + 1 in unique_elements:
            count += 1  # Wrong! Only counts once per unique element
    return count

Why It's Wrong: If arr = [1, 1, 2], this would return 1 instead of 2, because it only counts the unique element 1 once, ignoring the duplicate.

Correct Approach: Count the frequency of each element and sum up all occurrences when the condition is met:

def countElements(self, arr: List[int]) -> int:
    frequency_map = Counter(arr)
    count = 0
    for element, frequency in frequency_map.items():
        if element + 1 in frequency_map:
            count += frequency  # Correct! Adds all occurrences
    return count

Pitfall 2: Checking Array Values Directly Without Efficient Lookup

The Mistake: Using repeated linear searches through the array to check if x + 1 exists.

Inefficient Implementation:

def countElements(self, arr: List[int]) -> int:
    count = 0
    for x in arr:
        if (x + 1) in arr:  # O(n) search for each element!
            count += 1
    return count

Why It's Problematic: This creates O(n²) time complexity because in arr performs a linear search for each element. For large arrays, this becomes extremely slow.

Better Solution: Use a set or Counter for O(1) lookup:

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

Pitfall 3: Misunderstanding the Problem Requirements

The Mistake: Counting elements where x - 1 exists instead of x + 1, or counting both x and x + 1 when the condition is met.

Wrong Interpretation Example:

def countElements(self, arr: List[int]) -> int:
    frequency_map = Counter(arr)
    count = 0
    for element, frequency in frequency_map.items():
        if element + 1 in frequency_map:
            # Wrong! Counting both x and x+1
            count += frequency + frequency_map[element + 1]
    return count

Correct Understanding: Only count occurrences of x when x + 1 exists. The element x + 1 itself is not counted unless x + 2 also exists in the array.