Before I reflect on my experience, let me give you a brief description of the challenge. The challenge is solving one common algorithm problem daily for 10 starting September 21 - 30, 2022.

Today's algorithm problem was:

Removing duplicates from a sorted list, the following are examples of the problem:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2, respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4, respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

When I first started it, I thought it was simply because the level of the problem was easy. Yes, solving it without considering the time and space complexity is simple.

I solved it in my first attempt by following a simple intuition.

  1. Start from the first index
  2. Check if the current position is less than or equal to the previous
    1. If the above condition is true, loop until you get a different value
    2. Get the index of the different value
    3. Replace the current position's value with the new one
  3. If not keep on looping

Even though the above code works, my code running time was 235 ms which is only 15% more than the other submissions. Then I spent around 1:30 mins to make it better I couldn't. At first, I didn't want to use any built-in function, but when I realized I was spending too much time on it, I decided to use built-in functions. Here is what I did.

  1. Convert the list to a set (Sets won't contain duplicates)
  2. Loop over the set and replace the first n elements with a set values

If all the elements are positive numbers, no problem. The problem arises when the list contains negative elements since the set place the negative elements at the end. So, I sorted the set to overcome the problem.

The result was 122 ms which is 75.30% faster than the other submissions.

I am not proud of this approach, but I accept it for the submission purpose and keep working on it until I came up with a better solution.