Filter Elements From Array - Leetcode Solution

Problem statement:

Given an array nums of integers, return an array of the elements that appeared more than once in nums. You may return the answer in any order.

Example:

Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3]

Solution:

The given problem can be solved using Hash Maps. We can store the frequency of each element in the array and then return the elements that have a frequency greater than one.

Below are the steps to solve the problem using Hash Maps:

1. Initialize a Hash Map to store the frequency of each element in the array.

2. Traverse the array and insert each element into the Hash Map with its frequency.

3. Traverse the Hash Map and add the elements with frequency greater than one to a new array.

4. Return the new array.

Python code:

class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: frequency_map = {} result = []

    # Traverse the array and insert each element into the Hash Map with its frequency
    for num in nums:
        if num not in frequency_map:
            frequency_map[num] = 1
        else:
            frequency_map[num] += 1
            
    # Traverse the Hash Map and add the elements with frequency greater than one to a new array
    for key, value in frequency_map.items():
        if value > 1:
            result.append(key)
            
    # Return the new array
    return result

Time Complexity: O(n) Space Complexity: O(n)

Explanation:

In the above code, we have used a Hash Map to store the frequency of each element in the array. Then, we have traversed the Hash Map and added the elements with frequency greater than one to a new array. Finally, we have returned the new array.

The time complexity of the above code is O(n) as we are traversing the array and the Hash Map only once. The space complexity of the above code is also O(n) as we are storing the frequency map and the result array in memory.

1