Is Counting Elements easy or hard?

Counting Elements is classified as an Easy problem. The main challenge is recognizing that repeated scans can be avoided by storing values in a hash set for O(1) lookups.

Counting Elements Python/Java solution

Most implementations use a set structure such as Python's set or Java's HashSet. Insert all values first, then loop through the array and check for x + 1 in the set. The logic is identical across languages like Python, Java, C++, Go, and JavaScript.

How to solve Counting Elements in O(n)?

Insert every number from the array into a hash set. Then iterate through the array and check if the set contains x + 1. If it does, increment the result counter. This uses O(n) time for iteration and O(n) space for the set.

What is the best approach for Counting Elements?

The optimal approach uses a hash set to store all array values. Then iterate through the array and check if x + 1 exists in the set. Each lookup is O(1) on average, giving an overall time complexity of O(n) with O(n) space.

Is Counting Elements asked at Google/Amazon/Meta?

Counting Elements represents a classic hash-table lookup pattern that frequently appears in interviews at companies like Amazon, Google, and Meta. Variations of this problem test your ability to replace nested loops with constant-time hash lookups.

What data structure is used in Counting Elements?

A hash set or hash map is the main data structure used in the optimal solution. It allows constant-time membership checks when verifying whether x + 1 exists in the array.

What is the time complexity of Counting Elements?

The optimal solution runs in O(n) time using a hash set for constant-time lookups. A brute force approach takes O(n^2) because it scans the array for every element. Sorting-based solutions run in O(n log n) due to the sorting step.

Description Hints 2 Solution Video 8:47

1426. Counting Elements

Easy60.9% acceptance1 companyPremium elsewhere, free here

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 1:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there is no 2, 4, 6, or 8 in arr.

Constraints:

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

Asked at 1 company

Drw

Topics

Array Hash Table

Hints open one at a time

Hint 1

Use hashset to store all elements.

Hint 2

Loop again to count all valid elements.

8:47

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,3]

Input

[1,1,3,3,5,5,7,7]

Your code is saved on this device.Solution