LeetCode 01: Remove Duplicates from Sorted Array

Solution to first challenge

Objective

I have certain…gaps in my programming knowledge, and while I’ve been able to hack away at them by doing the thing many developers do (Google, StackOverflow, burnt offerings to questionable gods), I’m also trying to make sure this is a short-term handicap.

Put succinctly: I want to be able to comprehensively complain about the shortcomings about my programming language/dev environment of choice in the future. You know, like every cool developer, apparently. And the only way to be able to know the limitations of your tools is to know the extent of their capabilities.

Today I’m beginning with the Easy problems on the Leetcode top technical interview questions. In my approach, I’ll be discussing things that trip me up about the way technical questions are asked, the hidden gotchas, and bits of syntax that confuse me.

Okay. On to the first one!

Challenge: Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns 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.

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 a 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]);
}

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: 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:

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

Constraints:

• 0 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums is sorted in ascending order.

How I think about the challenge

To properly solve this question, we need to understand a few aspects of the task.

1. We need to remove duplicates in place. This means that we cannot copy or duplicate the array in any way. Put in simple terms, everything we do to remove the duplicates in the array must happen in one, and only one array — the original array. This is important because it’s possible to perform operations on one array that yields another array that fulfils the challenge criteria. Here, this is forbidden.
2. The space complexity needs to be O(1). This ties directly to the previous point, but it bears studying in its own right, if only as an excuse to talk about Space Complexity. A constant time space complexity means that it takes constant time to execute your function/algorithm. Constant time here means that the space requirement won’t grow or expand with the size of the data you’re working on. It stands to reason — if you think about it — that if you’re working in-place, you won’t be creating extra arrays no matter how large your original array is. You’ll only have the one array.
3. There is a section called ‘Clarification’ which confused me for a bit. I finally figured out what it was trying to say. Even though you’re only returning a number after your code executes, because you passed the array by reference (which means that all modifications you make in your function affect the original array), it’s trivial to look at the array itself to see if you did indeed remove duplicates.
4. The number you return from your function is the total number of unique numbers in the array. So, if you passed this array [1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,6,6,6,7,7,7,7], by the time your function executes, you’ll return the number 7 because there are 7 unique numbers and everything else is a duplicate of those uniques.

In a nutshell, you remove duplicates in-place and return the number of unique numbers in the array.

I hope to God this makes sense.

My solution

var removeDuplicates = function(nums) {
    let pointer = 0;
    for (let j=1;j<nums.length;j++) {
        if (nums[pointer] != nums[j]) {
            pointer++;
            nums[pointer] = nums[j];
        }
    }
    console.log(nums,pointer+1);
    return pointer+1;
    
};

Here I created a ‘pointer’ variable to keep track of the first element of the array, and then initiated a for loop that keeps track of the next element of the array.

This allows me to compare them like this:

Imagine an array of [1,1,2]

We initialize a pointer = 0.

Now we loop over the array in such a way that we start at the 1st position (not the 0th one). So nums[j] is 1, and nums[pointer] = 1.

Given how the code is written now, the loop will skip the first comparison (since both nums[j] and nums[pointer] are == 1) but trigger the conditional on the next loop. `nums[pointer] != nums[j]` is true, so we increment pointer (which makes it 1) and make nums[pointer] (which is the second ‘1’ on the array) the value of nums[j] (which is ‘2’).

Now we have [1,2,2]

The function hits the ‘return’ path and gives us pointer+1 (which is 2) as the answer. The reason it does this is because arrays are zero index based.

Note: you’ll have noticed that we actually didn’t remove duplicates here. If anything, we ‘pushed’ them away from the ‘line of sight’ (so to speak) of the length of uniques. In essence if we looked at the first two elements of the array (where 2 = pointer+1, or total number of uniques), we’ll have a perfectly sorted array. This weirded me out, but it’s apparently a perfectly justifiable solution to this problem (“with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.”).

There it is, and I had to rely heavily on hints for this one!