Understanding the 'Remove Duplicates from Sorted Array' Problem

The task is to remove duplicates from a sorted array of numbers and return the new length of the array without duplicates

Problem Type- Easy

https://leetcode.com/problems/remove-duplicates-from-sorted-array

O(n) Solution using Two Pointers

function removeDuplicates(nums) {
    let k = 1;
    if(nums.length < 1) {
        return 0;
    }
    for(let i = 1; i < nums.length; i++) {
        if(nums[i] != nums[i - 1]) {
            nums[k] = nums[i];
            k++;
        }
    }
    return k;
};

Let me break it down for you:

1. I started by initializing a variable k to 1.

2. I checked if the array nums is empty. If it is, I returned 0 since there are no duplicates to remove.

3. I compared the current element nums[i] with its previous element nums[i - 1].

4. I used a for loop to iterate through the array starting from the second element (index 1) up to the last element.

5. If the current element is not equal to the previous element, it means it's a unique number. So, I placed this unique number at position k in the array and incremented k by 1.

6. Finally, I returned the value of k

   Learnings and Takeaways

   • Using a pointer or an index variable like k in the solution is important for ensuring that we only compare each element once and avoid duplicates and we don't have to use nested loops otheriwise our solution will be of O(n^2) or incorrect.

   • Since we are not using any extra space that grows with the size of the input array, the space complexity remains constant at O(1).

Comment if I have committed any mistake. Let's connect on my socials. I am always open for new opportunities , if I am free :P

Linkedin| Twitter | ShowwCase