Counting Elements - Practice Coding Problems

Counting Elements - 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.

Example: If arr = [1, 2, 3], then we have element 1 (and 1 + 1 = 2 exists), and element 2 (and 2 + 1 = 3 exists). So the answer is 2.

Input & Output

Example 1 — Basic Case

$ Input: arr = [1,2,3]

› Output: 2

💡 Note: Element 1 has successor 2 in array, element 2 has successor 3 in array. Element 3 has no successor 4. So count = 2.

Example 2 — With Duplicates

$ Input: arr = [1,1,3,3,5,5,7,7]

› Output: 0

💡 Note: No element x has x+1 in the array. 1→2 (missing), 3→4 (missing), 5→6 (missing), 7→8 (missing). Count = 0.

Example 3 — Counting Duplicates

$ Input: arr = [1,3,2,3,5,0]

› Output: 3

💡 Note: Element 0 has successor 1, element 1 has successor 2, element 2 has successor 3. Both instances of 3 don't have successor 4. Count = 3.

Constraints

1 ≤ arr.length ≤ 1000
0 ≤ arr[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with elements to check for successors

Find Successors

For each element x, check if x+1 exists

Count Result

Total count of elements with successors

Key Takeaway

🎯 Key Insight: Use hash set to check if x+1 exists in O(1) time instead of scanning the array

Asked in

F Facebook 15 A Amazon 12

The key insight is to use a hash set for O(1) successor lookups instead of linear search. Build a set of all elements, then count how many elements have their x+1 present. Best approach is hash set with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Lookup	O(n)	O(n)	Store all elements in a hash set, then check each element's successor in O(1)
Brute Force	O(n²)	O(1)	For each element, scan the entire array to find if x+1 exists

Hash Set Lookup — Algorithm Steps

Create a hash set and insert all array elements
For each element x in the array, check if x+1 exists in the set
Count all elements that have their successor present

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Set

Insert all array elements into hash set

Check Successors

For each element, lookup x+1 in O(1) time

Count Matches

Sum all elements that have successors

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_SIZE 10007

typedef struct Node {
    int value;
    struct Node* next;
} Node;

typedef struct {
    Node* table[HASH_SIZE];
} HashSet;

int hash(int value) {
    return abs(value) % HASH_SIZE;
}

void insert(HashSet* set, int value) {
    int index = hash(value);
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->value = value;
    newNode->next = set->table[index];
    set->table[index] = newNode;
}

int contains(HashSet* set, int value) {
    int index = hash(value);
    Node* current = set->table[index];
    while (current) {
        if (current->value == value) return 1;
        current = current->next;
    }
    return 0;
}

int solution(int* arr, int size) {
    // Create a hash set of all elements
    HashSet set = {0};
    for (int i = 0; i < size; i++) {
        insert(&set, arr[i]);
    }
    
    int count = 0;
    for (int i = 0; i < size; i++) {
        // Check if arr[i]+1 exists in the set
        if (contains(&set, arr[i] + 1)) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000];
    int size = 0;
    
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(arr, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through array - first to build set, second to check successors, each element processed once

✓ Linear Growth

Space Complexity

O(n)

Hash set stores all unique elements from the array, worst case n elements

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set Lookup — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler