Day 9 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#26.Remove Duplicates from Sorted Array(Easy/JS)

#javascript #beginners #programming #algorithms

Intro: I am a former accountant turned software engineer graduated from coding bootcamp in January 2022. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:

Pick a leetcode problem randomly or Online Assessment from targeted companies.
Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
Code out the solution in LeetCode without looking at the solutions
Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.

Problem#26.Remove Duplicates from Sorted Array

Difficulty: Easy Language: JavaScript

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.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

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 * 104
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

Solution 1:

var removeDuplicates = function(nums) {
    for (i = 0; i < nums.length; i++) {

//Loop (note 1) through 'nums' array

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

//find the number that is equal to the next number (note 2)

            nums.splice(i, 1);

//replaces 1 element at index i with nothing (delete) (note 3)
//In test case [1,1,2], since nums[0] and nums[1] are both "1"
//nums[0] - the first "1" in the array gets deleted.

            i--;

//reduce index i by 1 to reset it's position then keep iterating

        }
    }
};

Solution Submission detail as of 2/18/2022
(Data below could vary since there are new tests/submissions daily)

Runtime: 150ms
Memory Usage: 45.3mb

Solution 2 (slightly improved run time and saved space):

var removeDuplicates = function(nums) {
    let i = 0;

//set initial value of index 1 as 0

    for (let j = 0; j < nums.length; j++) {

//Loop (note 1) through 'nums' array

        if (nums[j] != nums[i]) 

//find the number at index j that is different from the number
//at index i.

            nums[++i] = nums[j];

//replace the value at index 'i+1' with the value at index j. In
//test case [1,1,2], while initial i is set as '0', value at index
//0 is '1' and value at index 2 is '2', since they don't equal, we
//increase i by 1 (++i: from '0' to '1') and then replace value at
//index 1 with '2' (value at index 2). New array will be [1,2,2],
//from this point, i increased to '1' and the loop stopped since
//there is nums[2] reaches the end of array 'nums'.

    }
    return ++i;

//increase i by 1 (note 4) to to get the total number of non-
//duplicated element. To continue the example above, once i turned
//into '1', we increase it by 1 to get "2". And that's the total
//number of non duplicated element in array [1,1,2].

};

Solution Submission detail as of 2/20/2022
(Data below could vary since there are new tests/submissions daily)