Counting Elements

Easy
665.

Counting Elements

Counting Elements is an easy coding problem on arrays, hash table and counting, asked in Amazon, TCS and Accenture interviews.

Given an array arr, count the elements x such that x + 1 also appears somewhere in arr.

Duplicates are counted separately: if arr holds 1 twice and also holds 2, both copies of 1 count.

Example 1

Input
arr = [1,2,3]
Output
2
Explanation
1 and 2 both have a successor present.

Example 2

Input
arr = [1,1,3,3,5,5,7,7]
Output
0
Explanation
No value has its successor in the array.

Example 3

Input
arr = [1,3,2,3,5,0]
Output
3
Explanation
0, 1 and 2 each have a successor.

Constraints

  • 1 <= arr.length <= 1000
  • 0 <= arr[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var countElements = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Counting Elements — Solution in Python, Java & C++

Counting Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Counting Elements is an easy coding problem on arrays, hash table and counting, asked in Amazon, TCS and Accenture interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table, Counting
  • Asked at: Amazon, TCS, Accenture
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array arr, count the elements x such that x + 1 also appears somewhere in arr.

Duplicates are counted separately: if arr holds 1 twice and also holds 2, both copies of 1 count.

Example 1

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 both have a successor present.

Example 2

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No value has its successor in the array.

Example 3

Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 each have a successor.

Constraints

  • 1 <= arr.length <= 1000
  • 0 <= arr[i] <= 1000

Hints for Counting Elements

  1. Hint 1

    Membership is what matters for x + 1, but multiplicity matters for x.

  2. Hint 2

    So build a set once, then walk the original array — not the set.

  3. Hint 3

    Walking the set instead would count each distinct value only once.

How to solve Counting Elements

Two different notions are in play: x + 1 only needs to exist, while each copy of x counts on its own. A set answers the first, and iterating the original array answers the second.

Approach

  1. Insert every element into a set.
  2. Walk the original array and count the elements whose successor is in the set.

Why it works

Testing x + 1 against a set is a pure existence question, so duplicates there are irrelevant; counting over the array rather than the set is what preserves the multiplicity the statement asks for.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Iterating the set loses duplicates — [1,1,2] would answer 1 instead of 2.
  • Checking x - 1 answers the mirror-image question.

Reference solution

Python

from typing import List

def countElements(arr: List[int]) -> int:
    present = set(arr)
    return sum(1 for x in arr if x + 1 in present)

Java

public static int countElements(int[] arr) {
    Set<Integer> present = new HashSet<>();
    for (int x : arr) present.add(x);
    int total = 0;
    for (int x : arr) {
        if (present.contains(x + 1)) total++;
    }
    return total;
}

C++

int countElements(vector<int>& arr) {
    unordered_set<int> present(arr.begin(), arr.end());
    int total = 0;
    for (int x : arr) {
        if (present.count(x + 1)) total++;
    }
    return total;
}

JavaScript

var countElements = function(arr) {
    var present = {};
    for (var i = 0; i < arr.length; i++) present[String(arr[i])] = true;
    var total = 0;
    for (var j = 0; j < arr.length; j++) {
        if (present[String(arr[j] + 1)] === true) total++;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets