In this article, I will decompose the Remove Duplicates from Sorted Array Problem on LeetCode. I also hope to clarify the two pointer technique. As I always say, C++ is a deep language with a lot to learn. Experimentation, projects and general development practice will catapult you forward. However, sometimes it is important to step back and review some basic computer science and coding challenges. Doing so has helped me think differently about solving problems and appreciate certain aspects of C++ that are easy to forget. This is a part of the reason why I have been practicing extensively on LeetCode.

The Problem

Click here to access the problem. Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

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:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Starter Code

    int removeDuplicates(vector<int>& nums) {
        
    }

Breaking It Down

This is very similar to the Move Zeros problem that I posted in an earlier article. In this problem we can use the same ‘two pointer‘ technique. Perhaps this is an easier problem to illustrate the method.

The ‘two pointer‘ technique relies on two pointers, iterators or indeces that increment through a vector at different rates or directions. Usually, one pointer will progress through the vector as per usual but the lagging pointer will only be incremented when a certain condition is met.

An Initial Solution (that misses the point…)

Here is a solution that may occur to those of you who are more practiced with C++.

    int removeDuplicates(vector<int>& nums) {
        /*return only unique elements...*/
        return std::unique(nums.begin(), nums.end()) - nums.begin();
    }

In an interview, it is possible that the evaluator could accept this answer. It is clear and it demonstrates you are aware of features in C++. std::unique is from the algorithms library from the standard library in C++. It also shows that you are aware of modern C++ practices using iterators and the STL container classes.

Unfortunately, this could also make an evaluator very frustrated as they may be trying to assess your understanding of problem solving using algorithms and data structures and not a particular language.

An Equivalent Solution (that gets the point…)

Here is a solution that runs in the same time as the previous solution. It essentially does the same thing as std::unique. This solution works by employing two pointers to compare values.

    int removeDuplicates(vector<int>& nums) {
        /*empty case...*/
        if(nums.size() == 0)
        {
            return 0;
        }
        
        int indexLag = 0;
        /*loop through the sorted vector starting with adjacent indeces...*/
        for(int indexCurrent = 1; indexCurrent < nums.size(); indexCurrent++)
        {
            /*are the values different?...*/
            if(nums[indexLag] != nums[indexCurrent])
            {
                /*increment the lagging point...*/
                indexLag++;
                /*overwrite value...*/
                nums[indexLag] = nums[indexCurrent];
            }
        }
        /*erase everything AFTER the lagging index position...*/
        nums.erase(nums.begin() + indexLag + 1, nums.end());
        
        return nums.size();
    }

Conclusion

I hope this example clears up any confusion surrounding the two pointer technique. It was a bit less obvious in the previous article and so I hope this helps. I suggest inserting print statements such that you can see this function at work. But of course, the question still remains…

Can we do better?

I would be interested in any more solutions in the comments below. Until then:

Be good to each other and take it easy…

-Will ☜(゚ヮ゚☜)

Liked it? Take a second to support William Fehlhaber on Patreon!

Shopping cart

Subtotal
Shipping and discount codes are added at checkout.
Checkout

Sign up here to learn about our premium courses and more!

 

Thank you for being a part of The Audio Programmer Community!