Teaching Kids Programming – Using Hash Set or Hash Table to Count Next Element

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums, return the number of elements x there are such that x + 1 exists as well.

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [3, 1, 2, 2, 7]
Output
3
Explanation
We can take

1 since 1 + 1 exists in the list.
2 since 2 + 1 exists in the list.
Another 2.

Bruteforce Algorithm to Count Next Element

Of course, we can bruteforce, but this is going to take O(N^2) quadratic time:

1
2
3
4
5
6
7
8
9
10

class Solution:
    def countNextElement(self, nums):
        d = set(nums)
        ans = 0
        for i in nums:
            for j in nums:
                if j == i + 1:
                     ans += 1
                     break
        return ans

class Solution:
    def countNextElement(self, nums):
        d = set(nums)
        ans = 0
        for i in nums:
            for j in nums:
                if j == i + 1:
                     ans += 1
                     break
        return ans

Algorithms to Count Next Element

We can use a set to store the unique numbers in the given array, then go through each number and check if next element is in the array:

1
2
3
4
5
6
7
8

class Solution:
    def countNextElement(self, nums):
        d = set(nums)
        ans = 0
        for i in nums:
            if i + 1 in d:
                ans += 1
        return ans

class Solution:
    def countNextElement(self, nums):
        d = set(nums)
        ans = 0
        for i in nums:
            if i + 1 in d:
                ans += 1
        return ans

We can also use the Counter object which counts the elements as key-value pairs. Then, we go through the keys and check if next element is in the dictionary. This may be a bit faster as the second pass we only go through the unique numbers:

1
2
3
4
5
6
7
8

class Solution:
    def countNextElement(self, nums):
        cn = Counter(nums)
        ans = 0
        for i in cn.keys():
            if i + 1 in cn:
                ans += cn[i]
        return ans

class Solution:
    def countNextElement(self, nums):
        cn = Counter(nums)
        ans = 0
        for i in cn.keys():
            if i + 1 in cn:
                ans += cn[i]
        return ans

Using Python’s list comprehension, we can implement this in a Pythonic way.

1
2
3
4

class Solution:
    def countNextElement(self, nums):
        cn = Counter(nums)
        return sum(v for k, v in cn.items() if k + 1 in cn)

class Solution:
    def countNextElement(self, nums):
        cn = Counter(nums)
        return sum(v for k, v in cn.items() if k + 1 in cn)

–EOF (The Ultimate Computing & Technology Blog) —