Remove Duplicates from Sorted Array

In this article, I share my solution and thought process for day 1's Leetcode challenge for the #I4G10DaysOfCodeChallenge series. I had actually solved this problem on Leetcode before, but having a second crack at it made me realize a better solution. I guess that's one of the many benefits of this challenge :-).

Let's get into it...

Problem statement, examples, and constraints.

#I4G10DaysOfCodeChallenge

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.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

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

Example 2:

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

Constraints:

1 <= nums.length <= 3 * 10⁴
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

Solution

var removeDuplicates = function(nums) {

    const lengthOfNums = nums.length;
    let tracker = 0;

    for(let i = 0; i < lengthOfNums; i++) {

        if(nums[i] !== nums[i + 1]) {

            nums[tracker++] = nums[i];
        }
    }

    return tracker;

};

Thought Process

From the problem statement, the whole idea of this problem is to remove the duplicates in-place and keep the relative order of the elements the same. As simple as this problem is, these requirements made it a tricky one for me.

Since this operation has to be done in-place, it's somewhat impossible to change the length of the array. Hence, the reason why my result has to occupy the first parts of the array it requires.

I use a two-pointer approach in this problem, the tracker variable keeps track of the first occurring duplicate value and handles its removal, while the i variable in the for-loop keeps track of the current index at every point in time.

All that is going on is this; I'm looping through the array, and checking the indexes of each adjacent element in the array. If two adjacent indexes aren't the same, they maintain their position. But if they are the same, only the first occurring index maintains its position and the other is moved.

if(nums[i] !== nums[i + 1]) {
    nums[tracker++] = nums[i];
}

Efficiency

With regard to efficiency, I think this is quite an optimal solution. Time Complexity: O(n) Space Complexity: O(1)

Closing

Thanks for reading through, I hope you learned a thing or two. Will see you in the next challenge post.

Please share your thoughts in the comment section, let's talk :-)

Your friend in progress,

CodeProphet.

Day 1 - Remove Duplicates from Sorted Array - Leetcode Problem Solved

#I4G10DaysOfCodeChallenge - Day 1

Problem statement, examples, and constraints.