1426. Counting Elements - Explanation

Problem Link

Description

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

1. Search with Array

class Solution:
    def countElements(self, arr: List[int]) -> int:
        count = 0
        for x in arr:
            if x + 1 in arr:
                count += 1
        return count

Time & Space Complexity

• Time complexity: $O(N^2)$
• Space complexity: $O(1)$ constant space

Where $N$ is the length of the input array arr.

---

2. Search with HashSet

class Solution:
    def countElements(self, arr: List[int]) -> int:
        hash_set = set(arr)
        count = 0
        for x in arr:
            if x + 1 in hash_set:
                count += 1
        return count

Time & Space Complexity

• Time complexity: $O(N)$
• Space complexity: $O(N)$

Where $N$ is the length of the input array arr.

---

3. Search with Sorted Array

class Solution:
    def countElements(self, arr: List[int]) -> int:
        arr.sort()
        count = 0
        run_length = 1
        for i in range(1, len(arr)):
            if arr[i - 1] != arr[i]:
                if arr[i - 1] + 1 == arr[i]:
                    count += run_length
                run_length = 0
            run_length += 1
        return count

Time & Space Complexity

• Time complexity: $O(N \log N)$
• Space complexity: varies from $O(N)$ to $O(1)$
  • The overall space complexity is dependent on the space complexity of the sorting algorithm you're using. The space complexity of sorting algorithms built into programming languages are generally anywhere from $O(N)$ to $O(1)$.

Where $N$ is the length of the input array arr.