Remove Duplicates From Array

Disclaimer: Most of the content for problem statement is taken from algodaily.com

Problem Statement

Given an array, return another array with just the ordered unique elements from the given array. In other words, you're removing any duplicates.

Note: Order needs to be preserved, so no sorting should be done. And the order should be maintained with the first occurrence of the element in the given array.

Constraints

• Length of the array <= 100000
• The values in the array between -1000000000 and 1000000000
• Expected time complexity: O(n)
• Expected space complexity: O(n)

Solution

Since the constraints mention that the expected space complexity is O(n). So we could use an additional hash/hash map to keep track of the numbers that have already appeared in the array.

This is how the code will look like

1. Initialize the hash object called already_present and an array result

   already_present = {}
   result = []
   

2. Iterate on the elements of the original array

   arr.each do |number|
   ...
   end
   

3. If the element does not exist in already_present hash then push the element to result array because this is the first occurrence of the element. Also, add the same element in the already_present hash object so that next time if it appears again, you can skip that.

   unless already_present[number]
   result.push number
   already_present[number] = true
   end
   

4. Once the loop ends, the result array will contain the unique elements from the original array. So just return that.

Final Code

Here is how the final code looks:

def uniques(arr)
    already_present = {}
    result = []
    arr.each do |number|
      unless already_present[number]
        result.push number
        already_present[number] = true
      end
    end
    result
end

Time & Space Complexity

Let's take a look at how efficient this code is in terms of space and time.

• We're iterating over the whole array once so the time complexity will be O(n) given that n is the length of the array.
• We are also pushing these numbers to the already_present hash. In addition to that, we're building a result array as well. So, the space complexity will be O(n)

Testing

We can run some unit tests to verify if our code works as expected

p uniques([
  8, 8, 15, 6, 19, 7, 12, 6, 6, 3, 13, 9, 15, 14, 1, 13, 4, 11, 16
]) == [
  8, 15, 6, 19, 7, 12, 3, 13, 9, 14, 1, 4, 11, 16
] # => true
p uniques([9, 9, 9, 9, 9, 9]) == [9] # => true
p uniques([1, 2, 3, 4, 5, 6]) == [1, 2, 3, 4, 5, 6] # => true
p uniques([6, 5, 4, 3, 2, 1]) == [6, 5, 4, 3, 2, 1] # => true