Coding Problem Solving

Remove duplicates from an integer array

Senthil Nayagan
Written by Senthil Nayagan on  - 2 Mins Read

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 of nums, so it does n iterations, and at each iteration, we are checking if the element is not in output. Note that searching for an element in an unsorted array has an O(n) cost.
  • Space complexity: O(n) - Because we are storing the output in a separate additional array that will contain n elements in the worst case, when there are no duplicates in nums.

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

comments powered by Disqus