Problem: Remove duplicates from an integer array
Description
Given an array of integers nums, create a function that returns an array containing the values of nums without duplicates; the order doesn’t matter.
Example 1
- Input: nums = [4, 2, 5, 3, 3, 1, 2, 4, 1, 5, 5, 5, 3, 1]
- Output: [4, 2, 5, 3, 1]
Example 2
- Input: nums = [1, 1, 1, 1, 1, 1, 1, 1]
- Output: [1]
Solution 1 (Brute force solution)
In this brute force solution we create an empty array, output. For each element of nums, we check if we didn’t put in the output yet. If it’s the case, we push it, and we continue.
# Brute force approach
def remove_duplicates(nums):
output = []
for element in nums:
if element not in output:
output.append(element)
return output
if __name__ == "__main__":
print(remove_duplicates([4, 2, 5, 3, 3, 1, 2, 4, 1, 5, 5, 5, 3, 1])) # returns [4, 2, 5, 3, 1]
print(remove_duplicates([1, 1, 1, 1, 1, 1, 1, 1])) # returns [1]
Complexity
- Time complexity:
O(n2)- The loop is traversing elements ofnums, so it doesniterations, and at each iteration, we are checking if the element is not inoutput. Note that searching for an element in an unsorted array has anO(n)cost. - Space complexity:
O(n)- Because we are storing the output in a separate additional array that will containnelements in the worst case, when there are no duplicates innums.
Let’s find a better solution than this one.
Solution 2 (Using sorting approach)
It’s a sorting approach.
def remove_duplicates_sorted(nums):
if len(nums) == 0:
return []
nums.sort()
output = [nums[0]]
for i in range(1, len(nums)):
if nums[i] != nums[i-1]:
output.append(nums[i])
return output
Complexity
- Time complexity:
O(n long n)- Because we sorted the array - Space complexity:
O(n)
Let’s find a better solution than this one.
Solution 3 (Using hash table and without the need for sorting)
This solution uses hash table. The hash table is a powerful tool when solving coding problems because it has an O(1) lookup on average, so we can get the value of a certain key in O(1). Also, it has an O(1) insertion on average, so we can insert an element in O(1). Also, this solution does not require the input data to be sorted.
def remove_duplicates(nums):
visited = {} # Dictionary as hash table
for element in nums: # This iterates n times though!
visited[element] = True # Overwrites the already present elements
return list(visited.keys())
Complexity
- Time complexity:
O(n)- Because we are traversing completely during worst case. - Space complexity:
O(n)- Because of the hash map.
Comments