DEV Community

loading...

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

mridubhatnagar profile image Mridu Bhatnagar ・1 min read

This was one of the problems in LeetCode's ongoing 30-day challenge. Published on 7th April 2020.

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.
Solution Approach
  1. As the original list contains duplicate elements as well. Convert the list to set to get unique elements.
  2. Iterate over the set and check if element+1 exists in the original list.
  3. If it exists. Find the count of the element in the original list.
  4. Keep adding the count to the new list.
  5. Sum of all the counts. Returns the required output.
Code snippet
class Solution:
    def countElements(self, arr: List[int]) -> int:
        unique_elements = set(arr)
        L = []
        for element in unique_elements:
           if element + 1 in arr:
               item_count = arr.count(element)
               L.append(item_count)
        return sum(L)

Discussion on more optimized solutions are welcome.

Discussion

pic
Editor guide
Collapse
philipstarkey profile image
Phil Starkey

I suspect using a collections.Counter dict would be beneficial. If you convert the input list to one of those you can then just iterate over the keys and check if dict[dict[key]+1] > 0, and if yes, add dict[key] to a running summation.

The loop would be O(N) and dictionary lookup is typically O(1), which I think would be faster than your algorithm above.

The question is whether the initial conversion of input data is performant, which I don't know! But from a practical point of view, collections.Counter is good to know about!

Collapse
mridubhatnagar profile image
Mridu Bhatnagar Author

Hey Phil, thank you for suggesting the collections.Counter approach. I am yet to check out that module. But, yes I did read it somewhere it helps in achieving efficiency.

Also, with these, I am purposefully avoiding using libraries. :)