Day 1; I4G 10 Days of Code Challenge

INTRODUCTION

I only just learned about time and space complexities in DSAs last week and was quite excited to see a mail from Ingreessive4Good a couple of days later informing me about the code challenge. I had thought "well, here's a way to practice and improve my knowledge of DSAs". Day 1 was about removing duplicate elements from a sorted array. In simpler terms (*hopefully), I was instructed to remove duplicates of a value in a group of values, such that all values left are unique.

THOUGHT PROCESS

I remember first thinking about how the problem was quite similar to those mental math questions in primary school (Not necessarily meaning I found it easy. Mental math was tough then). The word "non-decreasing" definitely wasn't helping.

I translated non-decreasing to not decreasing and then to increasing and my first idea was to create a new empty array, go through the original array and compare values. Then, store all the unique values into the new array whilst returning the length of that new array. Of course, this was before I found out that the solution had to be applied "in-place". (*cue tears)

Next idea was to create extra empty elements within the array while scanning for duplicates and move the duplicates there. Then, delete all empty elements in the array. How to return the length of unique elements? Not so sure. The last algorithm, in addition to being incomplete, was also not exactly time and space effective. I thought to optimise the algorithm by swapping the elements in place of creating additional empty elements.

SOLUTION

Finally, I made some adjustments that allowed the replacement to be more planned. In order for this to happen, there need to be 2 pointers scanning the array. The first pointer, f, would scan for unique values by comparing the current value with the previous one. It started from the 2nd element (index 1) till the end of the array. Then, the second pointer will scan through the array, replacing each element with a unique element from "f" in non-decreasing order and then, moving to the next element. It was initialised at the 2nd element till the point where there were no duplicates observed by "f"

An Illustration :

s returns 5 since it is at the fifth element. Since both pointers(variables) did a single scan of the array, the time complexity was = O(n). I used just two extra variables without creating extra memory for a new array or array element. So, Space complexity = O(1).

CODE

I wrote this with JavaScript and got a better run time during the second try after adjusting the indentations!

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let first = 1
    for (r=1; r < nums.length; r++) {
        if (nums[r] !== nums[r-1]) {
            nums[first] = nums[r]
            first++
        }
    }
    return first;
};

Output:

Overall, it was definitely exciting trying this. I am currently reading this on DSAs : w3schools.in/data-structures/tutorials

Ciao!