Day One

Problem description

Remove duplicates from sorted array.

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Examples

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).

You can find a brief description about the problem here.

Experience

When I first started it, I thought it was simple 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.

Start from the first index
Check if the current position is less than or equal to the previous
	If the above condition is true then loop until you get a different value
	Get the index of the different value
	Replace the current position's value with the new one
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 1hr 30 mins to make it better yet 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.

Convert the list to a set (Sets won't contain duplicates)
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

• Runtime: 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.

The code

def removeDuplicates(nums: List[int]) -> int:
	iterator = 0

	# sort the set and loop over it
	for number in sorted(set(nums)):
		nums[iterator] = number
		iterator += 1

	return iterator