Leetcode 1426. Counting Elements (Typescript)

Today we will be going over Leetcode 1426 - Counting Elements. This is a fairly classic hash table problem.

Problem Statement and Analysis

Let's go ahead and take a look at the problem statement:

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.

This problem is pretty straightforward. We are given an array of integers and we need to count how many elements in the array have the property that their value plus one is also in the array. To solidify what's going on here let's say we have an array like:

const arr = [1, 2, 3];

1. For the value at index 0 (1) we can see that 1 + 1 = 2 and 2 is in the array. So we count this.
2. For the value at index 1 (2) we can see that 2 + 1 = 3 and 3 is in the array. So we count this.
3. For the value at index 2 (3) we can see that 3 + 1 = 4 and 4 is NOT in the array. So we do not count this.
4. The final count is 2.

So how might we go about solving this problem? The first thing that comes to mind is to use a hash table. But what makes this problem slightly different is we need to count the number of times a number appears in the array. Therefore instead of using something like a Set that would just tell us "this value was found at least once" we need to use a Map. This will allow us to keep track of how many times each number appears in the array.

We will start by iterating through each value of the input array and adding it to our map. If the value already exists we increment the corresponding value in the map for that number. Otherwise we initialize the value in the map and set the value to 1. Once we finish filling in the hash map then we simply need to iterate through the map and find out for each hash map value whether or not the value plus one exists in the hash map. If it does we want to add the value of that hash map entry to our count. This is because we need to count the number of times that number appears in the array.

Solution

function countElements(arr: number[]): number {
  const hashMap = new Map<number, number>();

  //create dictionary
  for (const num of arr) {
    if (hashMap.has(num)) {
      hashMap.set(num, hashMap.get(num) + 1);
    } else {
      hashMap.set(num, 1);
    }
  }

  let count = 0;

  for (const [num, val] of hashMap) {
    if (hashMap.has(num + 1)) {
      count += val;
    }
  }

  return count;
}

Time and Space Complexity Analysis

The time complexity of this solution is O(n). This is because we are iterating through the array worst case twice. In Big O notation constants don't matter so we just care about N. Space complexity is also O(n) because we are creating a hash table that is the same size as the input array.

Thanks for reading and best of luck on your coding journey!