Google Javascript Interview Question - Remove Duplicates from Sorted Array

Problem Statement

Remove Duplicates from a Sorted Array

arr = [1,2,2,3,3,4,4,4,5]

Description - As you can see in the above array there are multiple occurrences of the same element like 2 is repeated twice then 3 is twice and 4 is repeated 3 times. So, we have to remove these duplicate elements and we have to keep only one copy of each element in our output

Expected Output : [1,2,3,4,5]

Implementation

Time Complexity - O(n) // as we are traversing the array only once where n is the size of the array
Space Complexity - O(n)

Javascript Implementation

var nums = [1,2,2,3,3,4,4,4,5];

var removeDuplicates = function(nums) {
    var sortedArray = nums.sort();
    var len = sortedArray.length - 1;
    var newArr = [];

    if (len >= 0) {
        // Start traversing elements
        for (var i = 0; i < len; i++) {
            // If current element is not equal  to next element then store that 
            // current element
            if (sortedArray[i] !== sortedArray[i + 1]) {
                newArr.push(sortedArray[i]);
            }
        }
         // Store the last element as whether it is unique or repeated, it hasn't 
         // stored previously 
        newArr.push(sortedArray[len]);
    }
    return newArr

}

removeDuplicates(nums) // Returns => [ 1, 2, 3, 4, 5 ]

Copy and paste the above code in your browser developer tools and you will get
[ 1, 2, 3, 4, 5 ] as the output.

If you found this article helpful, please tap the Follow this channel for more articles on data structures and algorithms.

Comments

[Jon Randy 🎖️]

let removeDuplicates = nums => [...new Set(nums)];

[Theofanis Despoudis]

This will not work on objects sadly. It will work only if they refer to the same object

[Leonardo Santos]

The point here is to write the algorithm yourself. In this case you are just delegating the problem to the library to solve.

[Jon Randy 🎖️]

Sets are built into JS, not a library.

The post states that this is specifically a JS interview question, not an algorithm or computer science test.

The question does not explicitly forbid anything, we've just been asked to solve the problem using JavaScript. Using this method would demonstrate to the interviewer that you have a grasp of modern JS, can use common sense by not reinventing the wheel, and have the sense to rely on an inbuilt language feature that is almost certainly faster than anything you could write (and presumably less likely to contain errors).

This is an interview situation where you should try to highlight everything you know, including being able to identify more efficient solutions.

If the interviewer actually wanted to test your ability to construct the algorithm yourself, they will ask for that explicitly - either in the question statement, or after you present them with the Sets based solution.

[Leonardo Santos]

built into JS = standard LIBRARY. You get what I mean.

The post states that this is specifically a JS interview question, not an algorithm or computer science test.

Yes, this post lacks a lot of details about the problem. It is actually a general problem, he is just using JS to solve it.

Before the author edited the post, he mentioned that the space complexity should be O(1) (this is what is required in many places where this problem is described) which your solution does not meet.

You can see more details about the problem here:
interviewbit.com/problems/remove-d...
leetcode.com/problems/remove-dupli...

This is an interview situation where you should try to highlight everything you know, including being able to identify more efficient solutions.

So, what's the overall performance of your solution? What's the time and space complexity?

The original problem requires you to use constant space and linear time, so that means you should work with the array in place and not allocate an extra array.

[Alex Martin]

Sorry can you explain a little more in detail what is happening there? Thank you.

[JP Antunes]

I can give it a go if that's ok :-)

let removeDuplicates = nums => ...

is the same as

var removeDuplicates = function(nums) {...}

but using arrow function expression syntax.

The function body

[...new Set(nums)]

does 4 things:
a) creates a new Set using the original nums array as source
b) makes use of the property of Sets not allowing duplicate values to perform "automatic" deduplication
c) uses destructuring assignment syntax to turn the new Set back into an array
d) returns this new array

References:
developer.mozilla.org/en-US/docs/W...
developer.mozilla.org/en-US/docs/W...
developer.mozilla.org/en-US/docs/W...

PS: if you want to practice some warm up exercises of this sort... dev.to/jpantunes/js-warmup-exercis...

[Daniel Donohue]

"Because each value in the Set has to be unique, the value equality will be checked." - from MDN. He is taking in the old array and spreading it into a new array while creating a new "Set" object which is forcing every value to be unique.

[Theofanis Despoudis]

Based on the code you've given:

nums.sort(): Is O(nlogn) where n = size of original array. Because array is already sorted then you don't need to sort again anyway.

You can also use a Map to keep track of already seen items.

The example shows integers but the problem statement does not mention any restrictions on the types. Will this work on any type?

[Leonardo Santos]

If you want to know how to do it in constant space (and linear time):

function removeDuplicates(arr) {
  let nextNonDuplicate = 0;

  for (let i = 0; i < arr.length; i++) {
    // If this is the last element or it's different from the next one we move it.
    if ((i >= arr.length - 1) || (arr[i] != arr[i + 1])) {
      arr[nextNonDuplicate++] = arr[i];
    }
  }

  arr.length = nextNonDuplicate;
}

You can think of nextNonDuplicate as the index of a new array, if we were using a secondary array to store the non duplicated elements.

[chris-pardy]

From the description it sounds like this was supposed to be an in place removal of duplicates. If that's the case and given the time complexity, it's a much trickier algorithm.

[Leonardo Santos]

Your solution is not using O(1) space. It's allocating a new array with at most N elements (worst case), so it's not constant.