Day 9 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#26....
source link: https://dev.to/corndog_com567/day-9-of-studying-leetcode-solution-until-i-can-solve-one-on-my-own-problem26remove-duplicates-from-sorted-arrayeasyjs-2fnm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Day 9 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#26.Remove Duplicates from Sorted Array(Easy/JS)
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];
}
Enter fullscreen mode
Exit fullscreen mode
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).
Enter fullscreen mode
Exit fullscreen mode
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 4 with nothing (delete) (note 3)
//In test case [1,1,2], this step will delete the first "1" in-
//place from the array.
i--;
//reduce index i by 1 to reset it's position then start iterating
//and return it's value
}
}
};
Enter fullscreen mode
Exit fullscreen mode
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].
};
Enter fullscreen mode
Exit fullscreen mode
Solution Submission detail as of 2/20/2022
(Data below could vary since there are new tests/submissions daily)
- Runtime: 100ms
- Memory Usage: 44.3mb
References:
LeetCode Problem Link
LeetCode Discussion: sze_chi
Note 1: for loop
Note 2: Access an array item by its index
Note 3: Splice()
Note 4: Prefix increment
Blog Cover Image Credit
Recommend
-
179
awesome-java-leetcode 我如今是一名 Android Developer,大学的我曾是一名 ACMer,我一直认为数据结构和算法是作为一名程序员必须掌握和善于利用的,为了不让数据结构和算法淡出我的记忆,所以我打算重拾 LeetCode 之 Algorithm,语言选择的是 Java,题库...
-
114
awesome-java-leetcode 我如今是一名 Android Developer,大学的我曾是一名 ACMer,我一直认为数据结构和算法是作为一名程序员必须掌握和善于利用的,为了不让数据结构和算法淡出我的记忆,所以我打算重拾 LeetCode 之 Algorithm,语言选择的是 Java,题库...
-
134
Files Permalink Latest commit message...
-
39
README.md ? awesome-golang-leetcode LeetCode of algorithms with golang solution(updating?).
-
14
Two Sum: Easy Problem Given an array of integers, return indices of the two numbe...
-
8
-
3
-
3
-
4
Road to solve LeetCode #322 My first solution is using dynamic programming. Then I want to also try breath-first-search. The first version of...
-
2
Until his dying dayMastodon Bastian Allgeier:
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK