Counting Elements — Easy Problem & Solution

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

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

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

Insert every element into a set.
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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue