LeetCode Challenge: Counting Elements

#computerscience #beginners #leetcode #problemsolving

This is the last problem in Week 1 of the month-long LeetCode challenge.

Looks like this is the first of the 5 new questions that were promised to make things interesting.

Problem

Given an integer array arr, count element x such that x + 1 is also in arr.

If there're 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's no 2, 4, 6, or 8 in arr.

Example 3:

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

Example 4:

Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

Constraints:

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

Clarification

The first 3 test cases are kind of misleading because they don't really show what is actually expected from us.

However, the last example gives some info.

From what we can observe, they're asking for the count of x in the array if x+1 also exists in the array.

Approach 1: Space Optimized

If the array is sorted then x+1 will be right after x. But if there are multiple occurrences of x then the 1st x+1 will come after the last x.

So, we need to count the frequency of each x and if the next element is different we need to check if it is x+1 or not.

Algorithm:

Initialize variables count to store the final result and currCount to store the count of the current element that is being tracked.
Sort the array
Iterate through the array
If the current element is equal to the previous element then increment currCount
Else if the current element is 1 greater than the previous element then add currCount to count. Reset currCount.
Return count

Code:

def approach1(arr):
    if len(arr) == 1:
        return 0

    arr = sorted(arr)
    count = 0
    currCount = 1

    for i in range(1, len(arr)):
        if arr[i] == arr[i-1]:
            currCount += 1
        else:
            if arr[i] == arr[i-1] + 1:
                count += currCount
            currCount = 1

    return count

Complexity analysis:

Time complexity: O(n*log(n)) 
Space complexity: O(1)

Approach 2: Time Optimized

Since we're dealing with counts we can use a hash map to maintain the count of each number and then easily check for the presence of the next number.

Code:

def approach2(arr):
    count = 0
    freq = {}

    for num in arr:
        freq[num] = freq.get(num, 0) + 1

    for x in freq:
        if x+1 in freq:
            count += freq[x]

    return count

Complexity analysis:

Time complexity: O(n) 
Space complexity: O(n)

Summary

Not many people talk about this but sometimes a programmer needs to consider the tradeoffs between space and time complexity of different solutions because not all situations have enough space to achieve optimal runtime complexity. The same applies the other way around.

As usual,