## DEV Community is a community of 797,169 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Posted on

# 30-Day LeetCoding Challenge: Counting Elements

## Approach 1:

If you read the problem carefully you will find the solution in the problem statement itself.

It says you have an `integer array` and we need to count the element when the `element + 1` is also in that array considering if you have duplicates count at as separate so we don't care about duplicates.

Let's actually do whatever the problem says in the following example.

• Example:

`arr = [1,2,3]`

1. Start with `element = 1` is `element + 1 = 1 + 1 = 2` in the array or not, yes it is there so increate our answer with one `answer = 1`

2. Second element is `element = 2`, `element + 1 = 2 + 1 = 3` in the array yes it is there so `answer = 2`

3. Third and our last `element = 3`, `element + 1 = 3 + 1 = 4` is in the array no it is not so our final answer stays as it is and it will be `answer = 2`.

Try it out with this example `arr = [1,1,3,3,5,5,7,7]`

Remember we don't care about duplicates.

• Pseudocode:
``````1. define counts = 0
2. loop for each element in arr
3.    if element + 1 is in arr
4.        counts += 1
5. return counts
``````
• Complexity:

• Time Complexity: we do only one path over the whole array so it will be O() where `n` is the size of the array, and inside this loop, we do another check which `element is in arr` this will take also O(n) so overall the time complexity will be O(n2).

• Space Complexity: We only use extra space to store our answer which is constant so our overall space is O(1).

• Solution in python

## Approach 2:

Can we improve the above solution yes we can improve it at least on the time complexity part?

Let's think about the problem again:

• We need to know if each `element + 1` is in the array or not and if it is there increase our answer by `1`.

• What if one element is existing more than one time for example we have three twos and we have a three in the array so the condition of `elem + 1` will be valid.

• Hmm, so each time I will reach a `2` I will add `1` to my answer so what if I have a map telling me that 2 already exist 3 times like this `{2: 3}`.

• Now, easily I can say if `2 + 1 = 3` exist just add `3` to my answer.

So to be able to have this map which will contain every element and it is occurrence times. Why map (hash-map) because it is search time complexity is O(1) this will improve our search right!

• Example: `arr = [1,2,1,3]`
1. We need to define our hash-map so it will be: `counts = {1: 2, 2: 1, 3: 1}`

2. Then go over the `counts` hash-map, starts with `1` is `1 + 1 = 2` in our `counts` yes it is there so our `answer += counts[1] += 2 = 2`.

3. Then with the `2` is `2 + 1 = 3` in our `counts`, yes so `answer += counts[2] += 1 = 3`

4. With the `3` and `3 + 1 = 4` not in the `counts` so we stop here and our final answer is `answer = 3`.

• Pseudocode:
``````1. define counts = Count(arr)
2. define ans = 0
3. for elem in counts
4.    if elem + 1 in counts:
5.        ans += counts[elem]
6. return ans
``````
• Complexity:

• Time Complexity: We do two loops here the first one to build our `counts` map from the original array and it will take O(n) where `n` is the length of the array, then we go through the `counts` map which will take O(n) * O(1) where O(1) is `elem+1 in counts` so totally the loop will be O(n) and the overall will be O(n) + O(n) = O(n).

• Space Complexity: we use extra space to store the counts of the elements in hash-map so it will be O(n) as we store all elements in the array with the space to store our answer which is O(1) so the overall will be O(n).

• Solution in python